C++: A variation of priority queue
- by Helltone
I need some kind of priority queue to store pairs <key, value>. Values are unique, but keys aren't. I will be performing the following operations (most common first):
random insertion;
retrieving (and removing) all elements with the least key.
random removal (by value);
I can't use std::priority_queue because it only supports removing the head.
For now, I'm using an unsorted std::list. Insertion is performed by just pushing new elements to the back (O(1)). Operation 2 sorts the list with std::sort (O(N*logN)), before performing the actual retrieval. Removal, however, is O(n), which is a bit expensive.
Any idea of a better data structure?
