This test inserts a number of values with i.i.d. integer keys into a container using push , then removes them using pop . It measures the average time for push and pop as a function of the number of values.
(The test was executed with priority_queue_random_int_push_pop_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)
The test checks the effect of different underlying data structures (see Design::Priority Queues::Implementations).
Figures NPG, NPM, and NPL shows the results for the native priority queues and pb_ds 's priority queues in g++, msvc++, and local, respectively.
In the above figure, the names in the legends have the following meaning:
In the above figure, the names in the legends have the following meaning:
Binary heaps are the most suited for sequences of push and pop operations of primitive types (e.g. ints). This is explained in Priority Queue Random Int push Timing Test . (See Priority Queue Text push Timing Test for the case of primitive types.)
At first glance it seems that the STL's vector-based priority queue is approximately on par with pb_ds's corresponding priority queue. There are two differences however:
Priority-Queue Performance Tests::Observations discusses this further and summarizes.