Collaboration diagram for Algorithms:

Namespaces
	ksort_local

	sort_local

	stable_ksort_local

Functions
template<typename ExtIterator_ , typename KeyExtractor_ >
void	ksort (ExtIterator_ first_, ExtIterator_ last_, KeyExtractor_ keyobj, unsigned_type M__)
	Sort records with integer keys. More...

template<typename ExtIterator_ >
void	ksort (ExtIterator_ first_, ExtIterator_ last_, unsigned_type M__)
	Sort records with integer keys. More...

template<typename ExtIterator_ , typename RandomNumberGenerator_ , unsigned BlockSize_, unsigned PageSize_, typename AllocStrategy_ >
void	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 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_ > last, RandomNumberGenerator_ &rand, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector) More...

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_ > last, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector) More...

template<typename _ExtIterator , typename _UnaryFunction >
_UnaryFunction	for_each (_ExtIterator _begin, _ExtIterator _end, _UnaryFunction _functor, int_type nbuffers)
	External equivalent of std::for_each. More...

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) More...

template<typename _ExtIterator , typename _Generator >
void	generate (_ExtIterator _begin, _ExtIterator _end, _Generator _generator, int_type nbuffers)
	External equivalent of std::generate. More...

template<typename _ExtIterator , typename _EqualityComparable >
_ExtIterator	find (_ExtIterator _begin, _ExtIterator _end, const _EqualityComparable &_value, int_type nbuffers)
	External equivalent of std::find. More...

template<typename ExtIterator_ , typename StrictWeakOrdering_ >
void	sort (ExtIterator_ first, ExtIterator_ last, StrictWeakOrdering_ cmp, unsigned_type M)
	Sort records comparison-based. More...

template<typename ExtIterator_ >
void	stable_ksort (ExtIterator_ first, ExtIterator_ last, unsigned_type M)
	Sort records with integer keys. More...

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

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

template<typename ExtIterator_ , typename KeyExtractor_ >

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

References block_manager::delete_block(), block_manager::new_block(), request_interface::wait(), and wait_all().

Referenced by ksort().

template<typename ExtIterator_ >

void 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).

References ksort().

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

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

References stream::streamify().

Referenced by 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_ >	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

References 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_ >	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

References random_shuffle().

template<typename ExtIterator_ , typename StrictWeakOrdering_ >

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

References block_manager::delete_block(), block_manager::new_block(), and request_interface::wait().

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

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_ >

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

References config::disks_number(), and request_interface::wait().

Namespaces

Functions

Detailed Description

Key extractor concept

Comparison concept

Function Documentation