Efficient insert data structure

Question

I am looking for a data structure (similar to an array) that allows fast (faster than O (N)) arbitrary insertion of values ​​into the structure. The data structure should be able to print its elements in the form in which they were inserted . This is similar to something like List.Insert () (which is too slow since it should move every item), except that I don't need random access or deletion. The insert will always be within the size of the array. All values ​​are unique. No other operations are required.

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

• The insert (1, 0) gives {1}
• The insert (3, 1) gives {1,3}
• Box (2, 1) gives {1,2,3}
• The insert (5,0) gives {5,1,2,3}

And he will have to be able to print {5,1,2,3} at the end.

I am using C ++.

Answer 1

Use the skip list . Another option should be a multi-level vector . The skip list inserts into const O (log (n)) and stores the numbers in order. A layered vector supports insertion into O (sqrt (n)) and can again print items in order.

EDIT: for the amit comment I will explain how you find the kth element in the skip list:

For each element, you have a tower for links to the following elements, and for each link you know how many elements it jumps. Therefore, looking for the k-th element that you start with the head of the list, and go down the tower until you find a link that jumps to no more than k elements. You go to the node indicated by that node and decrease k with the number of elements you jumped over. Keep doing this until you get k = 0.

Answer 2

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

You can use std::map with an input rank as a key. And vector has a member function reserve .

Answer 3

You can use std::map mapping (index, insertion-time) pairs for values ​​where the insertion time is an integer "auto-increment" (in terms of SQL). The order in pairs should be

 (i, t) < (i*, t*) 

then and only then

 i < i* or t > t* 

In code:

 struct lt { bool operator()(std::pair<size_t, size_t> const &x, std::pair<size_t, size_t> const &y) { return x.first < y.first || x.second > y.second; } }; typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; void insert(array_like &a, int value, size_t i) { a[std::make_pair(i, a.size())] = value; } 

Answer 4

Regarding your comment:

List.Insert () (which is too slow as it should shift every item)

Lists do not change their values, they iterate over them to find the location you want to insert, be careful what you say. This can confuse beginners like me.

Answer 5

The solution included in GCC by default is a rope data structure. Here is the documentation. Typically, ropes come to mind when working with long lines of characters. Here we have int instead of characters, but it works the same. Just use int as a template parameter. (There may also be pair s, etc.)

Here's a description of the rope on Wikipedia .

Basically, it is a binary tree that maintains the number of elements in the left and right subtrees (or equivalent information called order statistics), and these counts are updated accordingly when the subtrees are rotated when elements are inserted and deleted. This allows O (log n) operations to be performed.

Answer 6

In C ++, you can just use a vector map, for example:

 int main() { map<int, vector<int> > data; data[0].push_back(1); data[1].push_back(3); data[1].push_back(2); data[0].push_back(5); map<int, vector<int> >::iterator it; for (it = data.begin(); it != data.end(); it++) { vector<int> v = it->second; for (int i = v.size() - 1; i >= 0; i--) { cout << v[i] << ' '; } } cout << '\n'; } 

Fingerprints:

 5 1 2 3 

Just as you want, and the inserts are O (log n).