Collaboration diagram for Algorithms:

Namespaces
namespace	ksort_local
namespace	sort_local
namespace	stable_ksort_local
Functions
template<typename ExtIterator_ , typename KeyExtractor_ >
void	ksort (ExtIterator_ first_, ExtIterator_ last_, KeyExtractor_ keyobj, unsigned_type M__)
	External sorting routine for records with keys.
template<typename ExtIterator_ >
void	ksort (ExtIterator_ first_, ExtIterator_ last_, unsigned_type M__)
	External sorting routine for records with keys.
template<typename Tp_ , typename AllocStrategy_ , typename SzTp_ , typename DiffTp_ , unsigned BlockSize_, typename PgTp_ , unsigned PageSize_, typename RandomNumberGenerator_ >
void	random_shuffle (stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > first, stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > beyond, RandomNumberGenerator_ &rand, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector).
template<typename ExtIterator_ , typename RandomNumberGenerator_ , unsigned BlockSize_, unsigned PageSize_, typename AllocStrategy_ >
void	random_shuffle (ExtIterator_ first, ExtIterator_ beyond, 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_>
void	random_shuffle (stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > first, stxxl::vector_iterator< Tp_, AllocStrategy_, SzTp_, DiffTp_, BlockSize_, PgTp_, PageSize_ > beyond, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector).
template<typename _ExtIterator , typename _UnaryFunction >
_UnaryFunction	for_each (_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
	External equivalent of std::for_each.
template<typename _ExtIterator , typename _UnaryFunction >
_UnaryFunction	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	generate (_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers)
	External equivalent of std::generate.
template<typename _ExtIterator , typename _EqualityComparable >
_ExtIterator	find (_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable &_value, int_type nbuffers)
	External equivalent of std::find.
template<typename ExtIterator_ , typename StrictWeakOrdering_ >
void	sort (ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp, unsigned_type M)
	External sorting routine for records that allow only comparisons.
template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >
void	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 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 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.

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

Function Documentation

template<typename _ExtIterator , typename _EqualityComparable >

_ExtIterator 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.

template<typename _ExtIterator , typename _UnaryFunction >

_UnaryFunction 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

template<typename _ExtIterator , typename _UnaryFunction >

_UnaryFunction 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.

template<typename _ExtIterator , typename _Generator >

void 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_random_shuffle.cpp, algo/test_scan.cpp, containers/test_vector.cpp, and stream/test_sorted_runs.cpp.

template<typename ExtIterator_ >

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

External sorting routine for records with 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:: Implements external merge sort described in [Dementiev & Sanders'03]; 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).

References ksort().

template<typename ExtIterator_ , typename KeyExtractor_ >

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

External sorting routine for records with 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:: Implements external merge sort described in [Dementiev & Sanders'03]; Order in the result is non-stable

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

References block_manager::delete_block(), block_manager::new_blocks(), and wait_all().

Referenced by ksort().

template<typename ExtIterator_ , typename RandomNumberGenerator_ , unsigned BlockSize_, unsigned PageSize_, typename AllocStrategy_ >

void random_shuffle	(	ExtIterator_	first,
		ExtIterator_	beyond,
		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
	beyond	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

References random_shuffle(), and stream::streamify().

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

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

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

Parameters:

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

References random_shuffle().

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

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

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

Parameters:

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

Examples:: algo/test_random_shuffle.cpp.

References stream::streamify().

Referenced by random_shuffle().

template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >

void 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

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

template<typename ExtIterator_ , typename StrictWeakOrdering_ >

void sort	(	ExtIterator_	first,
		ExtIterator_	last,
		StrictWeakOrdering_	cmp,
		unsigned_type	M
	)

External sorting routine for records that allow only comparisons.

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/test_sort.cpp, stream/test_sorted_runs.cpp, and stream/test_stream.cpp.

References block_manager::delete_block(), and block_manager::new_blocks().

Referenced by priority_queue_local::internal_priority_queue< value_type, std::vector< value_type >, comparator_type >::sort_to().

Algorithms [STL-user layer]

Namespaces

Functions

Detailed Description

Key extractor concept

Function Documentation

Algorithms
[STL-user layer]