Re: [boost] Determining interest in container with efficient random access insert and erase

You have Random access iterators with access time O(logN) ( you can run a std::sort over the data structure with good results).

Traversal operations are mandated to be Amortized O(1) for random-access iterators. If the traversal is O(log N) it isn't a random-access iterator. http://en.cppreference.com/w/cpp/concept/RandomAccessIterator Neil