Stxxl  1.2.1
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
_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
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
_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
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
_beginobject of model of ext_random_access_iterator concept
_endobject of model of ext_random_access_iterator concept
_functor
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
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
_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 )
Examples:
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__ 
)

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
keyobjkey 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(), request::wait(), and wait_all().

Referenced by ksort().

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 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
firstbegin of the range to shuffle
beyondend of the range to shuffle
randrandom number generator object (functor)
Mnumber of bytes for internal use
Examples:
algo/test_random_shuffle.cpp.

References stream::streamify().

Referenced by random_shuffle().

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
firstbegin of the range to shuffle
beyondend 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

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
firstbegin of the range to shuffle
beyondend of the range to shuffle
Mnumber of bytes for internal use

References random_shuffle().

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
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
cmpcomparison object
Mamount 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(), block_manager::new_blocks(), and request::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
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

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