stxxl::ksort -- Sorting Integer Keys

Author

Roman Dementiev (2006)

stxxl::ksort is a specialization of external memory sorting optimized for records having integer keys.

Prototype

template < typename ExtIterator >
void ksort ( ExtIterator   first,
             ExtIterator   last,
             unsigned_type M
           )

template < typename ExtIterator, typename KeyExtractor >
void ksort ( ExtIterator   first,
             ExtIterator   last,
             KeyExtractor  keyobj,
             unsigned_type M
           )

Description

stxxl::ksort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort and stxxl::sort, stxxl::ksort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::ksort.

The two versions of stxxl::ksort differ in how they define whether one element is less than another. The first version assumes that the elements have key() member function that returns an integral key (32 or 64 bit), as well as the minimum and the maximum element values. The second version compares objects extracting the keys using keyobj object, that is in turn provides min and max element values.

The sorter's internal memory consumption is bounded by M bytes.

Parameters

first	object of model of ext_random_access_iterator concept
last	object of model of ext_random_access_iterator concept
keyobj	key extractor object
M	amount of memory for internal use (in bytes)

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 is mutable.
• KeyExtractor must implement operator() that extracts the key of an element and provide min and max values for the elements in the input, see Key Extractor Concept.
• ExtIterator's value type is convertible to KeyExtractor's argument type.
• ExtIterator's value type has a typedef key_type.
• For the first version of stxxl::ksort ExtIterator's value type must have a key() function that returns the key value of the element, and the min_value() and max_value() member functions that return minimum and maximum element values respectively.
  Example:

  struct MyType
  {
      typedef unsigned long long key_type;
      key_type m_key;
      char m_data[32];
      MyType() {}
      MyType(key_type k) : m_key(k) {}
      key_type key() { return m_key; }
      MyType min_value() const
      { return MyType( std::numeric_limits<key_type>::min() ); }
      MyType max_value() const
      { return MyType( std::numeric_limits<key_type>::max() ); }
  };

Key Extractor Concept

A model of the Key Extractor concept must:

• define type key_type for the type of the keys.
• provide operator() that returns key value of an object of user type.
• provide max_value method that returns a value that is strictly greater than all other objects of user type in respect to the key obtained by this key extractor,
• provide min_value method that returns a value that is strictly less than all other objects of user type in respect to the key obtained by this key extractor,
• operator >, operator <, operator == and operator != on type key_type must be defined.
• Note: when using unsigned integral types as key, the value 0 cannot be used as a key value 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 key extractor object for ordering elements having 64 bit integer keys:

struct MyType
{
    typedef unsigned long long key_type;
    key_type m_key;
    char m_data[32];
    MyType() {}
    MyType(key_type k) : m_key(k) {}
};
struct GetKey
{
    typedef MyType::key_type key_type;
    key_type operator() (const MyType & obj)
    { return obj.m_key; }
    MyType min_value() const
    { return MyType( std::numeric_limits<key_type>::min() ); }
    MyType max_value() const
    { return MyType( std::numeric_limits<key_type>::max() ); }
};

A key extractor class GetWeight, that extracts weight from an Edge:

struct Edge
{
    unsigned src, dest, weight;
    Edge(unsigned s, unsigned d, unsigned w) : src(s), dest(d), weight(w) {}
};

struct GetWeight
{
    typedef unsigned key_type;
    key_type operator() (const Edge & e) const
    {
        return e.weight;
    }
    Edge min_value() const { return Edge(0, 0, std::numeric_limits<key_type>::min()); }
    Edge max_value() const { return Edge(0, 0, std::numeric_limits<key_type>::max()); }
};

Preconditions

The same as for stxxl::sort.

Complexity

The same as for stxxl::sort.

Internal Memory Consumption

The same as for stxxl::sort.

External Memory Consumption

The same as for stxxl::sort.

Example

struct MyType
{
    typedef unsigned long long key_type;
    key_type m_key;
    char m_data[32];
    MyType() {}
    MyType(key_type k) : m_key(k) {}
    key_type key() { return obj.m_key; }
    static MyType min_value() const
    { return MyType( std::numeric_limits<key_type>::min() ); }
    static MyType max_value() const
    { return MyType( std::numeric_limits<key_type>::max()); }
};

typedef stxxl::VECTOR_GENERATOR<MyType>::result vec_type;

vec_type V;
// ... fill here the vector with some values

// Sort in ascending order use 512 MiB of main memory
stxxl::ksort(V.begin(), V.end(), 512*1024*1024);
// sorted