STL priority_queue <pair> vs map
I need a priority queue that will store a value for each key, not just the key. I think viable options std::multi_map<K,V>
, as they are repeated in key order or std::priority_queue<std::pair<K,V>>
as it sorts on K to V. Is there any reason I should prefer one over the other other than personal preference? Are they really the same or am I missing something?
source share
The priority sort is first sorted in O (N) time, and then iterating through all the elements in descending order takes O (N log N). It is stored std::vector
behind the scenes, so there is only a small factor after the behavior of the big O. Part of that, however, moves elements within the vector. If sizeof (K)
or is sizeof (V)
large, it will be slightly slower.
std::map
is a red-black tree (in general practice), so it takes O (N log N) time to insert elements, keeping them sorted after each insert. They are stored as related nodes, so each element carries overhead malloc
and free
. Then it takes O (N) time to iterate over them and destroy the structure.
In general, a priority queue should have better performance, but it limits your use more: items of data will move during iteration, and you can only iterate once.
If you don't need to insert new elements during iteration, you can use std::sort
with std::vector
, of course. This must be trumped by priority_queue
some constant factor.
As with most things in performance, the only way to judge for sure is to try it both ways (with real benchmarks) and measure.
By the way, to maximize performance, you can define a custom compare function to ignore V
and only compare K
internally pair<K,V>
.
source share