Efficient Data Structure for Insertion

Question

I'm looking for a data structure (array-like) that allows fast (faster than O(N)) arbitrary insertion of values into the structure. The data structure must be able to print out its elements in the way they were inserted. This is similar to something like List.Insert() (which is too slow as it has to shift every element over), except I don't need random access or deletion. Insertion will always be within the size of the 'array'. All values are unique. No other operations are needed.

For example, if Insert(x, i) inserts value x at index i (0-indexing). Then:

• Insert(1, 0) gives {1}
• Insert(3, 1) gives {1,3}
• Insert(2, 1) gives {1,2,3}
• Insert(5, 0) gives {5,1,2,3}

And it'll need to be able to print out {5,1,2,3} at the end.

I am using C++.

Answer 1

Use skip list. Another option should be tiered vector. The skip list performs inserts at const O(log(n)) and keeps the numbers in order. The tiered vector supports insert in O(sqrt(n)) and again can print the elements in order.

EDIT: per the comment of amit I will explain how do you find the k-th element in a skip list:

For each element you have a tower on links to next elements and for each link you know how many elements does it jump over. So looking for the k-th element you start with the head of the list and go down the tower until you find a link that jumps over no more then k elements. You go to the node pointed to by this node and decrease k with the number of elements you have jumped over. Continue doing that until you have k = 0.

Answer 2

Did you consider using std::map or std::vector ?

You could use a std::map with the rank of insertion as key. And vector has a reserve member function.