This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container, then pops them until only one is left in the container. It measures the memory use as a function of the number of values pushed to the container.
(The test was executed with priority_queue_text_pop_mem_usage_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.
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:
The priority queue implementations (excluding the STL's) use memory proportionally to the number of values they hold: node-based implementations (e.g., a pairing heap) do so naturally; pb_ds's binary heap de-allocates memory when a certain lower threshold is exceeded.
Note from Priority Queue Text push and pop Timing Test and Priority Queue Random Integer push and pop Timing Test that this does not impede performance compared to the STL's priority queues.
(See Hash-Based Erase Memory Use Test for a similar phenomenon regarding priority queues.)