Collaboration diagram for Algorithms:

Classes
struct	stxxl::ksort_defaultkey< record_type >
Namespaces
namespace	stxxl::ksort_local
namespace	stxxl::sort_local
namespace	stxxl::stable_ksort_local
Functions
template<typename ExtIterator_ , typename KeyExtractor_ >
void	stxxl::ksort (ExtIterator_ first_, ExtIterator_ last_, KeyExtractor_ keyobj, unsigned_type M__)
	Sort records with integer keys.
template<typename ExtIterator_ >
void	stxxl::ksort (ExtIterator_ first_, ExtIterator_ last_, unsigned_type M__)
	Sort records with integer keys.
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.
template<typename Tp_ , typename AllocStrategy_ , typename SzTp_ , typename DiffTp_ , unsigned BlockSize_, typename PgTp_ , unsigned PageSize_, typename RandomNumberGenerator_ >
void	stxxl::random_shuffle (stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > first, stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > last, RandomNumberGenerator_ &rand, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector)
template<typename Tp_ , typename AllocStrategy_ , typename SzTp_ , typename DiffTp_ , unsigned BlockSize_, typename PgTp_ , unsigned PageSize_>
void	stxxl::random_shuffle (stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > first, stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > last, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector)
template<typename _ExtIterator , typename _UnaryFunction >
_UnaryFunction	stxxl::for_each (_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
	External equivalent of std::for_each.
template<typename _ExtIterator , typename _UnaryFunction >
_UnaryFunction	stxxl::for_each_m (_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
	External equivalent of std::for_each (mutating)
template<typename _ExtIterator , typename _Generator >
void	stxxl::generate (_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers)
	External equivalent of std::generate.
template<typename _ExtIterator , typename _EqualityComparable >
_ExtIterator	stxxl::find (_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable &_value, int_type nbuffers)
	External equivalent of std::find.
template<typename ExtIterator_ , typename StrictWeakOrdering_ >
void	stxxl::sort (ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp, unsigned_type M)
	Sort records comparison-based.
template<typename ExtIterator_ >
void	stxxl::stable_ksort (ExtIterator_ first, ExtIterator_ last, unsigned_type M)
	Sort records with integer keys.
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.

Detailed Description

Algorithms with STL-compatible interface

Key extractor concept

Model of Key extractor concept must:

define type key_type ,
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

Example: 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)()); };
   };

Comparison concept

Model of Comparison concept must:

provide operator(a,b) that returns comparison result of two user types, must define strict weak ordering
provide max_value method that returns a value that is strictly greater than all other objects of user type,
provide min_value method that returns a value that is strictly less than all other objects of user type,
Note: when using unsigned integral types as key in user types, the value 0 cannot be used as a key value of the data to be sorted because it would conflict with the sentinel value returned by min_value

Example: comparator class my_less_int

   struct my_less_int
   {
    bool operator() (int a, int b) const
    {
        return a < b;
    }
    int min_value() const { return std::numeric_limits<int>::min(); };
    int max_value() const { return std::numeric_limits<int>::max(); };
   };

Example: comparator class my_less, could be instantiated as e.g. my_less<int> , my_less<unsigned long> , ...

   template <typename Tp>
   struct my_less
   {
    typedef Tp value_type;
    bool operator() (const value_type & a, const value_type & b) const
    {
        return a < b;
    }
    value_type min_value() const { return std::numeric_limits<value_type>::min(); };
    value_type max_value() const { return std::numeric_limits<value_type>::max(); };
   };

Function Documentation

template<typename _ExtIterator , typename _EqualityComparable >

_ExtIterator stxxl::find	(	_ExtIterator	_begin,
		_ExtIterator	_end,
		const _EqualityComparable &	_value,
		int_type	nbuffers
	)

External equivalent of std::find.

Remarks:: The implementation exploits <stxxl> buffered streams (computation and I/O overlapped)

Parameters:

_begin	object of model of `ext_random_access_iterator` concept
_end	object of model of `ext_random_access_iterator` concept
_value	value that is equality comparable to the _ExtIterator's value type
nbuffers	number 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

Examples:: algo/test_scan.cpp.

Definition at line 215 of file scan.h.

Referenced by stxxl::request_queue_impl_1q::cancel_request(), stxxl::request_queue_impl_qwqr::cancel_request(), stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::count(), and main().

template<typename _ExtIterator , typename _UnaryFunction >

_UnaryFunction stxxl::for_each	(	_ExtIterator	_begin,
		_ExtIterator	_end,
		_UnaryFunction	_functor,
		int_type	nbuffers
	)

External equivalent of std::for_each.

Remarks:: The implementation exploits <stxxl> buffered streams (computation and I/O overlapped)

Parameters:

_begin	object of model of `ext_random_access_iterator` concept
_end	object of model of `ext_random_access_iterator` concept
_functor	function object of model of `std::UnaryFunction` concept
nbuffers	number 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

Definition at line 37 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
	)

External equivalent of std::for_each (mutating)

Remarks:: The implementation exploits <stxxl> buffered streams (computation and I/O overlapped)

Parameters:

_begin	object of model of `ext_random_access_iterator` concept
_end	object of model of `ext_random_access_iterator` concept
_functor
nbuffers	number 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

Examples:: algo/test_scan.cpp.

Definition at line 91 of file scan.h.

Referenced by main().

template<typename _ExtIterator , typename _Generator >

void stxxl::generate	(	_ExtIterator	_begin,
		_ExtIterator	_end,
		_Generator	_generator,
		int_type	nbuffers
	)

External equivalent of std::generate.

Remarks:: The implementation exploits <stxxl> buffered streams (computation and I/O overlapped)

Parameters:

_begin	object of model of `ext_random_access_iterator` concept
_end	object of model of `ext_random_access_iterator` concept
_generator	function object of model of `std::Generator` concept
nbuffers	number of buffers (blocks) for internal use (should be at least 2*D )

Examples:: algo/test_parallel_sort.cpp, algo/test_random_shuffle.cpp, algo/test_scan.cpp, containers/test_vector.cpp, and stream/test_sorted_runs.cpp.

Definition at line 150 of file scan.h.

Referenced by long_test(), main(), and test().

template<typename ExtIterator_ , typename KeyExtractor_ >

void stxxl::ksort	(	ExtIterator_	first_,
		ExtIterator_	last_,
		KeyExtractor_	keyobj,
		unsigned_type	M__
	)

Sort records with integer keys.

Parameters:

first_	object of model of `ext_random_access_iterator` concept
last_	object of model of `ext_random_access_iterator` concept
keyobj	key extractor object
M__	amount of memory for internal use (in bytes)

Remarks:: Order in the result is non-stable

Examples:: algo/sort_file.cpp, and algo/test_ksort.cpp.

Definition at line 743 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(), std::swap(), stxxl::request_interface::wait(), and stxxl::wait_all().

Referenced by stxxl::ksort(), main(), and test().

template<typename ExtIterator_ >

void stxxl::ksort	(	ExtIterator_	first_,
		ExtIterator_	last_,
		unsigned_type	M__
	)

Sort records with integer keys.

Parameters:

first_	object of model of `ext_random_access_iterator` concept
last_	object of model of `ext_random_access_iterator` concept
M__	amount of buffers for internal use

Remarks:: Order in the result is non-stable

Record's type must:

provide max_value method that returns an object that is greater than all other objects of user type ,
provide min_value method that returns an object that is less than all other objects of user type ,
operator < that must define strict weak ordering on record's values (see what it is).

Definition at line 1097 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:

first	begin of the range to shuffle
last	end of the range to shuffle
rand	random number generator object (functor)
M	number of bytes for internal use
AS	parallel 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

Examples:: algo/test_random_shuffle.cpp.

Definition at line 49 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(), and STXXL_STATIC_ASSERT.

Referenced by stxxl::RC::init(), stxxl::interleaved_RC::interleaved_RC(), long_test(), main(), stxxl::random_shuffle(), run_test(), and short_test().

template<typename Tp_ , typename AllocStrategy_ , typename SzTp_ , typename DiffTp_ , unsigned BlockSize_, typename PgTp_ , unsigned PageSize_, typename RandomNumberGenerator_ >

void stxxl::random_shuffle	(	stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ >	first,
		stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ >	last,
		RandomNumberGenerator_ &	rand,
		unsigned_type	M
	)

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

Parameters:

first	begin of the range to shuffle
last	end of the range to shuffle
rand	random number generator object (functor)
M	number of bytes for internal use

Definition at line 196 of file random_shuffle.h.

References stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::bid(), stxxl::vector_iterator< Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_ >::block_offset(), stxxl::external, stxxl::grow_shrink2, stxxl::random_shuffle(), stxxl::read_write_pool< BlockType >::resize_prefetch(), and stxxl::read_write_pool< BlockType >::resize_write().

template<typename Tp_ , typename AllocStrategy_ , typename SzTp_ , typename DiffTp_ , unsigned BlockSize_, typename PgTp_ , unsigned PageSize_>

void stxxl::random_shuffle	(	stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ >	first,
		stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ >	last,
		unsigned_type	M
	)		`[inline]`

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

Parameters:

first	begin of the range to shuffle
last	end of the range to shuffle
M	number of bytes for internal use

Definition at line 367 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.

Parameters:

first	object of model of `ext_random_access_iterator` concept
last	object of model of `ext_random_access_iterator` concept
cmp	comparison object
M	amount of memory for internal use (in bytes)

Remarks:: Implements external merge sort described in [Dementiev & Sanders'03]; non-stable

Examples:: algo/sort_file.cpp, algo/test_bad_cmp.cpp, algo/test_parallel_sort.cpp, algo/test_sort.cpp, stream/test_sorted_runs.cpp, and stream/test_stream.cpp.

Definition at line 702 of file sort.h.

References stxxl::block_manager::delete_block(), stxxl::is_sorted(), stxxl::block_manager::new_block(), stxxl::sort_local::sort_blocks(), stxxl::stl_in_memory_sort(), std::swap(), stxxl::sort_helper::verify_sentinel_strict_weak_ordering(), and stxxl::request_interface::wait().

Referenced by stxxl::cleanup(), stxxl::stream::basic_runs_creator< Input_, CompareType_, BlockSize_, AllocStr_ >::compute_result(), stxxl::sort_local::create_runs(), linear_sort_normal(), main(), 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(), stxxl::stl_in_memory_sort(), and test().

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:

begin	iterator pointing to the first element of the range
end	iterator pointing to the last+1 element of the range
cmp	comparison object
MemSize	memory to use for sorting (in bytes)
AS	allocation strategy

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

Warning:: Slower than External Iterator Sort

Definition at line 1607 of file sort_stream.h.

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

template<typename ExtIterator_ >

void stxxl::stable_ksort	(	ExtIterator_	first,
		ExtIterator_	last,
		unsigned_type	M
	)

Sort records with integer keys.

Parameters:

first	object of model of `ext_random_access_iterator` concept
last	object of model of `ext_random_access_iterator` concept
M	amount 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:: algo/sort_file.cpp, and algo/test_stable_ksort.cpp.

Definition at line 224 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(), init(), stxxl::l1sort(), stxxl::log2_ceil(), stxxl::log2_floor(), STXXL_L2_SIZE, stxxl::STXXL_MAX(), STXXL_MSG, STXXL_VERBOSE_STABLE_KSORT, std::swap(), stxxl::timestamp(), and stxxl::request_interface::wait().

Referenced by main(), and test().

Classes

Namespaces

Functions

Detailed Description

Key extractor concept

Comparison concept

Function Documentation