My Project
Loading...
Searching...
No Matches
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

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