Container with fast inserts and index? [closed]

Question

I am looking for a C++ container class that is indexed like an std::vector, but has fast insertions, deletions and indexing. For example, a vector interface implemented with an underlying balancing tree would have O(logN) insertions/deletions and O(logN) indexing as well.

To be clear: I am not looking for std::map<int, T>. Inserting an element at index N should increment indices of all subsequent elements in the array which would not be the case with std::map<int, T>.

I have found AVL Array which does exactly what I am looking for. It has the right interface, but I would like to see if there are other options.

Do you know any other (production-quality) implementations? Maybe something more popular (does boost have something of the sort?). Something with a smaller memory footprint? (A node holding a pointer in the AVL Array is 64 bytes on my machine.)

Answer 1

Thought about using SkipLists yet? Basically it is a linked list, with multiple levels of shortcuts added on top that are organised as a tree. No shuffling of nodes, just a few pointer updates. The shortcuts allow you to iterate much faster across your list. One of my favorites.

http://openmymind.net/Building-A-Skiplist/

http://en.wikipedia.org/wiki/Skip_list