c++ - Fastest way to store internally sorted map elements

Question

Are there any ordered container that allow O(n) in-ordered deletion and traversal? I'm trying to do the following:

Hello  -> 1,2,3,4,5,6
Hello1 -> 24,15,13,10,8,7

I need to be able to insert and delete continuously from Hello or Hello1 as quickly as possible. I was thinking of using a priority queue, but each time I want to delete I spend O(logn) adjusting, so n deletions will cost me O(nlogn) time to keep the internal structure ordered. Are there any data structures that can accomplish this task in O(n) time?

Answer 1

Just use a std::vector, with some sorting pegged on top; don't use std::sort every time - use a merge sort.

Complexity is important, but when the data set is small the time taken for memory allocation and cache misses will far out way this. Generally, profile it, but I would conject in this case a vector will be fine.

Think carefully about if you need to keep the structure always sorted; can you insert a number of items before resorting? What about 2 vectors and merging on a lookup? Think carefully about your algorithms; you can delete any number of items in O(n), for instance.