My Project
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

Key Extractor Concept

A model of the Key Extractor concept must:

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