STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy > Class Template Reference

Detailed Description

template<typename ValueType, typename CompareType, unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
class stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >

External sorter container.
Introduction to sorter container: see STXXL Sorter tutorial.
Design and Internals of sorter container: see Sorter.

External Sorter: use stream package objects to keep a sorted container.

This sorter container combines the two functions of runs_creator and runs_merger from the stream packages into a two-phase container.

In the first phase the container is filled with unordered items via push(), which are presorted internally into runs of size M. When the internal memory overflows a runs is written to external memory in blocks of block_size.

When sort() is called the container enters the output phase and push() is disallowed. After calling sort() the items can be read in sorted order using operator*() to get the top item, operator++() to advance to the next one and empty() to check for end of stream. This is exactly the stream interface.

In the output phase the sorter can be returned to the beginning of the stream using rewind() and everything is read again in sorted order.

Using clear() the object can be reset into input state and all items are destroyed.

Added in STXXL 1.4

Template Parameters
ValueTypetype of the contained objects (POD with no references to internal memory)
CompareTypetype of comparison object used for sorting the runs
BlockSizesize of the external memory block in bytes, default is STXXL_DEFAULT_BLOCK_SIZE(ValTp)
AllocStrparallel disk allocation strategy, default is STXXL_DEFAULT_ALLOC_STRATEGY
Examples:
examples/applications/skew3.cpp, examples/containers/sorter1.cpp, examples/containers/sorter2.cpp, and examples/stream/stream1.cpp.

Definition at line 64 of file sorter.h.

+ Inheritance diagram for stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >:
+ Collaboration diagram for stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >:

Public Types

enum  { block_size = BlockSize }
 
typedef AllocStrategy alloc_strategy_type
 
typedef CompareType cmp_type
 
typedef stream::runs_creator
< stream::use_push< ValueType >
, cmp_type, block_size,
alloc_strategy_type
runs_creator_type
 runs creator type with push() method More...
 
typedef stream::runs_merger
< typename
runs_creator_type::sorted_runs_type,
cmp_type, alloc_strategy_type
runs_merger_type
 corresponding runs merger type More...
 
typedef runs_merger_type::size_type size_type
 size type More...
 
typedef ValueType value_type
 

Public Member Functions

void set_merger_memory_to_use (unsigned_type merger_memory_to_use)
 Change runs_merger memory usage. More...
 
Constructors
 sorter (const cmp_type &cmp, unsigned_type memory_to_use)
 Constructor allocation memory_to_use bytes in ram for sorted runs. More...
 
 sorter (const cmp_type &cmp, unsigned_type creator_memory_to_use, unsigned_type merger_memory_to_use)
 Constructor variant with differently sizes runs_creator and runs_merger. More...
 
Modifiers
void clear ()
 Remove all items and return to input state. More...
 
void push (const value_type &val)
 Push another item (only callable during input state). More...
 
void sort ()
 Switch to output state, rewind() in case the output was already sorted. More...
 
void sort (unsigned_type merger_memory_to_use)
 Switch to output state, rewind() in case the output was already sorted. More...
 
Modus
void finish ()
 Finish push input state and deallocate input buffer. More...
 
void finish_clear ()
 Deallocate buffers and clear result. More...
 
void sort_reuse ()
 Switch to output state, rewind() in case the output was already sorted. More...
 
void rewind ()
 Rewind output stream to beginning. More...
 
Capacity
size_type size () const
 Number of items pushed or items remaining to be read. More...
 
bool empty () const
 Standard stream method. More...
 
Operators
const value_typeoperator* () const
 Standard stream method. More...
 
const value_typeoperator-> () const
 Standard stream method. More...
 
sorteroperator++ ()
 Standard stream method (preincrement operator) More...
 

Protected Types

enum  { STATE_INPUT, STATE_OUTPUT }
 current state of sorter More...
 

Protected Attributes

runs_creator_type m_runs_creator
 runs creator object holding all items More...
 
runs_merger_type m_runs_merger
 runs merger reading items when in STATE_OUTPUT More...
 
enum stxxl::sorter:: { ... }  m_state
 current state of sorter More...
 

Additional Inherited Members

- Private Member Functions inherited from stxxl::noncopyable
 noncopyable ()
 

Member Typedef Documentation

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef AllocStrategy stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::alloc_strategy_type

Definition at line 74 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef CompareType stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::cmp_type

Definition at line 70 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef stream::runs_creator<stream::use_push<ValueType>, cmp_type, block_size, alloc_strategy_type> stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::runs_creator_type

runs creator type with push() method

Definition at line 80 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef stream::runs_merger<typename runs_creator_type::sorted_runs_type, cmp_type, alloc_strategy_type> stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::runs_merger_type

corresponding runs merger type

Definition at line 84 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef runs_merger_type::size_type stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::size_type

size type

Definition at line 87 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
typedef ValueType stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::value_type

Definition at line 69 of file sorter.h.

Member Enumeration Documentation

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
anonymous enum
Enumerator
block_size 

Definition at line 71 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
anonymous enum
protected

current state of sorter

Enumerator
STATE_INPUT 
STATE_OUTPUT 

Definition at line 93 of file sorter.h.

Constructor & Destructor Documentation

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sorter ( const cmp_type cmp,
unsigned_type  memory_to_use 
)
inline

Constructor allocation memory_to_use bytes in ram for sorted runs.

Definition at line 106 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sorter ( const cmp_type cmp,
unsigned_type  creator_memory_to_use,
unsigned_type  merger_memory_to_use 
)
inline

Constructor variant with differently sizes runs_creator and runs_merger.

Definition at line 113 of file sorter.h.

Member Function Documentation

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::clear ( )
inline

Remove all items and return to input state.

Definition at line 126 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
bool stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::empty ( ) const
inline

Standard stream method.

Definition at line 242 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::finish ( )
inline

Finish push input state and deallocate input buffer.

Definition at line 148 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::finish_clear ( )
inline

Deallocate buffers and clear result.

Definition at line 159 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
const value_type& stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::operator* ( ) const
inline

Standard stream method.

Definition at line 254 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
sorter& stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::operator++ ( )
inline

Standard stream method (preincrement operator)

Definition at line 267 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
const value_type* stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::operator-> ( ) const
inline

Standard stream method.

Definition at line 261 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::push ( const value_type val)
inline

Push another item (only callable during input state).

Definition at line 136 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::rewind ( )
inline

Rewind output stream to beginning.

Definition at line 210 of file sorter.h.

References stxxl::sort().

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::set_merger_memory_to_use ( unsigned_type  merger_memory_to_use)
inline

Change runs_merger memory usage.

Definition at line 223 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
size_type stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::size ( ) const
inline

Number of items pushed or items remaining to be read.

Definition at line 234 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sort ( )
inline

Switch to output state, rewind() in case the output was already sorted.

Definition at line 176 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sort ( unsigned_type  merger_memory_to_use)
inline

Switch to output state, rewind() in case the output was already sorted.

Definition at line 189 of file sorter.h.

References stxxl::sort().

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
void stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sort_reuse ( )
inline

Switch to output state, rewind() in case the output was already sorted.

Definition at line 201 of file sorter.h.

Member Data Documentation

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
runs_creator_type stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::m_runs_creator
protected

runs creator object holding all items

Definition at line 96 of file sorter.h.

template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
runs_merger_type stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::m_runs_merger
protected

runs merger reading items when in STATE_OUTPUT

Definition at line 99 of file sorter.h.

enum { ... } stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::m_state

current state of sorter


The documentation for this class was generated from the following file: