- 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;
stxxl::ksort(V.begin(), V.end(), 512*1024*1024);