在这种情况下,为什么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,KCachegrind testMap占用了总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

优先级队列实现为堆:每次删除head元素时都必须"重新平衡" .在链接描述中,delete-min是一个O(log n)操作,实际上因为min(或head)元素是展平二叉树的根.

该集合通常实现为红黑树,而min元素将是最左边的节点(因此要么是叶子,要么最多只有一个右子节点).因此,最多可以移动1个孩子,并且可以pop根据允许的不平衡程度对多次调用进行重新平衡.

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