The STXXL sorter container combines the two functions of runs_creator and runs_merger from the stream packages into a two-phase container. As a result, the STXXL sorter implements a external memory k-way merge sort to sort large amounts of data.
Before using a STXXL sorter, we initially have to define and then to instantiate a sorter object. Two template parameters are required to define a stxxl::sorter. ValueType defines the type of the contained objects (must be a POD with no references to internal memory) and CompareType is the type of comparison object used for sorting the runs (see example below). BlockSize and AllocStr are optional (see stxxl::sorter for additional information). The more straightforward of the two sorter constructors expects the comparator object and memory_to_use (bytes) in ram for sorted runs as parameters.
The comparator class may look as follows. The operator() is needed to compare two given elements a and b. CompareType must also provide a min_value() method, that returns the value of type ValueType that is smaller than any element of the queue x, i.e. CompareType(CompareType.min_value(),x) is always true as well as a max_value() method that works equivalent:
Note that CompareType must define strict weak ordering.
The sorter container know two different kind of states - the input state and a output state. Insertion of elements are only allowed when the sorter is in the input state. After sorting is called, the container enters the output state and inserting elements is disallowed.
Inserting elements is possible into the sorter container by calling the push() function:
Sorting all elements a sorter container is holding, call sort():
After calling sort, the items ca be read in sorted order using the operator*(), using operator++() to advance to the next item and empty() to check for the end:
To determine the size (i.e. the number of elements) of a sorter container, call size():
To check if the sorter is empty, call empty() which returns true in case:
(See examples/containers/sorter1.cpp for the sourcecode of the following example).
See examples/containers/sorter2.cpp for the sourcecode of a more comprehensive example.