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 features 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