c++ 为什么 std::multimap 比 std::priority_queue 慢

Question

我实现了一种使用优先级队列的算法。我被这个问题所激励: 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的重组太多了？

Answer 1

总结:您的运行时配置文件涉及从抽象优先级队列中删除和插入元素，您尝试同时使用 std::priority_queue 和 std::multimap 作为实际的实现。

插入优先级队列和插入多映射具有大致相同的复杂度:对数。

但是，从多重映射和优先级队列中移除下一个元素有很大的不同。对于优先级队列，这将是一个复杂度恒定的操作。底层容器是一个 vector ，您要从 vector 中删除最后一个元素，这将主要是一个空汉堡。

但是对于多重映射，您要从多重映射的最末端之一移除元素。

multimap 的典型底层实现是平衡的红/黑树。从 multimap 的一个极端中重复删除元素很可能会使树倾斜，需要对整个树进行频繁的重新平衡。这将是一项昂贵的操作。

这可能是您看到明显的性能差异的原因。