Looking for special C++ data structure

I'm looking for a C++ implementation of a data structure ( or a combination of data structures ) that meet the following criteria:

• items are accessed in the same way as in std::vector
• provides random access iterator ( along with iterator comparison <,> )
• average item access(:lookup) time is at worst of O(log(n)) complexity
• items are iterated over in the same order as they were added to the container
• given an iterator, i can find out the ordinal position of the item pointed to in the container, at worst of O(log(n)) complexity
• provides item insertion and removal at specific position of at worst O(log(n)) complexity
• removal/insertion of items does not invalidate previously obtained iterators

Thank you in advance for any suggestions

Dalibor

(Edit) Answers:

The answer I selected describes a data structure that meet all these requirements. However, boost::multi_index, as suggested by Maxim Yegorushkin, provides featu开发者_开发知识库res very close to those above.

(Edit) Some of the requirements were not correctly specified. They are modified according to correction(:original)

(Edit) I've found an implementation of the data structure described in the accepted answer. So far, it works as expected. It's called counter tree

(Edit) Consider using the AVL-Array suggested by sp2danny

Based on your requirements boost::multi_index with two indices does the trick.

The first index is ordered index. It allows for O(log(n)) insert/lookup/remove. The second index is random access index. It allows for random access and the elements are stored in the order of insertion. For both indices iterators don't get invalidated when other elements are removed. Converting from one iterator to another is O(1) operation.

Let's go through these...

• average item lookup time is at worst of O(log(n)) complexity
• removal/insertion of items does not invalidate previously obtained iterators
• provides item insertion and removal of at worst O(log(n)) complexity

That pretty much screams "tree".

• provides random access iterator ( along with iterator comparison <,> )
• given an iterator, i can find out the ordinal position of the item pointed to in the container, at worst of O(log(n)) complexity
• items are iterated over in the same order as they were added to the container

I'm assuming that the index you're providing your random-access iterator is by order of insertion, so [0] would be the oldest element in the container, [1] would be the next oldest, etc. This means that, on deletion, for the iterators to be valid, the iterator internally cannot store the index, since it could change without notice. So just using a map with the key being the insertion order isn't going to work.

Given that, each node of your tree needs to keep track of how many elements are in each subtree, in addition to its usual members. This will allow random-access with O(log(N)) time. I don't know of a ready-to-go set of code, but subclassing std::rb_tree and std::rb_node would be my starting point.

See here: STL Containers (scroll down the page to see information on algorithmic complexity) and I think std::deque fits your requirements.

AVL-Array should fit the bill.

Here's my "lv" container that fit the requirement, O(log n) insert/delete/access time. https://github.com/xhawk18/lv

The container is header only C++ libraries, and has the same iterator and functions with other C++ containers, such as list and vector.

"lv" container is based on rb-tree, each node of which has a size value about the amount of nodes in the sub-tree. By check the size of left/right child of a tree, we can fast access the node randomly.