我实现了一种使用优先级队列的算法。 我被这个问题所激励: Transform a std::multimap into std::priority_queue
我将存储多达 1000 万个元素及其特定的优先级值。
然后我想迭代直到队列为空。 每次检索一个元素时，它也会从队列中删除。
在此之后我重新计算元素的优先级值，因为之前的迭代它可能会改变。
如果值确实增加了，我将再次将该元素插入到队列中。 这种情况更经常发生取决于进度。 (前 25% 不会发生，接下来的 50% 会发生，最后 25% 会发生多次)。
接收到下一个元素后没有重新插入，我要处理它。这是因为我不需要这个元素的优先级值，而是这个元素的技术 ID。
这就是我凭直觉选择 std::multimap 来实现这一点的原因，使用 .begin() 获取第一个元素 .insert () 插入它和 .erase() 删除它。
此外，我没有直接选择 std::priority_queue，因为该主题的其他问题回答了 std::priority_queue 很可能仅用于单个值而不是映射值。
阅读上面的链接后，我使用优先级队列类比链接中的其他问题重新实现了它。
我的运行时间似乎并没有那么不平衡(10 个 mio 元素大约需要一个小时)。
现在我想知道为什么 std::priority_queue 更快。
我实际上希望 std::multimap 更快，因为有很多重新插入。
可能问题是multimap的重组太多了？
最佳答案
总结:您的运行时配置文件涉及从抽象优先级队列中删除和插入元素，您尝试同时使用 std::priority_queue 和 std::multimap 作为实际的实现。
插入优先级队列和插入多映射具有大致相同的复杂度:对数。
但是，从多重映射和优先级队列中移除下一个元素有很大的不同。对于优先级队列，这将是一个复杂度恒定的操作。底层容器是一个 vector ，您要从 vector 中删除最后一个元素，这将主要是一个空汉堡。
但是对于多重映射，您要从多重映射的最末端之一移除元素。
multimap 的典型底层实现是平衡的红/黑树。从 multimap 的一个极端中重复删除元素很可能会使树倾斜，需要对整个树进行频繁的重新平衡。这将是一项昂贵的操作。
这可能是您看到明显的性能差异的原因。
关于c++ 为什么 std::multimap 比 std::priority_queue 慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41807720/