The problem seems to be an interesting little exercise that John Bentley once proposed to me: Insert a sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions: Do you use a vector (a contiguously allocated sequence of elements) or a linked list?
http://www.stroustrup.com/bs_faq.html
* Generate N random integers and insert them into a sequence so that each is inserted in its proper position in the numerical order. 5 1 4 2 gives:
- 5
- 1 5
- 1 4 5
- 1 2 3 4
* Remove elements one at a time by picking a random position in the sequence and removing the element there. Positions 1 2 0 0 gives
- 1 2 4 5
- 1 4 5
- 1 4
- 4
* For which N is it better to use a linked list than a vector (or an array) to represent the sequence?
GoingNative 2012 Bjarne Stroustrup: C++11 Style
Challenge accepted. To be continued...