Namespaces | Functions

Algorithms
[STL-user layer]

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:

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