Почему в этом случае очередь STL с приоритетом _не намного быстрее, чем мультисет?

Я сравниваю производительность очереди STL (g++ )с приоритетом _и обнаружил, что 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 занимает 54% всего ЦП testPriorityQueue занимает 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> >

Похоже, что эта функция вызывается из вызова pop ().

Что именно делает эта функция? Есть ли способ избежать этого, используя другой контейнер или распределитель?