我需要一个优先级队列来存储每个键的值，而不仅仅是键。我认为可行的选择是 std::multi_map<K,V>因为它按键顺序迭代，或 std::priority_queue<std::pair<K,V>>因为它在 V 之前在 K 上排序。除了个人偏好之外，我有什么理由更喜欢另一个吗？它们真的一样吗，还是我漏掉了什么？
最佳答案
优先级队列最初是在 O(N) 时间内排序的，然后以降序迭代所有元素需要 O(N log N) 时间。它存储在 std::vector 中在幕后，所以在大 O 行为之后只有很小的系数。不过，其中一部分是在 vector 内部移动元素。如果sizeof (K)或 sizeof (V)很大，会慢一些。
std::map是红黑树(在通用实践中)，因此插入元素需要 O(N log N) 时间，并在每次插入后保持它们排序。它们存储为链接节点，因此每个项目都会产生 malloc和 free高架。然后需要 O(N) 的时间来迭代它们并破坏结构。
优先级队列总体上应该有更好的性能，但它对你的使用有更多的限制:数据项会在迭代过程中来回移动，你只能迭代一次。
如果迭代时不需要插入新项，可以使用std::sort用std::vector ， 当然。这应该优于 priority_queue由一些常数因子。
与性能方面的大多数事情一样，确定判断的唯一方法是同时尝试(使用真实世界的测试用例)和测量。
顺便说一下，为了最大化性能，您可以定义一个自定义比较函数来忽略 V并只比较 K在 pair<K,V> 内.
关于c++ - STL priority_queue<pair> 与 map，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27898324/