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