c++ - C++ STL优先级队列使用什么堆结构？

Question

具体来说，STL 优先级队列容器适配器使用什么堆变体？我正在对它与我自己的手工二进制堆和双桶结构实现进行基准测试，所以只是想知道。任何有趣的实现知识均可加分!

Answer 1

这个问题被标记为 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. 分别。因此，某些堆实现可能由这些特征指示，但没有调用特定的堆。