__gnu_parallel(3cxx) | __gnu_parallel(3cxx) |
NAME¶
__gnu_parallel -SYNOPSIS¶
Classes¶
struct _Settings
Typedefs¶
typedef unsigned short bin_index
Enumerations¶
enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel }
Functions¶
template<typename Size > Size __log2 (Size n)
Variables¶
static const int lcas_t_bits
Detailed Description¶
GNU parallel code for public use.Typedef Documentation¶
typedef unsigned short __gnu_parallel::bin_index¶
Type to hold the index of a bin. Since many variables of this type are allocated, it should be chosen as small as possible. Definition at line 47 of file random_shuffle.h.typedef short __gnu_parallel::int16¶
Integer Types. 16-bit signed integer. Definition at line 114 of file types.h.typedef int __gnu_parallel::int32¶
32-bit signed integer. Definition at line 120 of file types.h.typedef long long __gnu_parallel::int64¶
64-bit signed integer. Definition at line 126 of file types.h.typedef int64 __gnu_parallel::lcas_t¶
Longest compare-and-swappable integer type on this platform. Definition at line 145 of file types.h.typedef uint64 __gnu_parallel::sequence_index_t¶
Unsigned integer to index elements. The total number of elements for each algorithm must fit into this type. Definition at line 135 of file types.h.typedef uint16 __gnu_parallel::thread_index_t¶
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. Definition at line 141 of file types.h.typedef unsigned short __gnu_parallel::uint16¶
16-bit unsigned integer. Definition at line 117 of file types.h.typedef unsigned int __gnu_parallel::uint32¶
32-bit unsigned integer. Definition at line 123 of file types.h.typedef unsigned long long __gnu_parallel::uint64¶
64-bit unsigned integer. Definition at line 129 of file types.h.Enumeration Type Documentation¶
enum __gnu_parallel::_AlgorithmStrategy¶
Strategies for run-time algorithm selection: Definition at line 65 of file types.h.enum __gnu_parallel::_FindAlgorithm¶
Find algorithms: Definition at line 104 of file types.h.enum __gnu_parallel::_MultiwayMergeAlgorithm¶
Merging algorithms: Definition at line 83 of file types.h.enum __gnu_parallel::_Parallelism¶
Run-time equivalents for the compile-time tags. Enumerator:- sequential
- Not parallel.
- parallel_unbalanced
- Parallel unbalanced (equal-sized chunks).
- parallel_balanced
- Parallel balanced (work-stealing).
- parallel_omp_loop
- Parallel with OpenMP dynamic load-balancing.
- parallel_omp_loop_static
- Parallel with OpenMP static load-balancing.
- parallel_taskqueue
- Parallel with OpenMP taskqueue construct.
enum __gnu_parallel::_PartialSumAlgorithm¶
Partial sum algorithms: recursive, linear. Definition at line 89 of file types.h.enum __gnu_parallel::_SortAlgorithm¶
Sorting algorithms: Definition at line 74 of file types.h.enum __gnu_parallel::_SplittingAlgorithm¶
Sorting/merging algorithms: sampling, exact. Definition at line 96 of file types.h.Function Documentation¶
template<typename Size > Size __gnu_parallel::__log2 (Sizen) [inline]¶
Calculates the rounded-down logarithm of n for base 2. Parameters:n Argument.
Returns:
Returns 0 for any argument <1.
template<typename RandomAccessIterator , typename _DifferenceTp > void __gnu_parallel::calc_borders (RandomAccessIteratorelements, _DifferenceTplength, _DifferenceTp *off)¶
Precalculate advances for Knuth-Morris-Pratt algorithm. Parameters:elements Begin iterator of sequence to
search for.
length Length of sequence to search for.
advances Returned offsets.
template<typename T > bool __gnu_parallel::compare_and_swap (volatile T *ptr, Tcomparand, Treplacement) [inline]¶
Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:ptr Pointer to signed integer.
comparand Compare value.
replacement Replacement value.
bool __gnu_parallel::compare_and_swap_32 (volatile int32 *ptr, int32comparand, int32replacement) [inline]¶
Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:ptr Pointer to 32-bit signed integer.
comparand Compare value.
replacement Replacement value.
bool __gnu_parallel::compare_and_swap_64 (volatile int64 *ptr, int64comparand, int64replacement) [inline]¶
Compare *ptr and comparand. If equal, let *ptr=replacement and return true, return false otherwise. Implementation is heavily platform-dependent. Parameters:ptr Pointer to 64-bit signed integer.
comparand Compare value.
replacement Replacement value.
void __gnu_parallel::decode2 (lcas_tx, int &a, int &b) [inline]¶
Decode two integers from one __gnu_parallel::lcas_t. Parameters:x __gnu_parallel::lcas_t to
decode integers from.
a First integer, to be decoded from the most-significant lcas_t_bits/2
bits of x.
b Second integer, to be encoded in the least-significant lcas_t_bits/2
bits of x.
See Also:
encode2
template<typename RandomAccessIterator , typename _DifferenceTp > void __gnu_parallel::determine_samples (PMWMSSortingData< RandomAccessIterator > *sd, _DifferenceTpnum_samples)¶
Select samples from a sequence. Parameters:sd Pointer to algorithm data. Result
will be placed in sd->samples.
num_samples Number of samples to select.
lcas_t __gnu_parallel::encode2 (inta, intb) [inline]¶
Encode two integers into one __gnu_parallel::lcas_t. Parameters:a First integer, to be encoded in the
most-significant lcas_t_bits/2 bits.
b Second integer, to be encoded in the least-significant lcas_t_bits/2
bits.
Returns:
__gnu_parallel::lcas_t value encoding a
and b.
See Also:
decode2
template<typename difference_type , typename OutputIterator > OutputIterator __gnu_parallel::equally_split (difference_typen, thread_index_tnum_threads, OutputIterators)¶
Function to split a sequence into parts of almost equal size. The resulting sequence s of length num_threads+1 contains the splitting positions when splitting the range [0,n) into parts of almost equal size (plus minus 1). The first entry is 0, the last one n. There may result empty parts. Parameters:n Number of elements
num_threads Number of parts
s Splitters
Returns:
End of splitter sequence, i. e.
s+num_threads+1
template<typename difference_type > difference_type __gnu_parallel::equally_split_point (difference_typen, thread_index_tnum_threads, thread_index_tthread_no)¶
Function to split a sequence into parts of almost equal size. Returns the position of the splitting point between thread number thread_no (included) and thread number thread_no+1 (excluded). Parameters:n Number of elements
num_threads Number of parts
Returns:
_SplittingAlgorithm point
template<typename T > T __gnu_parallel::fetch_and_add (volatile T *ptr, Taddend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:ptr Pointer to a signed integer.
addend Value to add.
int32 __gnu_parallel::fetch_and_add_32 (volatile int32 *ptr, int32addend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:ptr Pointer to a 32-bit signed integer.
addend Value to add.
int64 __gnu_parallel::fetch_and_add_64 (volatile int64 *ptr, int64addend) [inline]¶
Add a value to a variable, atomically. Implementation is heavily platform-dependent. Parameters:ptr Pointer to a 64-bit signed integer.
addend Value to add.
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename Pred , typename Selector > std::pair<RandomAccessIterator1, RandomAccessIterator2> __gnu_parallel::find_template (RandomAccessIterator1begin1, RandomAccessIterator1end1, RandomAccessIterator2begin2, Predpred, Selectorselector) [inline]¶
Parallel std::find, switch for different algorithms. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence. Must have same length as first
sequence.
pred Find predicate.
selector Functionality (e. g. std::find_if (), std::equal(),...)
Returns:
Place of finding in both sequences.
template<typename InputIterator , typename UserOp , typename Functionality , typename Red , typename Result > UserOp __gnu_parallel::for_each_template_random_access (InputIteratorbegin, InputIteratorend, UserOpuser_op, Functionality &functionality, Redreduction, Resultreduction_start, Result &output, typename std::iterator_traits< InputIterator >::difference_typebound, _Parallelismparallelism_tag)¶
Chose the desired algorithm by evaluating parallelism_tag. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
user_op A user-specified functor (comparator, predicate, associative
operator,...)
functionality functor to 'process' an element with user_op (depends on
desired functionality, e. g. accumulate, for_each,...
reduction Reduction functor.
reduction_start Initial value for reduction.
output Output iterator.
bound Maximum number of elements processed.
parallelism_tag Parallelization method
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_ed (RandomAccessIteratorbegin, RandomAccessIteratorend, Opo, Fu &f, Redr, Resultbase, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_typebound)¶
Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. Parameters:begin Begin iterator of element
sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor, ...)
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed elements
(depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to
bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_omp_loop (RandomAccessIteratorbegin, RandomAccessIteratorend, Opo, Fu &f, Redr, Resultbase, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_typebound)¶
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. Parameters:begin Begin iterator of element
sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor, etc.).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed elements
(depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to
bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_omp_loop_static (RandomAccessIteratorbegin, RandomAccessIteratorend, Opo, Fu &f, Redr, Resultbase, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_typebound)¶
Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. Parameters:begin Begin iterator of element
sequence.
end End iterator of element sequence.
o User-supplied functor (comparator, predicate, adding functor, ...).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed elements
(depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to
bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename RandomAccessIterator , typename Op , typename Fu , typename Red , typename Result > Op __gnu_parallel::for_each_template_random_access_workstealing (RandomAccessIteratorbegin, RandomAccessIteratorend, Opop, Fu &f, Redr, Resultbase, Result &output, typename std::iterator_traits< RandomAccessIterator >::difference_typebound)¶
Work stealing algorithm for random access iterators. Uses O(1) additional memory. Synchronization at job lists is done with atomic operations. Parameters:begin Begin iterator of element
sequence.
end End iterator of element sequence.
op User-supplied functor (comparator, predicate, adding functor, ...).
f Functor to 'process' an element with op (depends on desired
functionality, e. g. for std::for_each(), ...).
r Functor to 'add' a single result to the already processed elements
(depends on functionality).
base Base value for reduction.
output Pointer to position where final result is written to
bound Maximum number of elements processed (e. g. for
std::count_n()).
Returns:
User-supplied functor (that may contain a part
of the result).
template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted (InputIteratorbegin, InputIteratorend, Comparatorcomp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() )¶
Check whether [begin, end) is sorted according to comp. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
Returns:
true if sorted, false otherwise.
template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted_failure (InputIteratorbegin, InputIteratorend, InputIterator &first_failure, Comparatorcomp = std::less<typename std::iterator_traits<InputIterator>:: value_type>() )¶
Check whether [begin, end) is sorted according to comp. Prints the position in case an unordered pair is found. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
first_failure The first failure is returned in this variable.
comp Comparator.
Returns:
true if sorted, false otherwise.
template<typename InputIterator , typename Comparator > bool __gnu_parallel::is_sorted_print_failures (InputIteratorbegin, InputIteratorend, Comparatorcomp = std::less<typename std::iterator_traits <InputIterator>::value_type>() )¶
Check whether [begin, end) is sorted according to comp. Prints all unordered pair, including the surrounding two elements. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
Returns:
true if sorted, false otherwise.
template<typename InputIterator , typename FunctorType > size_t __gnu_parallel::list_partition (const InputIteratorbegin, const InputIteratorend, InputIterator *starts, size_t *lengths, const intnum_parts, FunctorType &f, intoversampling = 0)¶
Splits a sequence given by input iterators into parts of almost equal size. The function needs only one pass over the sequence. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
starts Start iterators for the resulting parts, dimension num_parts+1.
For convenience, starts [num_parts] contains the end iterator of the sequence.
lengths Length of the resulting parts.
num_parts Number of parts to split the sequence into.
f Functor to be applied to each element by traversing it
oversampling Oversampling factor. If 0, then the partitions will differ
in at most $ rt{thrm{end} - thrm{begin}} $ elements. Otherwise, the ratio
between the longest and the shortest part is bounded by $
1/(thrm{oversampling} dot thrm{num_parts}) $.
Returns:
Length of the whole sequence.
template<typename T > const T& __gnu_parallel::max (const T &a, const T &b)¶
Equivalent to std::max. Definition at line 151 of file base.h. Referenced by multiseq_partition(), multiseq_selection(), and parallel_nth_element().template<typename RandomAccessIterator , typename Comparator > RandomAccessIterator __gnu_parallel::median_of_three_iterators (RandomAccessIteratora, RandomAccessIteratorb, RandomAccessIteratorc, Comparator &comp)¶
Compute the median of three referenced elements, according to comp. Parameters:a First iterator.
b Second iterator.
c Third iterator.
comp Comparator.
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1end1, RandomAccessIterator2 &begin2, RandomAccessIterator2end2, OutputIteratortarget, _DifferenceTpmax_length, Comparatorcomp) [inline]¶
Merge routine being able to merge only the max_length smallest elements. The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Static switch on whether to use the conditional-move variant. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge.
comp Comparator.
Returns:
Output end iterator.
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance_movc (RandomAccessIterator1 &begin1, RandomAccessIterator1end1, RandomAccessIterator2 &begin2, RandomAccessIterator2end2, OutputIteratortarget, _DifferenceTpmax_length, Comparatorcomp)¶
Merge routine being able to merge only the max_length smallest elements. The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Specially designed code should allow the compiler to generate conditional moves instead of branches. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge.
comp Comparator.
Returns:
Output end iterator.
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename OutputIterator , typename _DifferenceTp , typename Comparator > OutputIterator __gnu_parallel::merge_advance_usual (RandomAccessIterator1 &begin1, RandomAccessIterator1end1, RandomAccessIterator2 &begin2, RandomAccessIterator2end2, OutputIteratortarget, _DifferenceTpmax_length, Comparatorcomp)¶
Merge routine being able to merge only the max_length smallest elements. The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge.
comp Comparator.
Returns:
Output end iterator.
template<typename T > const T& __gnu_parallel::min (const T &a, const T &b)¶
Equivalent to std::min. Definition at line 145 of file base.h. Referenced by for_each_template_random_access_workstealing(), multiseq_partition(), multiseq_selection(), parallel_random_shuffle_drs(), parallel_sort_qs_divide(), search_template(), and sequential_random_shuffle().template<typename RanSeqs , typename RankType , typename RankIterator , typename Comparator > void __gnu_parallel::multiseq_partition (RanSeqsbegin_seqs, RanSeqsend_seqs, RankTyperank, RankIteratorbegin_offsets, Comparatorcomp = std::less< typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type:: first_type>::value_type>() )¶
Splits several sorted sequences at a certain global rank, resulting in a splitting point for each sequence. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. If there are several equal elements across the split, the ones on the left side will be chosen from sequences with smaller number. Parameters:begin_seqs Begin of the sequence of
iterator pairs.
end_seqs End of the sequence of iterator pairs.
rank The global rank to partition at.
begin_offsets A random-access sequence begin where the result will be
stored in. Each element of the sequence is an iterator that points to the
first element on the greater part of the respective sequence.
comp The ordering functor, defaults to std::less<T>.
template<typename T , typename RanSeqs , typename RankType , typename Comparator > T __gnu_parallel::multiseq_selection (RanSeqsbegin_seqs, RanSeqsend_seqs, RankTyperank, RankType &offset, Comparatorcomp = std::less<T>())¶
Selects the element at a certain global rank from several sorted sequences. The sequences are passed via a sequence of random-access iterator pairs, none of the sequences may be empty. Parameters:begin_seqs Begin of the sequence of
iterator pairs.
end_seqs End of the sequence of iterator pairs.
rank The global rank to partition at.
offset The rank of the selected element in the global subsequence of
elements equal to the selected element. If the selected element is unique,
this number is 0.
comp The ordering functor, defaults to std::less.
template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIteratorseqs_begin, RandomAccessIteratorPairIteratorseqs_end, RandomAccessIteratorOuttarget, _DifferenceTplength, Comparatorcomp, __gnu_parallel::sequential_tag)¶
Multiway Merge Frontend. Merge the sequences specified by seqs_begin and seqs_end into target. seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second entry. Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower. The first entries of the pairs (i.e. the begin iterators) will be moved forward. The output sequence has to provide enough space for all elements that are written to it. This function will merge the input sequences:- •
- not stable
- •
- parallel, depending on the input size and Settings
- •
- using sampling for splitting
- •
- not using sentinels
int sequences[10][10]; for (int i = 0; i < 10; ++i) for (int j = 0; i < 10; ++j) sequences[i][j] = j;
int out[33]; std::vector<std::pair<int*> > seqs; for (int i = 0; i < 10; ++i) { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);See Also:
stable_multiway_merge
Precondition:
All input sequences must be sorted.
Target must provide enough space to merge out length elements or the number of
elements in all sequences, whichever is smaller.
Postcondition:
[target, return value) contains merged
elements from the input sequences.
return value - target = min(length, number of elements in all sequences).
Parameters:
RandomAccessIteratorPairIterator
iterator over sequence of pairs of iterators
RandomAccessIteratorOut iterator over target sequence
_DifferenceTp difference type for the sequence
Comparator strict weak ordering type to compare elements in sequences
seqs_begin begin of sequence sequence
seqs_end end of sequence sequence
target target sequence to merge to.
comp strict weak ordering to use for element comparison.
length Maximum length to merge, possibly larger than the number of
elements available.
Returns:
end iterator of output sequence
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, _DifferenceTplength, Comparatorcomp)¶
Highly efficient 3-way merging procedure. Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into labels in C++). This works well for merging up to 4 sequences. Note that making the merging stable does not come at a performance hit. Whether the merging is done guarded or unguarded is selected by the used iterator class. Parameters:seqs_begin Begin iterator of iterator
pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, _DifferenceTplength, Comparatorcomp)¶
Highly efficient 4-way merging procedure. Merging is done with the algorithm implementation described by Peter Sanders. Basically, the idea is to minimize the number of necessary comparison after merging out an element. The implementation trick that makes this fast is that the order of the sequences is stored in the instruction pointer (translated into goto labels in C++). This works well for merging up to 4 sequences. Note that making the merging stable does not come at a performance hit. Whether the merging is done guarded or unguarded is selected by the used iterator class. Parameters:seqs_begin Begin iterator of iterator
pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void __gnu_parallel::multiway_merge_exact_splitting (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, difference_typelength, difference_typetotal_length, Comparatorcomp, std::vector< std::pair< difference_type, difference_type > > *pieces)¶
Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty. Definition at line 1181 of file multiway_merge.h. References _GLIBCXX_PARALLEL_LENGTH, std::vector< _Tp, _Alloc >::begin(), equally_split(), multiseq_partition(), and std::vector< _Tp, _Alloc >::resize(). Referenced by parallel_merge_advance().template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, _DifferenceTplength, Comparatorcomp)¶
Multi-way merging procedure for a high branching factor, guarded case. This merging variant uses a LoserTree class as selected by LT. Stability is selected through the used LoserTree class LT. At least one non-empty sequence is required. Parameters:seqs_begin Begin iterator of iterator
pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<typename UnguardedLoserTree , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTplength, Comparatorcomp)¶
Multi-way merging procedure for a high branching factor, requiring sentinels to exist. Parameters:stable The value must the same as for
the used LoserTrees.
UnguardedLoserTree Loser Tree variant to use for the unguarded merging.
GuardedLoserTree Loser Tree variant to use for the guarded merging.
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<typename LT , typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_unguarded (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTplength, Comparatorcomp)¶
Multi-way merging procedure for a high branching factor, unguarded case. Merging is done using the LoserTree class LT. Stability is selected by the used LoserTrees. Precondition:No input will run out of elements during the
merge.
Parameters:
seqs_begin Begin iterator of iterator
pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, less equal than the total number of
elements available.
Returns:
End iterator of output sequence.
template<bool stable, typename RandomAccessIteratorIterator , typename Comparator , typename difference_type > void __gnu_parallel::multiway_merge_sampling_splitting (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, difference_typelength, difference_typetotal_length, Comparatorcomp, std::vector< std::pair< difference_type, difference_type > > *pieces)¶
Sampling based splitting for parallel multiway-merge routine. Definition at line 1100 of file multiway_merge.h. References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling.template<typename RandomAccessIteratorPairIterator , typename RandomAccessIteratorOut , typename _DifferenceTp , typename Comparator > RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIteratorseqs_begin, RandomAccessIteratorPairIteratorseqs_end, RandomAccessIteratorOuttarget, _DifferenceTplength, Comparatorcomp, __gnu_parallel::sequential_tag)¶
Multiway Merge Frontend. Merge the sequences specified by seqs_begin and seqs_end into target. seqs_begin and seqs_end must point to a sequence of pairs. These pairs must contain an iterator to the beginning of a sequence in their first entry and an iterator the end of the same sequence in their second entry. Ties are broken arbitrarily. See stable_multiway_merge for a variant that breaks ties by sequence number but is slower. The first entries of the pairs (i.e. the begin iterators) will be moved forward accordingly. The output sequence has to provide enough space for all elements that are written to it. This function will merge the input sequences:- •
- not stable
- •
- parallel, depending on the input size and Settings
- •
- using sampling for splitting
- •
- using sentinels
int sequences[10][11]; for (int i = 0; i < 10; ++i) for (int j = 0; i < 11; ++j) sequences[i][j] = j; // last one is sentinel!
int out[33]; std::vector<std::pair<int*> > seqs; for (int i = 0; i < 10; ++i) { seqs.push(std::make_pair<int*>(sequences[i], sequences[i] + 10)) }
multiway_merge(seqs.begin(), seqs.end(), target, std::less<int>(), 33);Precondition:
All input sequences must be sorted.
Target must provide enough space to merge out length elements or the number of
elements in all sequences, whichever is smaller.
For each i, seqs_begin[i].second must be the end marker of the sequence, but
also reference the one more sentinel element.
Postcondition:
[target, return value) contains merged
elements from the input sequences.
return value - target = min(length, number of elements in all sequences).
See Also:
stable_multiway_merge_sentinels
Parameters:
RandomAccessIteratorPairIterator
iterator over sequence of pairs of iterators
RandomAccessIteratorOut iterator over target sequence
_DifferenceTp difference type for the sequence
Comparator strict weak ordering type to compare elements in sequences
seqs_begin begin of sequence sequence
seqs_end end of sequence sequence
target target sequence to merge to.
comp strict weak ordering to use for element comparison.
length Maximum length to merge, possibly larger than the number of
elements available.
Returns:
end iterator of output sequence
template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator< (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2) [inline]¶
Compare two elements referenced by guarded iterators. Parameters:bi1 First iterator.
bi2 Second iterator.
Returns:
True if less.
template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator< (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2) [inline]¶
Compare two elements referenced by unguarded iterators. Parameters:bi1 First iterator.
bi2 Second iterator.
Returns:
True if less.
template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator<= (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2) [inline]¶
Compare two elements referenced by guarded iterators. Parameters:bi1 First iterator.
bi2 Second iterator.
Returns:
True if less equal.
template<typename RandomAccessIterator , typename Comparator > bool __gnu_parallel::operator<= (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2) [inline]¶
Compare two elements referenced by unguarded iterators. Parameters:bi1 First iterator.
bi2 Second iterator.
Returns:
True if less equal.
template<typename RandomAccessIterator1 , typename RandomAccessIterator2 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1end1, RandomAccessIterator2 &begin2, RandomAccessIterator2end2, RandomAccessIterator3target, typename std::iterator_traits< RandomAccessIterator1 >::difference_typemax_length, Comparatorcomp) [inline]¶
Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge.
comp Comparator.
Returns:
Output end iterator.
template<typename RandomAccessIterator1 , typename RandomAccessIterator3 , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_merge_advance (RandomAccessIterator1 &begin1, RandomAccessIterator1end1, RandomAccessIterator1 &begin2, RandomAccessIterator1end2, RandomAccessIterator3target, typename std::iterator_traits< RandomAccessIterator1 >::difference_typemax_length, Comparatorcomp) [inline]¶
Parallel merge routine being able to merge only the max_length smallest elements. The begin iterators are advanced accordingly, they might not reach end, in contrast to the usual variant. The functionality is projected onto parallel_multiway_merge. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
target Target begin iterator.
max_length Maximum number of elements to merge.
comp Comparator.
Returns:
Output end iterator.
template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Splitter , typename Comparator > RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, Splittersplitter, _DifferenceTplength, Comparatorcomp, thread_index_tnum_threads)¶
Parallel multi-way merge routine. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings. Must not be called if the number of sequences is 1. Parameters:Splitter functor to split input (either
exact or sampling based)
seqs_begin Begin iterator of iterator pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, possibly larger than the number of
elements available.
stable Stable merging incurs a performance penalty.
sentinel Ignored.
Returns:
End iterator of output sequence.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_nth_element (RandomAccessIteratorbegin, RandomAccessIteratornth, RandomAccessIteratorend, Comparatorcomp)¶
Parallel implementation of std::nth_element(). Parameters:begin Begin iterator of input sequence.
nth Iterator of element that must be in position afterwards.
end End iterator of input sequence.
comp Comparator.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_partial_sort (RandomAccessIteratorbegin, RandomAccessIteratormiddle, RandomAccessIteratorend, Comparatorcomp)¶
Parallel implementation of std::partial_sort(). Parameters:begin Begin iterator of input sequence.
middle Sort until this position.
end End iterator of input sequence.
comp Comparator.
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum (InputIteratorbegin, InputIteratorend, OutputIteratorresult, BinaryOperationbin_op)¶
Parallel partial sum front-end. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.
Returns:
End iterator of output sequence.
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum_basecase (InputIteratorbegin, InputIteratorend, OutputIteratorresult, BinaryOperationbin_op, typename std::iterator_traits< InputIterator >::value_typevalue)¶
Base case prefix sum routine. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.
value Start value. Must be passed since the neutral element is unknown in
general.
Returns:
End iterator of output sequence.
template<typename InputIterator , typename OutputIterator , typename BinaryOperation > OutputIterator __gnu_parallel::parallel_partial_sum_linear (InputIteratorbegin, InputIteratorend, OutputIteratorresult, BinaryOperationbin_op, typename std::iterator_traits< InputIterator >::difference_typen)¶
Parallel partial sum implementation, two-phase approach, no recursion. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
result Begin iterator of output sequence.
bin_op Associative binary function.
n Length of sequence.
num_threads Number of threads to use.
Returns:
End iterator of output sequence.
template<typename RandomAccessIterator , typename Predicate > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_partition (RandomAccessIteratorbegin, RandomAccessIteratorend, Predicatepred, thread_index_tnum_threads)¶
Parallel implementation of std::partition. Parameters:begin Begin iterator of input sequence
to split.
end End iterator of input sequence to split.
pred Partition predicate, possibly including some kind of pivot.
num_threads Maximum number of threads to use for this task.
Returns:
Number of elements not fulfilling the
predicate.
template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle (RandomAccessIteratorbegin, RandomAccessIteratorend, RandomNumberGeneratorrng = random_number()) [inline]¶
Parallel random public call. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
rng Random number generator to use.
template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle_drs (RandomAccessIteratorbegin, RandomAccessIteratorend, typename std::iterator_traits< RandomAccessIterator >::difference_typen, thread_index_tnum_threads, RandomNumberGenerator &rng)¶
Main parallel random shuffle step. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
n Length of sequence.
num_threads Number of threads to use.
rng Random number generator to use.
template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::parallel_random_shuffle_drs_pu (DRSSorterPU< RandomAccessIterator, RandomNumberGenerator > *pus)¶
Random shuffle code executed by each thread. Parameters:pus Array of thread-local data
records.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, multiway_mergesort_tagparallelism) [inline]¶
Choose multiway mergesort, splitting variant at run-time, for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, multiway_mergesort_exact_tagparallelism) [inline]¶
Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, multiway_mergesort_sampling_tagparallelism) [inline]¶
Choose multiway mergesort with splitting by sampling, for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, quicksort_tagparallelism) [inline]¶
Choose quicksort for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, balanced_quicksort_tagparallelism) [inline]¶
Choose balanced quicksort for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
stable Sort stable.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, default_parallel_tagparallelism) [inline]¶
Choose multiway mergesort with exact splitting, for parallel sorting. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
template<bool stable, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, parallel_tagparallelism) [inline]¶
Choose a parallel sorting algorithm. Parameters:begin Begin iterator of input sequence.
end End iterator of input sequence.
comp Comparator.
stable Sort stable.
template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_mwms (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tnum_threads)¶
PMWMS main call. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
n Length of sequence.
num_threads Number of threads to use.
template<bool stable, bool exact, typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_mwms_pu (PMWMSSortingData< RandomAccessIterator > *sd, Comparator &comp)¶
PMWMS code executed by each thread. Parameters:sd Pointer to algorithm data.
comp Comparator.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qs (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tnum_threads)¶
Unbalanced quicksort main call. Parameters:begin Begin iterator of input sequence.
end End iterator input sequence, ignored.
comp Comparator.
num_threads Number of threads that are allowed to work on this
part.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qs_conquer (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tnum_threads)¶
Unbalanced quicksort conquer step. Parameters:begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this
part.
template<typename RandomAccessIterator , typename Comparator > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::parallel_sort_qs_divide (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, typename std::iterator_traits< RandomAccessIterator >::difference_typepivot_rank, typename std::iterator_traits< RandomAccessIterator >::difference_typenum_samples, thread_index_tnum_threads)¶
Unbalanced quicksort divide step. Parameters:begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
pivot_rank Desired rank of the pivot.
num_samples Choose pivot from that many samples.
num_threads Number of threads that are allowed to work on this
part.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::parallel_sort_qsb (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tnum_threads)¶
Top-level quicksort routine. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this
part.
template<typename InputIterator , class OutputIterator , class BinaryPredicate > OutputIterator __gnu_parallel::parallel_unique_copy (InputIteratorfirst, InputIteratorlast, OutputIteratorresult, BinaryPredicatebinary_pred)¶
Parallel std::unique_copy(), w/o explicit equality predicate. Parameters:first Begin iterator of input sequence.
last End iterator of input sequence.
result Begin iterator of result sequence.
binary_pred Equality predicate.
Returns:
End iterator of result sequence.
template<typename InputIterator , class OutputIterator > OutputIterator __gnu_parallel::parallel_unique_copy (InputIteratorfirst, InputIteratorlast, OutputIteratorresult) [inline]¶
Parallel std::unique_copy(), without explicit equality predicate. Parameters:first Begin iterator of input sequence.
last End iterator of input sequence.
result Begin iterator of result sequence.
Returns:
End iterator of result sequence.
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::qsb_conquer (QSBThreadLocal< RandomAccessIterator > **tls, RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tiam, thread_index_tnum_threads, boolparent_wait)¶
Quicksort conquer step. Parameters:tls Array of thread-local storages.
begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
iam Number of the thread processing this function.
num_threads Number of threads that are allowed to work on this
part.
template<typename RandomAccessIterator , typename Comparator > std::iterator_traits<RandomAccessIterator>::difference_type __gnu_parallel::qsb_divide (RandomAccessIteratorbegin, RandomAccessIteratorend, Comparatorcomp, thread_index_tnum_threads)¶
Balanced quicksort divide step. Parameters:begin Begin iterator of subsequence.
end End iterator of subsequence.
comp Comparator.
num_threads Number of threads that are allowed to work on this
part.
Precondition:
(end-begin)>=1
template<typename RandomAccessIterator , typename Comparator > void __gnu_parallel::qsb_local_sort_with_helping (QSBThreadLocal< RandomAccessIterator > **tls, Comparator &comp, intiam, boolwait)¶
Quicksort step doing load-balanced local sort. Parameters:tls Array of thread-local storages.
comp Comparator.
iam Number of the thread processing this function.
template<typename RandomNumberGenerator > int __gnu_parallel::random_number_pow2 (intlogp, RandomNumberGenerator &rng) [inline]¶
Generate a random number in [0,2^logp). Parameters:logp Logarithm (basis 2) of the upper
range bound.
rng Random number generator to use.
template<typename T > T __gnu_parallel::round_up_to_pow2 (Tx)¶
Round up to the next greater power of 2. Parameters:x Integer to round up
template<typename _RandomAccessIterator1 , typename _RandomAccessIterator2 , typename Pred > _RandomAccessIterator1 __gnu_parallel::search_template (_RandomAccessIterator1begin1, _RandomAccessIterator1end1, _RandomAccessIterator2begin2, _RandomAccessIterator2end2, Predpred)¶
Parallel std::search. Parameters:begin1 Begin iterator of first
sequence.
end1 End iterator of first sequence.
begin2 Begin iterator of second sequence.
end2 End iterator of second sequence.
pred Find predicate.
Returns:
Place of finding in first sequences.
template<bool stable, bool sentinels, typename RandomAccessIteratorIterator , typename RandomAccessIterator3 , typename _DifferenceTp , typename Comparator > RandomAccessIterator3 __gnu_parallel::sequential_multiway_merge (RandomAccessIteratorIteratorseqs_begin, RandomAccessIteratorIteratorseqs_end, RandomAccessIterator3target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, _DifferenceTplength, Comparatorcomp)¶
Sequential multi-way merging switch. The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and runtime settings. Parameters:seqs_begin Begin iterator of iterator
pair input sequence.
seqs_end End iterator of iterator pair input sequence.
target Begin iterator out output sequence.
comp Comparator.
length Maximum length to merge, possibly larger than the number of
elements available.
stable Stable merging incurs a performance penalty.
sentinel The sequences have a sentinel element.
Returns:
End iterator of output sequence.
template<typename RandomAccessIterator , typename RandomNumberGenerator > void __gnu_parallel::sequential_random_shuffle (RandomAccessIteratorbegin, RandomAccessIteratorend, RandomNumberGenerator &rng)¶
Sequential cache-efficient random shuffle. Parameters:begin Begin iterator of sequence.
end End iterator of sequence.
rng Random number generator to use.
template<typename InputIterator > void __gnu_parallel::shrink ( std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length)¶
Combines two ranges into one and thus halves the number of ranges. Parameters:os_starts Start positions worked on
(oversampled).
count_to_two Counts up to 2.
range_length Current length of a chunk.
template<typename InputIterator > void __gnu_parallel::shrink_and_double ( std::vector< InputIterator > &os_starts, size_t &count_to_two, size_t &range_length, const boolmake_twice)¶
Shrinks and doubles the ranges. Parameters:os_starts Start positions worked on
(oversampled).
count_to_two Counts up to 2.
range_length Current length of a chunk.
make_twice Whether the os_starts is allowed to be grown or not
void __gnu_parallel::yield () [inline]¶
Yield the control to another thread, without waiting for the end to the time slice. Definition at line 340 of file parallel/compatibility.h. Referenced by for_each_template_random_access_workstealing(), and qsb_local_sort_with_helping().Variable Documentation¶
const int __gnu_parallel::lcas_t_bits [static]¶
Number of bits of lcas_t. Definition at line 149 of file types.h. Referenced by decode2(), and encode2().const lcas_t __gnu_parallel::lcas_t_mask [static]¶
lcas_t with the right half of bits set to 1. Definition at line 152 of file types.h. Referenced by decode2().Author¶
Generated automatically by Doxygen for libstdc++ from the source code.Thu Aug 2 2012 | libstdc++ |