STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Algorithms

Algorithms with STL-compatible interface. More...

+ Collaboration diagram for Algorithms:

Namespaces

 stxxl::ksort_local
 
 stxxl::sort_local
 
 stxxl::stable_ksort_local
 

Classes

struct  stxxl::ksort_defaultkey< RecordType >
 

Functions

template<typename ExtIterator , typename EqualityComparable >
ExtIterator stxxl::find (ExtIterator begin, ExtIterator end, const EqualityComparable &value, int_type nbuffers=0)
 External equivalent of std::find, see stxxl::find. More...
 
template<typename ExtIterator , typename UnaryFunction >
UnaryFunction stxxl::for_each (ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
 External equivalent of std::for_each, see stxxl::for_each. More...
 
template<typename ExtIterator , typename UnaryFunction >
UnaryFunction stxxl::for_each_m (ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
 External equivalent of std::for_each (mutating), see stxxl::for_each_m (mutating). More...
 
template<typename ExtIterator , typename Generator >
void stxxl::generate (ExtIterator begin, ExtIterator end, Generator generator, int_type nbuffers=0)
 External equivalent of std::generate, see stxxl::generate. More...
 
template<typename ExtIterator , typename KeyExtractor >
void stxxl::ksort (ExtIterator first, ExtIterator last, KeyExtractor keyobj, unsigned_type M)
 Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys. More...
 
template<typename ExtIterator >
void stxxl::ksort (ExtIterator first, ExtIterator last, unsigned_type M)
 Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys. More...
 
template<typename ExtIterator , typename RandomNumberGenerator , unsigned BlockSize, unsigned PageSize, typename AllocStrategy >
void stxxl::random_shuffle (ExtIterator first, ExtIterator last, RandomNumberGenerator &rand, unsigned_type M, AllocStrategy AS=STXXL_DEFAULT_ALLOC_STRATEGY())
 External equivalent of std::random_shuffle. More...
 
template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize, typename RandomNumberGenerator >
void stxxl::random_shuffle (stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > first, stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > last, RandomNumberGenerator &rand, unsigned_type M)
 External equivalent of std::random_shuffle (specialization for stxxl::vector) More...
 
template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize>
void stxxl::random_shuffle (stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > first, stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > last, unsigned_type M)
 External equivalent of std::random_shuffle (specialization for stxxl::vector) More...
 
template<typename ExtIterator , typename StrictWeakOrdering >
void stxxl::sort (ExtIterator first, ExtIterator last, StrictWeakOrdering cmp, unsigned_type M)
 Sort records comparison-based, see stxxl::sort -- Sorting Comparison-Based. More...
 
template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >
void stxxl::sort (RandomAccessIterator begin, RandomAccessIterator end, CmpType cmp, unsigned_type MemSize, AllocStr AS)
 Sorts range of any random access iterators externally. More...
 
template<typename ExtIterator >
void stxxl::stable_ksort (ExtIterator first, ExtIterator last, unsigned_type M)
 Sort records with integer keys. More...
 

Detailed Description

Algorithms with STL-compatible interface.

Function Documentation

template<typename ExtIterator , typename EqualityComparable >
ExtIterator stxxl::find ( ExtIterator  begin,
ExtIterator  end,
const EqualityComparable &  value,
int_type  nbuffers = 0 
)

External equivalent of std::find, see stxxl::find.

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists. To overlap I/O and computation nbuffers are used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

Remarks
The implementation exploits STXXL buffered streams (computation and I/O overlapped).
Parameters
beginobject of model of ext_random_access_iterator concept
endobject of model of ext_random_access_iterator concept
valuevalue that is equality comparable to the ExtIterator's value type
nbuffersnumber of buffers (blocks) for internal use (should be at least 2*D)
Returns
first iterator i in the range [begin,end) such that *( i ) == value, if no such exists then end

Definition at line 289 of file scan.h.

Referenced by stxxl::request_queue_impl_1q::cancel_request(), stxxl::request_queue_impl_qwqr::cancel_request(), stxxl::linuxaio_queue::cancel_request(), stxxl::hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::count(), stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::count(), stxxl::hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::equal_range(), and stxxl::prefetch_pool< BlockType >::poll().

template<typename ExtIterator , typename UnaryFunction >
UnaryFunction stxxl::for_each ( ExtIterator  begin,
ExtIterator  end,
UnaryFunction  functor,
int_type  nbuffers = 0 
)

External equivalent of std::for_each, see stxxl::for_each.

stxxl::for_each applies the function object functor to each element in the range [first, last); functor's return value, if any, is ignored. Applications are performed in forward order, i.e. from first to last. stxxl::for_each returns the function object after it has been applied to each element. To overlap I/O and computation nbuffers used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

Remarks
The implementation exploits STXXL buffered streams (computation and I/O overlapped).
Parameters
beginobject of model of ext_random_access_iterator concept
endobject of model of ext_random_access_iterator concept
functorfunction object of model of std::UnaryFunction concept
nbuffersnumber of buffers (blocks) for internal use (should be at least 2*D )
Returns
function object functor after it has been applied to the each element of the given range
Warning
nested stxxl::for_each are not supported
Examples:
examples/algo/phonebills.cpp.

Definition at line 50 of file scan.h.

Referenced by stxxl::request_with_waiters::notify_waiters().

template<typename ExtIterator , typename UnaryFunction >
UnaryFunction stxxl::for_each_m ( ExtIterator  begin,
ExtIterator  end,
UnaryFunction  functor,
int_type  nbuffers = 0 
)

External equivalent of std::for_each (mutating), see stxxl::for_each_m (mutating).

stxxl::for_each_m applies the function object functor to each element in the range [first, last); functor's return value, if any, is ignored. Applications are performed in forward order, i.e. from first to last. stxxl::for_each_m returns the function object after it has been applied to each element. To overlap I/O and computation nbuffers are used (a value at least 2D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

Remarks
The implementation exploits STXXL buffered streams (computation and I/O overlapped)
Parameters
beginobject of model of ext_random_access_iterator concept
endobject of model of ext_random_access_iterator concept
functorobject of model of std::UnaryFunction concept
nbuffersnumber of buffers (blocks) for internal use (should be at least 2*D )
Returns
function object functor after it has been applied to the each element of the given range
Warning
nested stxxl::for_each_m are not supported

Definition at line 125 of file scan.h.

References stxxl::buf_ostream< BlockType, BidIteratorType >::flush().

template<typename ExtIterator , typename Generator >
void stxxl::generate ( ExtIterator  begin,
ExtIterator  end,
Generator  generator,
int_type  nbuffers = 0 
)

External equivalent of std::generate, see stxxl::generate.

Generate assigns the result of invoking generator, a function object that takes no arguments, to each element in the range [first, last). To overlap I/O and computation nbuffers are used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

Remarks
The implementation exploits STXXL buffered streams (computation and I/O overlapped).
Parameters
beginobject of model of ext_random_access_iterator concept
endobject of model of ext_random_access_iterator concept
generatorfunction object of model of std::generator concept
nbuffersnumber of buffers (blocks) for internal use (should be at least 2*D, or zero for automaticl 2*D)
Examples:
examples/applications/skew3.cpp.

Definition at line 207 of file scan.h.

template<typename ExtIterator , typename KeyExtractor >
void stxxl::ksort ( ExtIterator  first,
ExtIterator  last,
KeyExtractor  keyobj,
unsigned_type  M 
)

Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys.

stxxl::ksort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort and stxxl::sort, stxxl::ksort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::ksort.

The two versions of stxxl::ksort differ in how they define whether one element is less than another. The first version assumes that the elements have key() member function that returns an integral key (32 or 64 bit), as well as the minimum and the maximum element values. The second version compares objects extracting the keys using keyobj object, that is in turn provides min and max element values.

The sorter's internal memory consumption is bounded by M bytes.

Parameters
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
keyobjkey extractor object
Mamount of memory for internal use (in bytes)
Examples:
examples/algo/sort_file.cpp.

Definition at line 725 of file ksort.h.

References stxxl::block_manager::delete_block(), stxxl::is_sorted(), stxxl::ksort_local::ksort_blocks(), stxxl::block_manager::new_block(), stxxl::stl_in_memory_sort(), STXXL_ASSERT, and stxxl::wait_all().

Referenced by stxxl::ksort().

template<typename ExtIterator >
void stxxl::ksort ( ExtIterator  first,
ExtIterator  last,
unsigned_type  M 
)

Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys.

stxxl::ksort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort and stxxl::sort, stxxl::ksort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::ksort.

Parameters
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
Mamount of buffers for internal use
Remarks
Order in the result is non-stable

Definition at line 1072 of file ksort.h.

References stxxl::ksort().

template<typename ExtIterator , typename RandomNumberGenerator , unsigned BlockSize, unsigned PageSize, typename AllocStrategy >
void stxxl::random_shuffle ( ExtIterator  first,
ExtIterator  last,
RandomNumberGenerator &  rand,
unsigned_type  M,
AllocStrategy  AS = STXXL_DEFAULT_ALLOC_STRATEGY() 
)

External equivalent of std::random_shuffle.

Parameters
firstbegin of the range to shuffle
lastend of the range to shuffle
randrandom number generator object (functor)
Mnumber of bytes for internal use
ASparallel disk allocation strategy
  • BlockSize size of the block to use for external memory data structures
  • PageSize page size in blocks to use for external memory data structures

Definition at line 45 of file random_shuffle.h.

References stxxl::external, stxxl::grow_shrink2, stxxl::read_write_pool< BlockType >::resize_prefetch(), stxxl::read_write_pool< BlockType >::resize_write(), stxxl::stream::streamify(), STXXL_ERRMSG, STXXL_STATIC_ASSERT, stxxl::STXXL_UNUSED(), and STXXL_VERBOSE1.

Referenced by stxxl::RC::init(), stxxl::interleaved_RC::interleaved_RC(), and stxxl::random_shuffle().

template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize, typename RandomNumberGenerator >
void stxxl::random_shuffle ( stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >  first,
stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >  last,
RandomNumberGenerator &  rand,
unsigned_type  M 
)

External equivalent of std::random_shuffle (specialization for stxxl::vector)

Parameters
firstbegin of the range to shuffle
lastend of the range to shuffle
randrandom number generator object (functor)
Mnumber of bytes for internal use

Definition at line 192 of file random_shuffle.h.

References stxxl::external, stxxl::buf_ostream< BlockType, BidIteratorType >::flush(), stxxl::grow_shrink2, stxxl::random_shuffle(), stxxl::read_write_pool< BlockType >::resize_prefetch(), stxxl::read_write_pool< BlockType >::resize_write(), STXXL_ERRMSG, and STXXL_VERBOSE1.

template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize>
void stxxl::random_shuffle ( stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >  first,
stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >  last,
unsigned_type  M 
)
inline

External equivalent of std::random_shuffle (specialization for stxxl::vector)

Parameters
firstbegin of the range to shuffle
lastend of the range to shuffle
Mnumber of bytes for internal use

Definition at line 369 of file random_shuffle.h.

References stxxl::random_shuffle().

template<typename ExtIterator , typename StrictWeakOrdering >
void stxxl::sort ( ExtIterator  first,
ExtIterator  last,
StrictWeakOrdering  cmp,
unsigned_type  M 
)

Sort records comparison-based, see stxxl::sort -- Sorting Comparison-Based.

stxxl::sort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort, stxxl::sort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::sort.

The order is defined by the cmp parameter. The sorter's internal memory consumption is bounded by M bytes.

Parameters
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
cmpcomparison object of StrictWeakOrdering Comparison Concept
Mamount of memory for internal use (in bytes)
Examples:
examples/algo/phonebills.cpp, examples/algo/phonebills_genlog.cpp, and examples/algo/sort_file.cpp.

Definition at line 676 of file sort.h.

References stxxl::block_manager::delete_block(), stxxl::is_sorted(), stxxl::block_manager::new_block(), stxxl::sort_local::sort_blocks(), stxxl::sort_memory_usage_factor(), stxxl::stl_in_memory_sort(), and stxxl::sort_helper::verify_sentinel_strict_weak_ordering().

Referenced by stxxl::cleanup(), stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::compute_result(), stxxl::sort_local::create_runs(), stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_array_internal(), stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heap(), stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heaps(), stxxl::parallel_priority_queue< ValueType, CompareType, AllocStrategy, BlockSize, DefaultMemSize, MaxItems >::flush_insertion_heaps_with_limit(), stxxl::parallel::multiseq_partition(), stxxl::parallel::multiseq_selection(), stxxl::parallel::parallel_multiway_merge_sampling_splitting(), stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::rewind(), stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sort(), stxxl::stream::basic_runs_creator< stream::use_push< ValueType >, cmp_type, BlockSize, alloc_strategy_type >::sort_run(), stxxl::stream::runs_creator< use_push< ValueType >, CompareType, BlockSize, AllocStr >::sort_run(), stxxl::priority_queue_local::internal_priority_queue< value_type, std::vector< value_type >, comparator_type >::sort_to(), and stxxl::stl_in_memory_sort().

template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >
void stxxl::sort ( RandomAccessIterator  begin,
RandomAccessIterator  end,
CmpType  cmp,
unsigned_type  MemSize,
AllocStr  AS 
)

Sorts range of any random access iterators externally.

Parameters
beginiterator pointing to the first element of the range
enditerator pointing to the last+1 element of the range
cmpcomparison object
MemSizememory to use for sorting (in bytes)
ASallocation strategy

The BlockSize template parameter defines the block size to use (in bytes)

Warning
Slower than External Iterator Sort

Definition at line 1642 of file sort_stream.h.

References stxxl::stream::materialize(), and stxxl::STXXL_UNUSED().

template<typename ExtIterator >
void stxxl::stable_ksort ( ExtIterator  first,
ExtIterator  last,
unsigned_type  M 
)

Sort records with integer keys.

Parameters
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
Mamount of memory for internal use (in bytes)
Remarks
Elements must provide a method key() which returns the integer key.
Not yet fully implemented, it assumes that the keys are uniformly distributed between [0,std::numeric_limits<key_type>::max().
Examples:
examples/algo/sort_file.cpp.

Definition at line 221 of file stable_ksort.h.

References stxxl::classify(), stxxl::classify_block(), stxxl::config::disks_number(), stxxl::stable_ksort_local::distribute(), stxxl::div_ceil(), stxxl::exclusive_prefix_sum(), stxxl::ilog2_ceil(), stxxl::ilog2_floor(), stxxl::l1sort(), STXXL_ERRMSG, STXXL_L2_SIZE, stxxl::STXXL_MAX(), STXXL_MSG, STXXL_VERBOSE, STXXL_VERBOSE_STABLE_KSORT, and stxxl::timestamp().