Algorithms with STL-compatible interface. More...

Collaboration diagram for Algorithms:

Namespaces
	stxxl::ksort_local

	stxxl::sort_local

	stxxl::stable_ksort_local

Classes
struct	stxxl::ksort_defaultkey< RecordType >

Functions
template<typename ExtIterator , typename EqualityComparable >
ExtIterator	stxxl::find (ExtIterator begin, ExtIterator end, const EqualityComparable &value, int_type nbuffers=0)
	External equivalent of std::find, see stxxl::find. More...

template<typename ExtIterator , typename UnaryFunction >
UnaryFunction	stxxl::for_each (ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
	External equivalent of std::for_each, see stxxl::for_each. More...

template<typename ExtIterator , typename UnaryFunction >
UnaryFunction	stxxl::for_each_m (ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
	External equivalent of std::for_each (mutating), see stxxl::for_each_m (mutating). More...

template<typename ExtIterator , typename Generator >
void	stxxl::generate (ExtIterator begin, ExtIterator end, Generator generator, int_type nbuffers=0)
	External equivalent of std::generate, see stxxl::generate. More...

template<typename ExtIterator , typename KeyExtractor >
void	stxxl::ksort (ExtIterator first, ExtIterator last, KeyExtractor keyobj, unsigned_type M)
	Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys. More...

template<typename ExtIterator >
void	stxxl::ksort (ExtIterator first, ExtIterator last, unsigned_type M)
	Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys. More...

template<typename ExtIterator , typename RandomNumberGenerator , unsigned BlockSize, unsigned PageSize, typename AllocStrategy >
void	stxxl::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 Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize, typename RandomNumberGenerator >
void	stxxl::random_shuffle (stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > first, stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > last, RandomNumberGenerator &rand, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector) More...

template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize>
void	stxxl::random_shuffle (stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > first, stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize > last, unsigned_type M)
	External equivalent of std::random_shuffle (specialization for stxxl::vector) More...

template<typename ExtIterator , typename StrictWeakOrdering >
void	stxxl::sort (ExtIterator first, ExtIterator last, StrictWeakOrdering cmp, unsigned_type M)
	Sort records comparison-based, see stxxl::sort -- Sorting Comparison-Based. More...

template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >
void	stxxl::sort (RandomAccessIterator begin, RandomAccessIterator end, CmpType cmp, unsigned_type MemSize, AllocStr AS)
	Sorts range of any random access iterators externally. More...

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

Detailed Description

Algorithms with STL-compatible interface.

Function Documentation

template<typename ExtIterator , typename EqualityComparable >

ExtIterator stxxl::find	(	ExtIterator	begin,
		ExtIterator	end,
		const EqualityComparable &	value,
		int_type	nbuffers = `0`
	)

External equivalent of std::find, see stxxl::find.

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists. To overlap I/O and computation nbuffers are used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

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

Definition at line 289 of file scan.h.

Referenced by stxxl::request_queue_impl_1q::cancel_request(), stxxl::request_queue_impl_qwqr::cancel_request(), stxxl::linuxaio_queue::cancel_request(), stxxl::hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::count(), stxxl::btree::btree< KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy >::count(), and stxxl::hash_map::hash_map< KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock, AllocType >::equal_range().

template<typename ExtIterator , typename UnaryFunction >

UnaryFunction stxxl::for_each	(	ExtIterator	begin,
		ExtIterator	end,
		UnaryFunction	functor,
		int_type	nbuffers = `0`
	)

External equivalent of std::for_each, see stxxl::for_each.

stxxl::for_each applies the function object functor to each element in the range [first, last); functor's return value, if any, is ignored. Applications are performed in forward order, i.e. from first to last. stxxl::for_each returns the function object after it has been applied to each element. To overlap I/O and computation nbuffers used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

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

Examples:: examples/algo/phonebills.cpp.

Definition at line 50 of file scan.h.

Referenced by stxxl::request_with_waiters::notify_waiters().

template<typename ExtIterator , typename UnaryFunction >

UnaryFunction stxxl::for_each_m	(	ExtIterator	begin,
		ExtIterator	end,
		UnaryFunction	functor,
		int_type	nbuffers = `0`
	)

External equivalent of std::for_each (mutating), see stxxl::for_each_m (mutating).

stxxl::for_each_m applies the function object functor to each element in the range [first, last); functor's return value, if any, is ignored. Applications are performed in forward order, i.e. from first to last. stxxl::for_each_m returns the function object after it has been applied to each element. To overlap I/O and computation nbuffers are used (a value at least 2D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

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	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_m are not supported

Definition at line 125 of file scan.h.

References stxxl::buf_ostream< BlockType, BidIteratorType >::flush().

template<typename ExtIterator , typename Generator >

void stxxl::generate	(	ExtIterator	begin,
		ExtIterator	end,
		Generator	generator,
		int_type	nbuffers = `0`
	)

External equivalent of std::generate, see stxxl::generate.

Generate assigns the result of invoking generator, a function object that takes no arguments, to each element in the range [first, last). To overlap I/O and computation nbuffers are used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

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 2D, or zero for automaticl 2D)

Examples:: examples/applications/skew3.cpp.

Definition at line 207 of file scan.h.

template<typename ExtIterator , typename KeyExtractor >

void stxxl::ksort	(	ExtIterator	first,
		ExtIterator	last,
		KeyExtractor	keyobj,
		unsigned_type	M
	)

Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys.

stxxl::ksort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort and stxxl::sort, stxxl::ksort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::ksort.

The two versions of stxxl::ksort differ in how they define whether one element is less than another. The first version assumes that the elements have key() member function that returns an integral key (32 or 64 bit), as well as the minimum and the maximum element values. The second version compares objects extracting the keys using keyobj object, that is in turn provides min and max element values.

The sorter's internal memory consumption is bounded by M bytes.

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)

Examples:: examples/algo/sort_file.cpp.

Definition at line 725 of file ksort.h.

References stxxl::block_manager::delete_block(), stxxl::is_sorted(), stxxl::ksort_local::ksort_blocks(), stxxl::block_manager::new_block(), stxxl::stl_in_memory_sort(), STXXL_ASSERT, and stxxl::wait_all().

Referenced by stxxl::ksort().

template<typename ExtIterator >

void stxxl::ksort	(	ExtIterator	first,
		ExtIterator	last,
		unsigned_type	M
	)

Sort records with integer keys, see stxxl::ksort -- Sorting Integer Keys.

stxxl::ksort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort and stxxl::sort, stxxl::ksort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::ksort.

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

Definition at line 1072 of file ksort.h.

References stxxl::ksort().

template<typename ExtIterator , typename RandomNumberGenerator , unsigned BlockSize, unsigned PageSize, typename AllocStrategy >

void stxxl::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

Definition at line 45 of file random_shuffle.h.

References stxxl::external, stxxl::grow_shrink2, stxxl::read_write_pool< BlockType >::resize_prefetch(), stxxl::read_write_pool< BlockType >::resize_write(), stxxl::stream::streamify(), STXXL_ERRMSG, STXXL_STATIC_ASSERT, stxxl::STXXL_UNUSED(), and STXXL_VERBOSE1.

Referenced by stxxl::RC::init(), stxxl::interleaved_RC::interleaved_RC(), and stxxl::random_shuffle().

template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize, typename RandomNumberGenerator >

void stxxl::random_shuffle	(	stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >	first,
		stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, 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

Definition at line 192 of file random_shuffle.h.

References stxxl::external, stxxl::buf_ostream< BlockType, BidIteratorType >::flush(), stxxl::grow_shrink2, stxxl::random_shuffle(), stxxl::read_write_pool< BlockType >::resize_prefetch(), stxxl::read_write_pool< BlockType >::resize_write(), STXXL_ERRMSG, and STXXL_VERBOSE1.

template<typename Type , typename AllocStrategy , typename SizeType , typename DiffType , unsigned BlockSize, typename PageType , unsigned PageSize>

void stxxl::random_shuffle	(	stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, PageSize >	first,
		stxxl::vector_iterator< Type, AllocStrategy, SizeType, DiffType, BlockSize, PageType, 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

Definition at line 368 of file random_shuffle.h.

References stxxl::random_shuffle().

template<typename ExtIterator , typename StrictWeakOrdering >

void stxxl::sort	(	ExtIterator	first,
		ExtIterator	last,
		StrictWeakOrdering	cmp,
		unsigned_type	M
	)

Sort records comparison-based, see stxxl::sort -- Sorting Comparison-Based.

stxxl::sort sorts the elements in [first, last) into ascending order, meaning that if i and j are any two valid iterators in [first, last) such that i precedes j, then *j is not less than *i. Note: as std::sort, stxxl::sort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by stxxl::sort.

The order is defined by the cmp parameter. The sorter's internal memory consumption is bounded by M bytes.

Parameters

first	object of model of `ext_random_access_iterator` concept
last	object of model of `ext_random_access_iterator` concept
cmp	comparison object of StrictWeakOrdering Comparison Concept
M	amount of memory for internal use (in bytes)

Examples:: examples/algo/phonebills.cpp, examples/algo/phonebills_genlog.cpp, and examples/algo/sort_file.cpp.

Definition at line 674 of file sort.h.

References stxxl::block_manager::delete_block(), stxxl::is_sorted(), stxxl::block_manager::new_block(), stxxl::sort_local::sort_blocks(), stxxl::sort_memory_usage_factor(), stxxl::stl_in_memory_sort(), and stxxl::sort_helper::verify_sentinel_strict_weak_ordering().

Referenced by stxxl::cleanup(), stxxl::stream::basic_runs_creator< Input, CompareType, BlockSize, AllocStr >::compute_result(), stxxl::sort_local::create_runs(), stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::rewind(), stxxl::sorter< ValueType, CompareType, BlockSize, AllocStrategy >::sort(), stxxl::stream::basic_runs_creator< stream::use_push< ValueType >, cmp_type, BlockSize, alloc_strategy_type >::sort_run(), stxxl::stream::runs_creator< use_push< ValueType >, CompareType, BlockSize, AllocStr >::sort_run(), stxxl::priority_queue_local::internal_priority_queue< value_type, std::vector< value_type >, comparator_type >::sort_to(), and stxxl::stl_in_memory_sort().

template<unsigned BlockSize, class RandomAccessIterator , class CmpType , class AllocStr >

void stxxl::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

Definition at line 1640 of file sort_stream.h.

References stxxl::stream::materialize(), and stxxl::STXXL_UNUSED().

template<typename ExtIterator >

void stxxl::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:: examples/algo/sort_file.cpp.

Definition at line 221 of file stable_ksort.h.

References stxxl::classify(), stxxl::classify_block(), stxxl::config::disks_number(), stxxl::stable_ksort_local::distribute(), stxxl::div_ceil(), stxxl::exclusive_prefix_sum(), stxxl::ilog2_ceil(), stxxl::ilog2_floor(), stxxl::l1sort(), STXXL_ERRMSG, STXXL_L2_SIZE, stxxl::STXXL_MAX(), STXXL_MSG, STXXL_VERBOSE, STXXL_VERBOSE_STABLE_KSORT, and stxxl::timestamp().

Namespaces

Classes

Functions

Detailed Description

Function Documentation