7

I need a priority queue that will store a value for every key, not just the key. I think the viable options are std::multi_map<K,V> since it iterates in key order, or std::priority_queue<std::pair<K,V>> since it sorts on K before V. Is there any reason I should prefer one over the other, other than personal preference? Are they really the same, or did I miss something?

Baruch
  • 20,590
  • 28
  • 126
  • 201
  • `std::priority_queue` by default stores your elements as `std::vector` under the hood unless you specify different. It's just an *adapter* of container, not *container* itself. – pkrysiak Jan 12 '15 at 09:03
  • @pkrysiak Right. I meant using the default vector-backed one – Baruch Jan 12 '15 at 09:06
  • 1
    then the question decays to basically [this one](http://stackoverflow.com/questions/454762/vector-or-map-which-one-to-use) – pkrysiak Jan 12 '15 at 09:09
  • Personally I would go with the one with the nicest interface for what you want to do. – Galik Jan 12 '15 at 09:12
  • @pkrysiak `std::priority_queue` isn't the same as a pre-sorted vector because it allows O(log N) insertion. It's preferable, though, if insertion isn't needed. – Potatoswatter Jan 12 '15 at 09:27

1 Answers1

16

A priority queue is sorted initially, in O(N) time, and then iterating all the elements in decreasing order takes O(N log N) time. It is stored in a std::vector behind the scenes, so there's only a small coefficient after the big-O behavior. Part of that, though, is moving the elements around inside the vector. If sizeof (K) or sizeof (V) is large, it will be a bit slower.

std::map is a red-black tree (in universal practice), so it takes O(N log N) time to insert the elements, keeping them sorted after each insertion. They are stored as linked nodes, so each item incurs malloc and free overhead. Then it takes O(N) time to iterate over them and destroy the structure.

The priority queue overall should usually have better performance, but it's more constraining on your usage: the data items will move around during iteration, and you can only iterate once.

If you don't need to insert new items while iterating, you can use std::sort with a std::vector, of course. This should outperform the priority_queue by some constant factor.

As with most things in performance, the only way to judge for sure is to try it both ways (with real-world testcases) and measure.

By the way, to maximize performance, you can define a custom comparison function to ignore the V and compare only the K within the pair<K,V>.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421