我实现了一个算法，我使用优先级队列。我被这个问题所激励：Transform a std::multimap into std::priority_queue
我将以其特定的优先级值存储多达1000万个元素。
然后我想迭代直到队列为空。每次检索元素时，它也会从队列中删除。
在此之后，我计算元素优先级值，因为它可以改变之前的迭代。
如果值确实增加，我将元素againg插入队列。这通常取决于进展。 （在前25％它没有发生，在接下来的50％它确实发生，在过去的25％它将发生多次）。
收到下一个元素而不重新插入后，我将处理它。这对于我不需要此元素的优先级值，而是此元素的技术ID。
这就是我直觉选择std::multimap来实现这一目标的原因，使用.begin()获取第一个元素，.insert()插入它，.erase()删除它。此外，我没有直观地选择std::priority_queue因为该主题的其他问题回答std::priority_queue最有可能仅用于单个值而不用于映射值。
在阅读上面的链接之后，我使用优先级队列类比重新实现了链接中的另一个问题。我的运行时间似乎不是那么不平等（大约一个小时就有10个mio元素）。现在我想知道为什么std::priority_queue更快。
由于许多重新插入，我实际上会期望更快地成为std::multimap。也许问题是多图的重组太多了？
总结一下：您的运行时配置文件涉及从抽象优先级队列中删除和插入元素，同时尝试使用std::priority_queue和std::multimap作为实际实现。
插入优先级队列和多重映射都具有大致相同的复杂性：对数。
但是，从多图表中删除下一个元素与优先级队列之间存在很大差异。使用优先级队列，这将是一个持续复杂的操作。底层容器是一个向量，你要从向量中移除最后一个元素，这将主要是一个无汉堡。
但是使用multimap，您将从多图的一个极端中删除该元素。
多图的典型底层实现是平衡的红/黑树。从多图的一个极端重复元素移除很有可能使树偏斜，需要频繁地重新平衡整个树。这将是一项昂贵的操作。
这可能是您看到明显的性能差异的原因。
我认为主要区别在于两个事实：
因此，虽然两者的操作的理论时间复杂性是相同的O(log(size))，但我认为来自erase的multimap，并且重新平衡RB树执行更多操作，它只需要移动更多元素。 （注意：RB树不是强制性的，但经常被选为multimap的底层容器）
vector）。我怀疑重新平衡也慢了，因为RB树依赖于节点（相对于向量的连续内存），这使得它容易出现缓存未命中，尽管必须记住堆上的操作不是以迭代方式完成的，而是跳跃通过矢量。我想要确定一个人必须对它进行分析。
以上几点适用于插入和删除。我会说，区别在于big-O表示法中丢失的常数因素。这是直觉思维。
地图变慢的抽象高级解释是它做得更多。它始终保持整个结构的排序。此功能需要付费。如果您使用的数据结构不能保留所有元素的排序，则不会支付该费用。
算法解释：
为了满足复杂性要求，必须将映射实现为基于节点的结构，而优先级队列可以实现为动态数组。 std::map的实现是一个平衡的（通常是红黑色）树，而std::priority_queue是一个以std::vector作为默认底层容器的堆。
堆插入通常非常快。与平衡树的O（log n）相比，插入堆中的平均复杂度为O（1）（尽管最差情况相同）。创建n个元素的优先级队列具有O（n）的最坏情况复杂度，而创建平衡树是O（n log n）。查看更多深度比较：Heap vs Binary Search Tree (BST)
其他，实施细节：
与基于节点的结构（如树或列表）相比，数组通常更有效地使用CPU缓存。这是因为阵列的相邻元素在存储器中相邻（高存储器局部性），因此可以适合单个高速缓存行。然而，链接结构的节点存在于存储器中的任意位置（低存储器局部性）中，并且通常仅一个或极少数位于单个高速缓存行内。现代CPU的计算速度非常快，但内存速度却是瓶颈。这就是为什么基于阵列的算法和数据结构往往明显快于基于节点的原因。