为什么在这种情况下，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 testPriorityQueue的54％需要CPU

的44％（无 - O3 testMap比testPriorityQueue） 似乎把大部分时间用于testPriorityQueue该功能被称为

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

这个功能似乎从弹出称为快得多（）打电话。

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

Answer 1

优先级队列实现为heap：必须每隔“重新平衡”时间删除head元素。在链接描述中，delete-min是O(log n)的操作，实际上是因为min（或head）元素是扁平二叉树的根。

该集合通常以red-black tree的形式实现，min元素将是最左边的节点（所以无论是叶子还是最多有一个正确的子节点）。因此，最多只有1个孩子可以被转移，并且可以根据允许的不平衡程度，在多个pop呼叫中平摊余额。

请注意，如果堆具有任何优势，那么它很可能位于参考位置（因为它是连续的而不是基于节点的）。这正是那种可以让callgrind准确测量的优势，所以我建议运行一些经过实时的基准测试，然后再接受这个结果。

Answer 2

我已经实现了一个优先级队列，使用-O3进行编译时似乎运行得更快。 也许只是因为编译器能够内联多于STL情况？

#include <set> 
#include <queue> 
#include <vector> 
#include <iostream> 

using namespace std; 

typedef multiset<int> IntSet; 

#define TIMES 10000000 

void testMap() 
{ 
    srand(0); 

    IntSet iSet; 

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

    for (size_t i = 0; i < TIMES; ++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 < TIMES; ++i) { 
     int v = q.top(); 
     q.pop(); 
     v = rand(); 
     q.push(v); 
    } 
} 


template <class T> 
class fast_priority_queue 
{ 
public: 
    fast_priority_queue() 
     :size(1) { 
     mVec.resize(1); // first element never used 
    } 
    void push(const T& rT) { 
     mVec.push_back(rT); 
     size_t s = size++; 
     while (s > 1) { 
      T* pTr = &mVec[s]; 
      s = s/2; 
      if (mVec[s] > *pTr) { 
       T tmp = mVec[s]; 
       mVec[s] = *pTr; 
       *pTr = tmp; 
      } else break; 
     } 
    } 
    const T& top() const { 
     return mVec[1]; 
    } 
    void pop() { 
     mVec[1] = mVec.back(); 
     mVec.pop_back(); 
     --size; 
     size_t s = 1; 
     size_t n = s*2; 
     T& rT = mVec[s]; 
     while (n < size) { 
      if (mVec[n] < rT) { 
       T tmp = mVec[n]; 
       mVec[n] = rT; 
       rT = tmp; 
       s = n; 
       n = 2 * s; 
       continue; 
      } 
      ++n; 
      if (mVec[n] < rT) { 
       T tmp = mVec[n]; 
       mVec[n] = rT; 
       rT = tmp; 
       s = n; 
       n = 2 * s; 
       continue; 
      } 
      break; 
     } 
    } 
    size_t size; 
    vector<T> mVec; 
}; 

typedef fast_priority_queue<int> MyQueue; 

void testMyPriorityQueue() 
{ 
    srand(0); 
    MyQueue q; 

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

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


int main(int,char**) 
{ 
    clock_t t1 = clock(); 
    testMyPriorityQueue(); 
    clock_t t2 = clock(); 
    testMap(); 
    clock_t t3 = clock(); 
    testPriorityQueue(); 
    clock_t t4 = clock(); 

    cout << "fast_priority_queue: " << t2 - t1 << endl; 
    cout << "std::multiset: " << t3 - t2 << endl; 
    cout << "std::priority_queue: " << t4 - t3 << endl; 
} 

当G ++ 4.1.2标志编译：-O3在64位Linux这给了我：

fast_priority_queue: 260000 
std::multiset: 620000 
std::priority_queue: 490000