Stxxl  1.3.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__)
 Sort records with integer keys.
template<typename ExtIterator_ >
void ksort (ExtIterator_ first_, ExtIterator_ last_, unsigned_type M__)
 Sort records with integer keys.
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.
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)
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)
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)
 Sort records comparison-based.
template<typename ExtIterator_ >
void stable_ksort (ExtIterator_ first, ExtIterator_ last, unsigned_type M)
 Sort records with integer keys.
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) 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:

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:
_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_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
keyobjkey 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:
firstbegin of the range to shuffle
lastend 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
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:
firstbegin of the range to shuffle
lastend of the range to shuffle
randrandom number generator object (functor)
Mnumber 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:
firstbegin of the range to shuffle
lastend 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 
)

Sort records comparison-based.

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

template<typename ExtIterator_ >
void stable_ksort ( ExtIterator_  first,
ExtIterator_  last,
unsigned_type  M 
)

Sort records with integer keys.

Parameters:
firstobject of model of ext_random_access_iterator concept
lastobject of model of ext_random_access_iterator concept
Mamount 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().