Priority Queue Option

Question

I need some sort of priority queue for storing pairs <key, value>. The values ​​are unique, but there are no keys. I will perform the following operations (most common):

• random insertion;
• extraction (and deletion) of all elements with the least key.
• accidental deletion (by value);

I can’t use std::priority_queuebecause it only supports head removal.

I am currently using unsorted std::list. Insertion is performed by simply pushing new elements on the back (O (1)). Operation 2 sorts the list using list::sort(O (N * logN)) before doing the actual search. Removing , however, is O (n), which is a bit expensive.

Any idea of ​​a better data structure?

Answer 1

Ok, so I checked a lot of options and got something based on the idea of ​​Matthieu M .. Currently I use std::map<key_type, std::list<value_type> >where it value_typecontains std::list<value_type>::iteratorfor myself, which is useful for uninstalling.

The deletion should check if the vector is free, which implies a request mapand, possibly, a call erase. In the worst case, the difficulty is that the keys are different, O(logN)for insert, O(1)for extraction, and O(logN)for removal. I have very good experimental results compared to other alternatives on my test machine.

std::vector (O (N) , ), , .

Answer 2

, .. <value, key>?

std::map O(logn) O(n) ( ) O(logn) ( ).

map (, std::map), : O(1), O(n), O(1).

Answer 3

, . .

:

• O(1)
• O(N log N)
• O(N) ( , , )

std::multi_map, :

• O(log N)
• O(log N) < - , ?
• O(N)

std::map< key, std::vector<value> >:

• O(log M) M -
• O(1) (begin )
• O(N)

... . :

typedef std::vector<value_type> data_value_t;
typedef std::map<key_type, data_value_t> data_t;

typedef std::pair<data_t::iterator,size_t> index_value_t;
  // where iterator gives you the right vector and size_t is an index in it

typedef std::unordered_map<value_type, index_value_t> index_t;

... ! , :

• O(log M) → - O(1)
• O(N/M) → , N/M
• O(N/M) → - O(1), O(1), O(N/M), . list O(1)... ( - ).

, - . , , .

std::map<key_type, std::vector<value_type> > . .

Answer 4

Visual Studio, hash_multimap. , Boost , . , STL multimap STL multiset

Answer 5

std:: multimap , .

, , / (begin(), rbegin()) (equal_range, lower_bound, upper_bound).

(EDIT: , , 30, )

Answer 6

If I understood correctly, your performance goal is to have fast (1) and (3), and (2) is not so important. In this case, and given that the values ​​are unique, why not just have std::set<value>and perform a sequential search (2)? You will have O (log n) for (1) and (3) and O (n) for (2). Even better, if your STL has std::hash_set, you would approach O (1) for (1) and (3).

If you need something better than O (n) for (2), one option would be to have a set of priority queues.