Looking for an indexed container with lookup and insertion/deletion in O(log n) in C++

Question

I am looking for an indexed container in C++ which has the following properties:

• get the element at the k-th position in O(log n)
• insert an element at the k-th position in O(log n)
• delete the element at the k-th position in O(log n)

I was thinking about a workaround using a map which works similar, but I can't figure it out. There is also a container in Java called TreeList which has said properties.

Answer 1

You need an order statistics tree. It's a binary search tree that keeps track of the size of each subtree, and that information can be used to perform the operations you need in logarithmic time. The C++ standard library doesn't implement such a data structure, so you need to implement your own or use another library. The GNU policy-based data structures extension includes this.