Public Types |
| enum | { block_size = BlockSize
} |
| typedef ValueType | value_type |
| typedef CompareType | cmp_type |
| typedef AllocStrategy | alloc_strategy_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
|
typedef stream::runs_merger
< typename
runs_creator_type::sorted_runs_type,
cmp_type, alloc_strategy_type > | runs_merger_type |
| | corresponding runs merger type
|
Public Member Functions |
| | sorter (const cmp_type &cmp, unsigned_type memory_to_use) |
| | Constructor allocation memory_to_use bytes in ram for sorted runs.
|
| | sorter (const cmp_type &cmp, unsigned_type creator_memory_to_use, unsigned_type merger_memory_to_use) |
| void | clear () |
| | Remove all items and return to input state.
|
| void | push (const value_type &val) |
| | Push another item (only callable during input state).
|
| void | finish () |
| | Finish push input state and deallocate input buffer.
|
| void | finish_clear () |
| | Deallocate buffers and clear result.
|
| unsigned_type | size () const |
| | Number of items pushed or items remaining to be read.
|
| void | sort () |
| | Switch to output state, rewind() in case the output was already sorted.
|
| void | sort (unsigned_type merger_memory_to_use) |
| | Switch to output state, rewind() in case the output was already sorted.
|
| void | sort_reuse () |
| | Switch to output state, rewind() in case the output was already sorted.
|
| void | rewind () |
| | Rewind output stream to beginning.
|
| void | set_creator_memory_to_use (unsigned_type creator_memory_to_use) |
| | Change runs_creator memory usage.
|
| void | set_merger_memory_to_use (unsigned_type merger_memory_to_use) |
| | Change runs_merger memory usage.
|
| bool | empty () const |
| | Standard stream method.
|
| const value_type & | operator* () const |
| | Standard stream method.
|
| const value_type * | operator-> () const |
| | Standard stream method.
|
| sorter & | operator++ () |
| | Standard stream method (preincrement operator)
|
Protected Types |
| enum | { STATE_INPUT,
STATE_OUTPUT
} |
| | current state of sorter More...
|
Protected Attributes |
| enum stxxl::sorter:: { ... } | m_state |
| | current state of sorter
|
| runs_creator_type | m_runs_creator |
| runs_merger_type | m_runs_merger |
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: 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.
- Template Parameters:
-
| ValueType | type of the contained objects (POD with no references to internal memory) |
| CompareType | type of comparison object used for sorting the runs |
| BlockSize | size of the external memory block in bytes, default is STXXL_DEFAULT_BLOCK_SIZE(ValTp) |
| AllocStr | parallel disk allocation strategy, default is STXXL_DEFAULT_ALLOC_STRATEGY |
- Examples:
- containers/test_sorter.cpp.
Definition at line 58 of file sorter.h.
template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
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 161 of file sorter.h.
template<typename ValueType , typename CompareType , unsigned BlockSize = STXXL_DEFAULT_BLOCK_SIZE(ValueType), class AllocStrategy = STXXL_DEFAULT_ALLOC_STRATEGY>
1.7.6.1
