为什么C++从队列中提取元素的性能较差？（包括比较）

Question

<>我在C++和Python标准LIBS（队列和堆）之间做了一个快速性能测试，与C中的基本实现相反。

• Python 2.7.5:：Anaconda 1.7.0（x86_64）
• i686-apple-darwin11-llvm-g++-4.2（GCC）4.2.1
• 要排序的元素是int。在

对队列构造段的性能差异并不感到惊讶（我的意思是从元素数组创建一个已排序的堆）。在

这有点奇怪。我不知道我是否遗漏了什么。。。为什么C++要花这么长时间提取元素？这是在C++上构建优先级队列的正确方法吗？在

对于Python，我的实现如下所示

# Construct the queue
heapq.heapify(int_values)

# Extract element
heapq.heappop(int_values)

C++中的P>：

^{pr2}$

这里是完整的C++代码，以及我如何测量时间。 https://gist.github.com/srodrb/6916802

下面是Python代码： https://gist.github.com/srodrb/6917081

<>编辑：<强>注意，我不假装优化我的C++代码<强>，这个比较对我来说是有效的，因为我正在测试标准库的工具。我只是想知道这个巨大的性能差距。我也不把C++和Python进行对比，因为可能HEAPQ调用了一些C函数。在

Answer 1

只需在数组/向量上使用make_heap和pop_heap。在