c++ - 在这种情况下，为什么 STL priority_queue 并不比 multiset 快多少？

Question

我正在比较 STL (g++) priority_queue 的性能，发现 push 和 pop 没有我预期的那么快。见以下代码:

#include <set>
#include <queue>

using namespace std;

typedef multiset<int> IntSet;

void testMap()
{
    srand( 0 );

    IntSet iSet;

    for ( size_t i = 0; i < 1000; ++i )
    {
        iSet.insert(rand());
    }

    for ( size_t i = 0; i < 100000; ++i )
    {
        int v = *(iSet.begin());
        iSet.erase( iSet.begin() );
        v = rand();
        iSet.insert(v);
    }
}

typedef priority_queue<int> IntQueue;

void testPriorityQueue()
{
    srand(0);
    IntQueue q;

    for ( size_t i = 0; i < 1000; ++i )
    {
        q.push(rand());
    }

    for ( size_t i = 0; i < 100000; ++i )
    {
        int v = q.top();
        q.pop();
        v = rand();
        q.push(v);
    }
}

int main(int,char**)
{
   testMap();
   testPriorityQueue();
}

我编译了这个 -O3 然后运行了 valgrind --tool=callgrind, KCachegrindtestMap 占用总 CPU 的 54%testPriorityQueue 占用 44% 的 CPU

(没有-O3 testMap比testPriorityQueue快很多)testPriorityQueue 貌似占用时间最多的函数被调用了

void std::__adjust_heap<__gbe_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, long, int, std::less<int> >

该函数似乎是从 pop() 调用中调用的。

这个函数到底做了什么？有没有办法通过使用不同的容器或分配器来避免它？

Answer 1

优先级队列实现为 heap : 这必须在您移除 head 元素时每次“重新平衡”。在链接描述中，delete-min 是一个 O(log n) 操作，实际上是因为 min(或 head)元素是 < em>扁平二叉树的根。

该集合通常实现为 red-black tree ，并且 min 元素将是最左边的节点(因此要么是叶子，要么最多有一个右 child )。因此，它最多有 1 个 child 要移动，并且可以根据允许的不平衡程度在多个 pop 调用中分摊再平衡。

请注意，如果堆有任何优势，它很可能位于引用位置(因为它是连续的而不是基于节点的)。这正是 callgrind 难以准确测量的优势，因此我建议在接受此结果之前也运行一些经过的实时基准测试。