This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using push , then removes them using pop . It measures the average time for push as a function of the number of values.
(The test was executed with priority_queue_text_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 show the results for the native priority queues and pb_ds 's priority queues in g++, msvc++, and local, respectively; Figures NBRG, NBRM, and NBRL show the results for the native priority queues and pb_ds's pairing 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:
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:
These results are very similar to Priority Queue Text push Timing Test. As stated there, pairing heaps (priority_queue with Tag = pairing_heap_tag) are most suited for push and pop sequences of non-primitive types such as strings. Observing these two tests, one can note that a pairing heap outperforms the others in terms of push operations, but equals binary heaps (priority_queue with Tag = binary_heap_tag) if the number of push and pop operations is equal. As the number of pop operations is at most equal to the number of push operations, pairing heaps are better in this case. See Priority Queue Random Integer push and pop Timing Test for a case which is different.
Priority-Queue Performance Tests::Observations discusses this further and summarizes.