Bar*_*Yeo 3 c++ heap stl priority-queue data-structures
具体来说,STL优先级队列容器适配器使用哪种堆变体？我正在使用我自己的手动滚动二进制堆和双桶结构实现进行基准测试,所以只是想知道.任何有趣的实施知识的奖励积分!
这个问题标记为C++(而不是要求特定编译器的特定于实现的详细信息),因此我检查了标准以获取任何信息.在23.6.4各个部分,我们了解到,priority_queue简单地表现为,如果它使用make_heap,push_heap和pop_heap.然后这些函数的文档(在25.4.6截面)为具有复杂性At most 3 * (last - first) comparisons.,At most log(last - first) comparisons.和At most 2 * log(last - first) comparisons.分别.因此,某些堆实现可能由这些特性指示,但不会调出特定的堆.