This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using push . It measures the average time for push as a function of the number of values pushed.
(The test was executed with priority_queue_text_push_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 shows the results for the binary-heap based native priority queues and pb_ds's pairing-heap 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:
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:
Pairing heaps (priority_queue with Tag = pairing_heap_tag) are the most suited for sequences of push and pop operations of non-primitive types (e.g. std::strings). (see also Priority Queue Text push and pop Timing Test.) They are less constrained than binomial heaps, e.g., and since they are node-based, they outperform binary heaps. (See Priority Queue Random Integer push Timing Test for the case of primitive types.)
The STL's priority queues do not seem to perform well in this case: the std::vector implementation needs to perform a logarithmic sequence of string operations for each operation, and the deque implementation is possibly hampered by its need to manipulate a relatively-complex type (deques support a O(1) push_front, even though it is not used by std::priority_queue.)
Priority-Queue Performance Tests::Observations discusses this further and summarizes.