Sorted data structure fast iteration, insertion, deletion by iterator

Question

I am looking for a data structure that has the following properties:

• Sorted(unless this is not needed for sorted order iteration)
• O(1) iteration in the sorted order.
• Fast insertion. I would think O(lg(n)) is the way to go.
• Fast deletion using an iterator. I am hoping for at least the same speed as insertion. I will never have to delete an item by value, and will always have the iterator available. This requirement means insertion and iteration will never invalidate iterators, unless deletion by value happens at the same speed as deletion by iterator.

Anything else is not relevant and will never be used.

After searching around for a while I was not able to find a data structure that follows these properties. A heap allows for fast insertion and removal(althought not by iterator per se), but is not easy to iterate in the required way.

I have also looked at a sorted vector. This has fast insertion and correct iteration, but deletion is pretty hard there.

I would say this is a pretty common data structure, even though I was not able to find a matching structure. Furthermore I think the fact that I always have an iterator when deleting might improve the performance.

I hope you can help me in the right direction.

Answer 1

std::set or std::multiset is specified to have logarithmic complexity for insert(), and amortized constant complexity for deletion via an existing iterator.

Iterating over a set/multiset will iterate in sorted order.