stxxl::sort is an external memory equivalent to STL std::sort. The design and implementation of the algorithm is described in detail in [DemSan03].
Prototype
template < typename ExtIterator,
typename StrictWeakOrdering
>
void sort ( ExtIterator first,
ExtIterator last,
StrictWeakOrdering cmp,
unsigned_type M
)
Description
Requirements on Types
ExtIterator is a model of External Random Access Iterator (In STXXL currently only stxxl::vector provides iterators that are models of External Random Access Iterator.).
ExtIterator's value type is convertible to StrictWeakOrdering's argument type.
StrictWeakOrdering Comparison Concept
Model of StrictWeakOrdering Comparison concept must:
provide operator(a,b) that returns comparison result of two user types, must define strict weak ordering
provide max_value method that returns a value that is strictly greater than all other objects of user type,
provide min_value method that returns a value that is strictly less than all other objects of user type,
Note: when using unsigned integral types as key in user types, the value 0 cannot be used as a key value of the data to be sorted because it would conflict with the sentinel value returned by min_value
Note, that according to the stxxl::sort requirements min_value() and max_value()can not be present in the input sequence.
Examples
A comparator class for integers: my_less_int.
struct my_less_int
{
bool operator() (int a, int b) const
{
return a < b;
}
int min_value() const { return std::numeric_limits<int>::min(); };
int max_value() const { return std::numeric_limits<int>::max(); };
};
A comparator class my_less, that could be instantiated as e.g. my_less<int>, my_less<unsigned long>, etc.
template <typename ValueType>
struct my_less
{
typedef ValueType value_type;
bool operator() (const value_type & a, const value_type & b) const
stxxl::sort chooses the block size (parameter B) equal to the block size of the container, the last and first iterators pointing to (e.g. stxxl::vector's block size).
The second term in the I/O complexity accounts for the merge phases of the external memory sorting algorithm [DemSan03]. Avoiding multiple merge phases speeds up the sorting. In practice one should choose the block size B$of the container to be sorted such that there is only one merge phase needed: . This is possible for and . But still this restriction gives a freedom to choose a variety of blocks sizes. The study [DemSan03] has shown that optimal B for sorting lies in the range . With such choice of the parameters the stxxl::sort always performs I/Os.
Internal Memory Consumption
The stxxl::sort consumes slightly more than M bytes of internal memory.
External Memory Consumption
The stxxl::sort is not in-place. It requires about N bytes of external memory to store the sorted runs during the sorting process [DemSan03]. After the sorting this memory is freed.
Example
struct MyCmp: public std::less<int> // ascending order
STXXL gives an ability to automatically check the order in the output of STXXL sorters and intermediate results of sorting (the order and a meta information in the sorted runs). The check is switched on if the source codes and the library are compiled with the option -DSTXXL_CHECK_ORDER_IN_SORTS and the option -DNDEBUG is not used. For details see the compiler.make file in the STXXL tar ball. Note, that the checking routines require more internal work as well as additional I/Os to read the sorted runs. Therefore for the final non-debug version of a user application on should switch this option off.
This checker checks the stxxl::sort, stxxl::ksort, and the pipelined sorter.