Basically, the priority queue provides insertion of new elements as well as access and deletion of the element on top. The invariant guarantees that the top element is the largest (or smallest if desired) of all inserted elements identified by comparison realized by the customizable comparator class.
To manage the configuration of the priority queue type, we use the generator template stxxl::PRIORITY_QUEUE_GENERATOR. This generator template expects a value type (which is an integer in our example), a class which we name Comparator(a,b) to compare two given elements a and b, a internal memory limit in bytes and the number of elements to be stored (in 1024 units). See section stxxl::PRIORITY_QUEUE_GENERATOR for additional configuration parameters and information.
Thus the definition may look as follows:
The ComparatorGreater(a,b) class is needed to compare two given elements a and b and has to be defined by hand (and before the priority queue definition above):
The compare-operator () of two elements a and b returns true, if a is larger than b, otherwise false. Consequently, this priority queue serves it's smallest element on top . The additional min_value() function ensures that Comparator(min_value(),x) is true for each and every x.
iLikewise the minimum-on-top Comparator, we can easily define a largest element on top Comparator which stores the the largest contained integer on top as well:
Note that CompareType must define a strict weak ordering. These and some other details are available in the Notes part of stxxl::PRIORITY_QUEUE_GENERATOR
To create a STXXL priority queue instance, a resizable buffered writing and prefetched reading pool (to overlap I/O and computation) is needed:
To insert a new element into the priority queue, call push():
The priority queue only allows to access the top element, which is the smallest or largest element (depending on the used comparator class) of all inserted elements. Calling top() on an instance returns this element:
Erasing elements is only possible on the top of the priority queue by calling pop(). Note that after removing the element on top, the priority queue still holds the above mentioned property.
To determine the size (i.e. the number of elements) of an instance, call size():
To check if the priority queue is empty, call empty() which returns true in case:
(See examples/containers/pqueue1.cpp for the sourcecode of the following example).
See examples/containers/pqueue2.cpp for the sourcecode of another small example.