__gnu_parallel(3) Library Functions Manual __gnu_parallel(3) NAME __gnu_parallel - GNU parallel code for public use. SYNOPSIS Classes struct __accumulate_binop_reduct General reduction, using a binary operator. struct __accumulate_selector std::accumulate() selector. struct __adjacent_difference_selector Selector that returns the difference between two adjacent __elements. struct __adjacent_find_selector Test predicate on two adjacent elements. class __binder1st Similar to std::binder1st, but giving the argument types explicitly. class __binder2nd Similar to std::binder2nd, but giving the argument types explicitly. struct __count_if_selector std::count_if () selector. struct __count_selector std::count() selector. struct __fill_selector std::fill() selector. struct __find_first_of_selector Test predicate on several elements. struct __find_if_selector Test predicate on a single element, used for std::find() and std::find_if (). struct __for_each_selector std::for_each() selector. struct __generate_selector std::generate() selector. struct __generic_find_selector Base class of all __gnu_parallel::__find_template selectors. struct __generic_for_each_selector Generic __selector for embarrassingly parallel functions. struct __identity_selector Selector that just returns the passed iterator. struct __inner_product_selector std::inner_product() selector. struct __max_element_reduct Reduction for finding the maximum element, using a comparator. struct __min_element_reduct Reduction for finding the maximum element, using a comparator. struct __mismatch_selector Test inverted predicate on a single element. struct __multiway_merge_3_variant_sentinel_switch Switch for 3-way merging with __sentinels turned off. struct __multiway_merge_3_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > Switch for 3-way merging with __sentinels turned on. struct __multiway_merge_4_variant_sentinel_switch Switch for 4-way merging with __sentinels turned off. struct __multiway_merge_4_variant_sentinel_switch< true, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > Switch for 4-way merging with __sentinels turned on. struct __multiway_merge_k_variant_sentinel_switch Switch for k-way merging with __sentinels turned on. struct __multiway_merge_k_variant_sentinel_switch< false, __stable, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare > Switch for k-way merging with __sentinels turned off. struct __replace_if_selector std::replace() selector. struct __replace_selector std::replace() selector. struct __transform1_selector std::transform() __selector, one input sequence variant. struct __transform2_selector std::transform() __selector, two input sequences variant. class __unary_negate Similar to std::unary_negate, but giving the argument types explicitly. struct _DRandomShufflingGlobalData Data known to every thread participating in __gnu_parallel::__parallel_random_shuffle(). struct _DRSSorterPU Local data for a thread participating in __gnu_parallel::__parallel_random_shuffle(). struct _DummyReduct Reduction function doing nothing. class _EqualFromLess Constructs predicate for equality from strict weak ordering predicate. struct _EqualTo Similar to std::equal_to, but allows two different types. class _GuardedIterator _Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. class _IteratorPair A pair of iterators. The usual iterator operations are applied to both child iterators. class _IteratorTriple A triple of iterators. The usual iterator operations are applied to all three child iterators. struct _Job One __job for a certain thread. struct _Less Similar to std::less, but allows two different types. class _Lexicographic Compare __a pair of types lexicographically, ascending. class _LexicographicReverse Compare __a pair of types lexicographically, descending. class _LoserTree Stable _LoserTree variant. class _LoserTree< false, _Tp, _Compare > Unstable _LoserTree variant. class _LoserTreeBase Guarded loser/tournament tree. class _LoserTreePointer Stable _LoserTree implementation. class _LoserTreePointer< false, _Tp, _Compare > Unstable _LoserTree implementation. class _LoserTreePointerBase Base class of _Loser Tree implementation using pointers. class _LoserTreePointerUnguarded Stable unguarded _LoserTree variant storing pointers. class _LoserTreePointerUnguarded< false, _Tp, _Compare > Unstable unguarded _LoserTree variant storing pointers. class _LoserTreePointerUnguardedBase Unguarded loser tree, keeping only pointers to the elements in the tree structure. struct _LoserTreeTraits Traits for determining whether the loser tree should use pointers or copies. class _LoserTreeUnguarded Stable implementation of unguarded _LoserTree. class _LoserTreeUnguarded< false, _Tp, _Compare > Non-Stable implementation of unguarded _LoserTree. class _LoserTreeUnguardedBase Base class for unguarded _LoserTree implementation. struct _Multiplies Similar to std::multiplies, but allows two different types. struct _Nothing Functor doing nothing. struct _Piece Subsequence description. struct _Plus Similar to std::plus, but allows two different types. struct _PMWMSSortingData Data accessed by all threads. class _PseudoSequence Sequence that conceptually consists of multiple copies of the same element. The copies are not stored explicitly, of course. class _PseudoSequenceIterator _Iterator associated with __gnu_parallel::_PseudoSequence. If features the usual random-access iterator functionality. struct _QSBThreadLocal Information local to one thread in the parallel quicksort run. class _RandomNumber Random number generator, based on the Mersenne twister. class _RestrictedBoundedConcurrentQueue Double-ended queue of bounded size, allowing lock-free atomic access. push_front() and pop_front() must not be called concurrently to each other, while pop_back() can be called concurrently at all times. empty(), size(), and top() are intentionally not provided. Calling them would not make sense in a concurrent setting. struct _SamplingSorter Stable sorting functor. struct _SamplingSorter< false, _RAIter, _StrictWeakOrdering > Non-__stable sorting functor. struct _Settings class _Settings Run-time settings for the parallel mode including all tunable parameters. struct _SplitConsistently Split consistently. struct _SplitConsistently< false, _RAIter, _Compare, _SortingPlacesIterator > Split by sampling. struct _SplitConsistently< true, _RAIter, _Compare, _SortingPlacesIterator > Split by exact splitting. struct balanced_quicksort_tag Forces parallel sorting using balanced quicksort at compile time. struct balanced_tag Recommends parallel execution using dynamic load-balancing at compile time. struct constant_size_blocks_tag Selects the constant block size variant for std::find(). struct default_parallel_tag Recommends parallel execution using the default parallel algorithm. struct equal_split_tag Selects the equal splitting variant for std::find(). struct exact_tag Forces parallel merging with exact splitting, at compile time. struct find_tag Base class for for std::find() variants. struct growing_blocks_tag Selects the growing block size variant for std::find(). struct multiway_mergesort_exact_tag Forces parallel sorting using multiway mergesort with exact splitting at compile time. struct multiway_mergesort_sampling_tag Forces parallel sorting using multiway mergesort with splitting by sampling at compile time. struct multiway_mergesort_tag Forces parallel sorting using multiway mergesort at compile time. struct omp_loop_static_tag Recommends parallel execution using OpenMP static load-balancing at compile time. struct omp_loop_tag Recommends parallel execution using OpenMP dynamic load-balancing at compile time. struct parallel_tag Recommends parallel execution at compile time, optionally using a user-specified number of threads. struct quicksort_tag Forces parallel sorting using unbalanced quicksort at compile time. struct sampling_tag Forces parallel merging with exact splitting, at compile time. struct sequential_tag Forces sequential execution at compile time. struct unbalanced_tag Recommends parallel execution using static load-balancing at compile time. Typedefs typedef unsigned short _BinIndex Type to hold the index of a bin. typedef int64_t _CASable Longest compare-and-swappable integer type on this platform. typedef uint64_t _SequenceIndex Unsigned integer to index __elements. The total number of elements for each algorithm must fit into this type. typedef uint16_t _ThreadIndex Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. Enumerations enum _AlgorithmStrategy { heuristic, force_sequential, force_parallel } Strategies for run-time algorithm selection: enum _FindAlgorithm { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT } Find algorithms: enum _MultiwayMergeAlgorithm { LOSER_TREE } Merging algorithms: enum _Parallelism { sequential, parallel_unbalanced, parallel_balanced, parallel_omp_loop, parallel_omp_loop_static, parallel_taskqueue } Run-time equivalents for the compile-time tags. enum _PartialSumAlgorithm { RECURSIVE, LINEAR } Partial sum algorithms: recursive, linear. enum _SortAlgorithm { MWMS, QS, QS_BALANCED } Sorting algorithms: enum _SplittingAlgorithm { SAMPLING, EXACT } Sorting/merging algorithms: sampling, __exact. Functions template _Tp __add_omp (volatile _Tp *__ptr, _Tp __addend) template void __calc_borders (_RAIter __elements, _DifferenceTp __length, _DifferenceTp *__off) Precalculate __advances for Knuth-Morris-Pratt algorithm. template bool __cas_omp (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement) template bool __compare_and_swap (volatile _Tp *__ptr, _Tp __comparand, _Tp __replacement) Compare-and-swap. template _OutputIterator __copy_tail (std::pair< _IIter, _IIter > __b, std::pair< _IIter, _IIter > __e, _OutputIterator __r) void __decode2 (_CASable __x, int &__a, int &__b) Decode two integers from one gnu_parallel::_CASable. template void __determine_samples (_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples) Select _M_samples from a sequence. _CASable __encode2 (int __a, int __b) Encode two integers into one gnu_parallel::_CASable. template _OutputIterator __equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s) function to split a sequence into parts of almost equal size. template _DifferenceType __equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_no) function to split a sequence into parts of almost equal size. template _Tp __fetch_and_add (volatile _Tp *__ptr, _Tp __addend) Add a value to a variable, atomically. template std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector) Parallel std::find, switch for different algorithms. template std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, constant_size_blocks_tag) Parallel std::find, constant block size variant. template std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, equal_split_tag) Parallel std::find, equal splitting variant. template std::pair< _RAIter1, _RAIter2 > __find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, growing_blocks_tag) Parallel std::find, growing block size variant. template _UserOp __for_each_template_random_access (_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag) Chose the desired algorithm by evaluating __parallelism_tag. template _Op __for_each_template_random_access_ed (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) Embarrassingly parallel algorithm for random access iterators, using hand-crafted parallelization by equal splitting the work. template _Op __for_each_template_random_access_omp_loop (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop. template _Op __for_each_template_random_access_omp_loop_static (_RAIter __begin, _RAIter __end, _Op __o, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) Embarrassingly parallel algorithm for random access iterators, using an OpenMP for loop with static scheduling. template _Op __for_each_template_random_access_workstealing (_RAIter __begin, _RAIter __end, _Op __op, _Fu &__f, _Red __r, _Result __base, _Result &__output, typename std::iterator_traits< _RAIter >::difference_type __bound) Work stealing algorithm for random access iterators. _ThreadIndex __get_max_threads () bool __is_parallel (const _Parallelism __p) template bool __is_sorted (_IIter __begin, _IIter __end, _Compare __comp) Check whether [__begin, __end) is sorted according to __comp. template _RAIter __median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp) Compute the median of three referenced elements, according to __comp. template _OutputIterator __merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) Merge routine being able to merge only the __max_length smallest elements. template _OutputIterator __merge_advance_movc (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) Merge routine being able to merge only the __max_length smallest elements. template _OutputIterator __merge_advance_usual (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) Merge routine being able to merge only the __max_length smallest elements. template _RAIter3 __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter1 &__begin2, _RAIter1 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) Parallel merge routine being able to merge only the __max_length smallest elements. template _RAIter3 __parallel_merge_advance (_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. template void __parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp) Parallel implementation of std::nth_element(). template void __parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp) Parallel implementation of std::partial_sort(). template _OutputIterator __parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op) Parallel partial sum front-__end. template _OutputIterator __parallel_partial_sum_basecase (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::value_type __value) Base case prefix sum routine. template _OutputIterator __parallel_partial_sum_linear (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::difference_type __n) Parallel partial sum implementation, two-phase approach, no recursion. template std::iterator_traits< _RAIter >::difference_type __parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads) Parallel implementation of std::partition. template void __parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber()) Parallel random public call. template void __parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_threads, _RandomNumberGenerator &__rng) Main parallel random shuffle step. template void __parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus) Random shuffle code executed by each thread. template _OutputIterator __parallel_set_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) template _OutputIterator __parallel_set_intersection (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) template _OutputIterator __parallel_set_operation (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Operation __op) template _OutputIterator __parallel_set_symmetric_difference (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) template _OutputIterator __parallel_set_union (_IIter __begin1, _IIter __end1, _IIter __begin2, _IIter __end2, _OutputIterator __result, _Compare __comp) template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, _Parallelism __parallelism) template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, balanced_quicksort_tag __parallelism) Choose balanced quicksort for parallel sorting. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism) Choose multiway mergesort with exact splitting, for parallel sorting. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism) Choose multiway mergesort with exact splitting, for parallel sorting. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism) Choose multiway mergesort with splitting by sampling, for parallel sorting. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism) Choose multiway mergesort, splitting variant at run-time, for parallel sorting. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism) Choose a parallel sorting algorithm. template void __parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism) Choose quicksort for parallel sorting. template void __parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) Unbalanced quicksort main call. template void __parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) Unbalanced quicksort conquer step. template std::iterator_traits< _RAIter >::difference_type __parallel_sort_qs_divide (_RAIter __begin, _RAIter __end, _Compare __comp, typename std::iterator_traits< _RAIter >::difference_type __pivot_rank, typename std::iterator_traits< _RAIter >::difference_type __num_samples, _ThreadIndex __num_threads) Unbalanced quicksort divide step. template void __parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) Top-level quicksort routine. template _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result) Parallel std::unique_copy(), without explicit equality predicate. template _OutputIterator __parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred) Parallel std::unique_copy(), w/__o explicit equality predicate. template void __qsb_conquer (_QSBThreadLocal< _RAIter > **__tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_wait) Quicksort conquer step. template std::iterator_traits< _RAIter >::difference_type __qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) Balanced quicksort divide step. template void __qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > **__tls, _Compare &__comp, _ThreadIndex __iam, bool __wait) Quicksort step doing load-balanced local sort. template int __random_number_pow2 (int __logp, _RandomNumberGenerator &__rng) Generate a random number in [0,2^__logp). template _Size __rd_log2 (_Size __n) Calculates the rounded-down logarithm of __n for base 2. template _Tp __round_up_to_pow2 (_Tp __x) Round up to the next greater power of 2. template __RAIter1 __search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred) Parallel std::search. template _RAIter3 __sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) Sequential multi-way merging switch. template void __sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng) Sequential cache-efficient random shuffle. template void __shrink (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length) Combines two ranges into one and thus halves the number of ranges. template void __shrink_and_double (std::vector< _IIter > &__os_starts, size_t &__count_to_two, size_t &__range_length, const bool __make_twice) Shrinks and doubles the ranges. void __yield () Yield control to another thread, without waiting for the end of the time slice. template size_t list_partition (const _IIter __begin, const _IIter __end, _IIter *__starts, size_t *__lengths, const int __num_parts, _FunctorType &__f, int __oversampling=0) Splits a sequence given by input iterators into parts of almost equal size. template const _Tp & max (const _Tp &__a, const _Tp &__b) Equivalent to std::max. template const _Tp & min (const _Tp &__a, const _Tp &__b) Equivalent to std::min. template void multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=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. template _Tp multiseq_selection (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType &__offset, _Compare __comp=std::less< _Tp >()) Selects the element at a certain global __rank from several sorted sequences. template _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) template _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sampling_tag __tag) template _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) Multiway Merge Frontend. template _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) template _RAIterOut multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) template class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) Highly efficient 3-way merging procedure. template class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) Highly efficient 4-way merging procedure. template void multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces) Exact splitting for parallel multiway-merge routine. template _RAIter3 multiway_merge_loser_tree (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) Multi-way merging procedure for a high branching factor, guarded case. template _RAIter3 multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) Multi-way merging procedure for a high branching factor, requiring sentinels to exist. template _RAIter3 multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type &__sentinel, _DifferenceTp __length, _Compare __comp) Multi-way merging procedure for a high branching factor, unguarded case. template void multiway_merge_sampling_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > *__pieces) Sampling based splitting for parallel multiway-merge routine. template _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) template _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) Multiway Merge Frontend. template _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) template _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) template _RAIterOut multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) template _RAIter3 parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_threads) Parallel multi-way merge routine. template void parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) PMWMS main call. template void parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp) PMWMS code executed by each thread. template _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) template _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) template _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) template _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) template _RAIterOut stable_multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) template _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::exact_tag __tag) template _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag) template _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, default_parallel_tag __tag) template _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, parallel_tag __tag=parallel_tag(0)) template _RAIterOut stable_multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, sampling_tag __tag) Variables static const int _CASable_bits Number of bits of _CASable. static const _CASable _CASable_mask _CASable with the right half of bits set to 1. Detailed Description GNU parallel code for public use. Typedef Documentation typedef unsigned short __gnu_parallel::_BinIndex Type to hold the index of a bin. Since many variables of this type are allocated, it should be chosen as small as possible. typedef int64_t __gnu_parallel::_CASable Longest compare-and-swappable integer type on this platform. typedef uint64_t __gnu_parallel::_SequenceIndex Unsigned integer to index __elements. The total number of elements for each algorithm must fit into this type. typedef uint16_t __gnu_parallel::_ThreadIndex Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit into this type. Enumeration Type Documentation enum __gnu_parallel::_AlgorithmStrategy Strategies for run-time algorithm selection: enum __gnu_parallel::_FindAlgorithm Find algorithms: enum __gnu_parallel::_MultiwayMergeAlgorithm Merging algorithms: 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. enum __gnu_parallel::_SortAlgorithm Sorting algorithms: enum __gnu_parallel::_SplittingAlgorithm Sorting/merging algorithms: sampling, __exact. Function Documentation template void __gnu_parallel::__calc_borders (_RAIter __elements, _DifferenceTp __length, _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. __off Returned __offsets. Referenced by __search_template(). template bool __gnu_parallel::__compare_and_swap (volatile _Tp * __ptr, _Tp __comparand, _Tp __replacement) [inline] Compare-and-swap. Compare *__ptr and __comparand. If equal, let *__ptr=__replacement and return true, return false otherwise. Parameters __ptr Pointer to signed integer. __comparand Compare value. __replacement Replacement value. Referenced by __parallel_partition(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_back(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_front(). void __gnu_parallel::__decode2 (_CASable __x, int & __a, int & __b) [inline] Decode two integers from one gnu_parallel::_CASable. Parameters __x __gnu_parallel::_CASable to decode integers from. __a First integer, to be decoded from the most-significant _CASable_bits/2 bits of __x. __b Second integer, to be encoded in the least-significant _CASable_bits/2 bits of __x. See also __encode2 References _CASable_bits, and _CASable_mask. Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::push_front(). template void __gnu_parallel::__determine_samples (_PMWMSSortingData< _RAIter > * __sd, _DifferenceTp __num_samples) Select _M_samples from a sequence. Parameters __sd Pointer to algorithm data. _Result will be placed in __sd->_M_samples. __num_samples Number of _M_samples to select. References __equally_split(), __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, and __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts. _CASable __gnu_parallel::__encode2 (int __a, int __b) [inline] Encode two integers into one gnu_parallel::_CASable. Parameters __a First integer, to be encoded in the most-significant _CASable_bits/2 bits. __b Second integer, to be encoded in the least-significant _CASable_bits/2 bits. Returns value encoding __a and __b. See also __decode2 References _CASable_bits. Referenced by __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::_RestrictedBoundedConcurrentQueue(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_back(), __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::pop_front(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::push_front(). template _OutputIterator __gnu_parallel::__equally_split (_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s) 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 Referenced by __determine_samples(), __find_template(), __parallel_partial_sum_linear(), __parallel_unique_copy(), __search_template(), and multiway_merge_exact_splitting(). template _DifferenceType __gnu_parallel::__equally_split_point (_DifferenceType __n, _ThreadIndex __num_threads, _ThreadIndex __thread_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 __thread_no Number of threads Returns splitting point Referenced by __for_each_template_random_access_ed(). template _Tp __gnu_parallel::__fetch_and_add (volatile _Tp * __ptr, _Tp __addend) [inline] Add a value to a variable, atomically. Parameters __ptr Pointer to a signed integer. __addend Value to add. Referenced by __find_template(), __for_each_template_random_access_workstealing(), __parallel_partition(), and __gnu_parallel::_RestrictedBoundedConcurrentQueue< _Tp >::push_front(). template std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector) [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. References __find_template(), __gnu_parallel::_Settings::get(), and std::make_pair(). Referenced by __find_template(). template std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, constant_size_blocks_tag ) Parallel std::find, constant block size variant. Parameters __begin1 Begin iterator of first sequence. __end1 End iterator of first sequence. __begin2 Begin iterator of second sequence. 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. See also __gnu_parallel::_Settings::find_sequential_search_size __gnu_parallel::_Settings::find_block_size There are two main differences between the growing blocks and the constant-size blocks variants. 1. For GB, the block size grows; for CSB, the block size is fixed. 2. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round-robin. References _GLIBCXX_CALL, __gnu_parallel::_Settings::find_initial_block_size, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, __gnu_parallel::_Settings::get(), and std::min(). template std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, equal_split_tag ) Parallel std::find, equal splitting variant. Parameters __begin1 Begin iterator of first sequence. __end1 End iterator of first sequence. __begin2 Begin iterator of second sequence. 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. References __equally_split(), and _GLIBCXX_CALL. template std::pair< _RAIter1, _RAIter2 > __gnu_parallel::__find_template (_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector, growing_blocks_tag ) Parallel std::find, growing block size variant. Parameters __begin1 Begin iterator of first sequence. __end1 End iterator of first sequence. __begin2 Begin iterator of second sequence. 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. See also __gnu_parallel::_Settings::find_sequential_search_size __gnu_parallel::_Settings::find_scale_factor There are two main differences between the growing blocks and the constant-size blocks variants. 1. For GB, the block size grows; for CSB, the block size is fixed. 2. For GB, the blocks are allocated dynamically; for CSB, the blocks are allocated in a predetermined manner, namely spacial round- robin. References __fetch_and_add(), _GLIBCXX_CALL, __gnu_parallel::_Settings::find_scale_factor, __gnu_parallel::_Settings::find_sequential_search_size, std::pair< _T1, _T2 >::first, __gnu_parallel::_Settings::get(), std::max(), and std::min(). template _UserOp __gnu_parallel::__for_each_template_random_access (_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality & __functionality, _Red __reduction, _Result __reduction_start, _Result & __output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_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 References __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), __for_each_template_random_access_workstealing(), parallel_omp_loop, parallel_omp_loop_static, and parallel_unbalanced. template _Op __gnu_parallel::__for_each_template_random_access_ed (_RAIter __begin, _RAIter __end, _Op __o, _Fu & __f, _Red __r, _Result __base, _Result & __output, typename std::iterator_traits< _RAIter >::difference_type __bound) 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). References __equally_split_point(), and min(). Referenced by __for_each_template_random_access(). template _Op __gnu_parallel::__for_each_template_random_access_omp_loop (_RAIter __begin, _RAIter __end, _Op __o, _Fu & __f, _Red __r, _Result __base, _Result & __output, typename std::iterator_traits< _RAIter >::difference_type __bound) 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). References min(). Referenced by __for_each_template_random_access(). template _Op __gnu_parallel::__for_each_template_random_access_omp_loop_static (_RAIter __begin, _RAIter __end, _Op __o, _Fu & __f, _Red __r, _Result __base, _Result & __output, typename std::iterator_traits< _RAIter >::difference_type __bound) 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). References std::min(). template _Op __gnu_parallel::__for_each_template_random_access_workstealing (_RAIter __begin, _RAIter __end, _Op __op, _Fu & __f, _Red __r, _Result __base, _Result & __output, typename std::iterator_traits< _RAIter >::difference_type __bound) 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). References __fetch_and_add(), __yield(), _GLIBCXX_CALL, __gnu_parallel::_Job< _DifferenceTp >::_M_first, __gnu_parallel::_Job< _DifferenceTp >::_M_last, __gnu_parallel::_Job< _DifferenceTp >::_M_load, __gnu_parallel::_Settings::cache_line_size, __gnu_parallel::_Settings::get(), max(), and min(). Referenced by __for_each_template_random_access(). template bool __gnu_parallel::__is_sorted (_IIter __begin, _IIter __end, _Compare __comp) 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. Referenced by __sequential_multiway_merge(), multiway_merge_loser_tree_sentinel(), and parallel_multiway_merge(). template _RAIter __gnu_parallel::__median_of_three_iterators (_RAIter __a, _RAIter __b, _RAIter __c, _Compare __comp) Compute the median of three referenced elements, according to __comp. Parameters __a First iterator. __b Second iterator. __c Third iterator. __comp Comparator. Referenced by __qsb_divide(). template _OutputIterator __gnu_parallel::__merge_advance (_RAIter1 & __begin1, _RAIter1 __end1, _RAIter2 & __begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) [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. References __merge_advance_movc(), and _GLIBCXX_CALL. Referenced by __parallel_merge_advance(), and __sequential_multiway_merge(). template _OutputIterator __gnu_parallel::__merge_advance_movc (_RAIter1 & __begin1, _RAIter1 __end1, _RAIter2 & __begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) 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. Referenced by __merge_advance(). template _OutputIterator __gnu_parallel::__merge_advance_usual (_RAIter1 & __begin1, _RAIter1 __end1, _RAIter2 & __begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp) 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 _RAIter3 __gnu_parallel::__parallel_merge_advance (_RAIter1 & __begin1, _RAIter1 __end1, _RAIter1 & __begin2, _RAIter1 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) [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. References std::make_pair(), multiway_merge_exact_splitting(), and parallel_multiway_merge(). template _RAIter3 __gnu_parallel::__parallel_merge_advance (_RAIter1 & __begin1, _RAIter1 __end1, _RAIter2 & __begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp) [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. References __merge_advance(). template void __gnu_parallel::__parallel_nth_element (_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp) 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. References __parallel_partition(), _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), std::max(), __gnu_parallel::_Settings::nth_element_minimal_n, and __gnu_parallel::_Settings::partition_minimal_n. Referenced by __parallel_partial_sort(). template void __gnu_parallel::__parallel_partial_sort (_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp) 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. References __parallel_nth_element(). template _OutputIterator __gnu_parallel::__parallel_partial_sum (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_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. References __parallel_partial_sum_linear(), _GLIBCXX_CALL, and __gnu_parallel::_Settings::get(). template _OutputIterator __gnu_parallel::__parallel_partial_sum_basecase (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::value_type __value) 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. Referenced by __parallel_partial_sum_linear(). template _OutputIterator __gnu_parallel::__parallel_partial_sum_linear (_IIter __begin, _IIter __end, _OutputIterator __result, _BinaryOperation __bin_op, typename std::iterator_traits< _IIter >::difference_type __n) 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. Returns End iterator of output sequence. References __equally_split(), __parallel_partial_sum_basecase(), __gnu_parallel::_Settings::get(), std::max(), std::min(), and __gnu_parallel::_Settings::partial_sum_dilation. Referenced by __parallel_partial_sum(). template std::iterator_traits< _RAIter >::difference_type __gnu_parallel::__parallel_partition (_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_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. References __compare_and_swap(), __fetch_and_add(), _GLIBCXX_CALL, _GLIBCXX_VOLATILE, __gnu_parallel::_Settings::get(), std::max(), __gnu_parallel::_Settings::partition_chunk_share, and __gnu_parallel::_Settings::partition_chunk_size. Referenced by __parallel_nth_element(), __parallel_sort_qs_divide(), and __qsb_divide(). template void __gnu_parallel::__parallel_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng = _RandomNumber()) [inline] Parallel random public call. Parameters __begin Begin iterator of sequence. __end End iterator of sequence. __rng Random number generator to use. References __parallel_random_shuffle_drs(). template void __gnu_parallel::__parallel_random_shuffle_drs (_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_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. References __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::__bins_end, __parallel_random_shuffle_drs_pu(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(), _GLIBCXX_CALL, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_bin_proc, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_bins_begin, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_temporaries, __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, std::max(), std::min(), and __gnu_parallel::_Settings::TLB_size. Referenced by __parallel_random_shuffle(). template void __gnu_parallel::__parallel_random_shuffle_drs_pu (_DRSSorterPU< _RAIter, _RandomNumberGenerator > * __pus) Random shuffle code executed by each thread. Parameters __pus Array of thread-local data records. References __random_number_pow2(), __sequential_random_shuffle(), __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_bin_proc, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_bins_begin, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_dist, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bins, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_num_bits, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_num_threads, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_sd, __gnu_parallel::_DRSSorterPU< _RAIter, _RandomNumberGenerator >::_M_seed, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_source, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_starts, __gnu_parallel::_DRandomShufflingGlobalData< _RAIter >::_M_temporaries, and std::partial_sum(). Referenced by __parallel_random_shuffle_drs(). template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, balanced_quicksort_tag __parallelism) [inline] Choose balanced quicksort for parallel sorting. Parameters __begin Begin iterator of input sequence. __end End iterator of input sequence. __comp Comparator. Template Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qsb(), and _GLIBCXX_CALL. template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, default_parallel_tag __parallelism) [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 Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), and _GLIBCXX_CALL. template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_exact_tag __parallelism) [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 Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, and parallel_sort_mwms(). template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_sampling_tag __parallelism) [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 Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, and parallel_sort_mwms(). template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, multiway_mergesort_tag __parallelism) [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 Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and parallel_sort_mwms(). template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, parallel_tag __parallelism) [inline] Choose a parallel sorting algorithm. Parameters __begin Begin iterator of input sequence. __end End iterator of input sequence. __comp Comparator. Template Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), __parallel_sort_qsb(), _GLIBCXX_CALL, __gnu_parallel::_Settings::get(), and parallel_sort_mwms(). template void __gnu_parallel::__parallel_sort (_RAIter __begin, _RAIter __end, _Compare __comp, quicksort_tag __parallelism) [inline] Choose quicksort for parallel sorting. Parameters __begin Begin iterator of input sequence. __end End iterator of input sequence. __comp Comparator. Template Parameters __stable Sort stable. References __gnu_parallel::parallel_tag::__get_num_threads(), __parallel_sort_qs(), and _GLIBCXX_CALL. template void __gnu_parallel::__parallel_sort_qs (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_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. References __parallel_sort_qs_conquer(), and _GLIBCXX_CALL. Referenced by __parallel_sort(), and __parallel_sort(). template void __gnu_parallel::__parallel_sort_qs_conquer (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_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. References __parallel_sort_qs_conquer(), __parallel_sort_qs_divide(), and __gnu_parallel::_Settings::get(). Referenced by __parallel_sort_qs(), and __parallel_sort_qs_conquer(). template std::iterator_traits< _RAIter >::difference_type __gnu_parallel::__parallel_sort_qs_divide (_RAIter __begin, _RAIter __end, _Compare __comp, typename std::iterator_traits< _RAIter >::difference_type __pivot_rank, typename std::iterator_traits< _RAIter >::difference_type __num_samples, _ThreadIndex __num_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. References __parallel_partition(), and std::min(). Referenced by __parallel_sort_qs_conquer(). template void __gnu_parallel::__parallel_sort_qsb (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_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. References __qsb_conquer(), __rd_log2(), _GLIBCXX_CALL, and std::make_pair(). Referenced by __parallel_sort(), and __parallel_sort(). template _OutputIterator __gnu_parallel::__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result) [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. References __parallel_unique_copy(). template _OutputIterator __gnu_parallel::__parallel_unique_copy (_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_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. References __equally_split(), and _GLIBCXX_CALL. Referenced by __parallel_unique_copy(). template void __gnu_parallel::__qsb_conquer (_QSBThreadLocal< _RAIter > ** __tls, _RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __iam, _ThreadIndex __num_threads, bool __parent_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. References __qsb_conquer(), __qsb_divide(), __qsb_local_sort_with_helping(), __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, std::max(), and std::min(). Referenced by __parallel_sort_qsb(), and __qsb_conquer(). template std::iterator_traits< _RAIter >::difference_type __gnu_parallel::__qsb_divide (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_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 References __median_of_three_iterators(), and __parallel_partition(). Referenced by __qsb_conquer(). template void __gnu_parallel::__qsb_local_sort_with_helping (_QSBThreadLocal< _RAIter > ** __tls, _Compare & __comp, _ThreadIndex __iam, bool __wait) Quicksort step doing load-balanced local sort. Parameters __tls Array of thread-local storages. __comp Comparator. __iam Number of the thread processing this function. References __yield(), _GLIBCXX_PARALLEL_ASSERTIONS, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_elements_leftover, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_initial, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_leftover_parts, __gnu_parallel::_QSBThreadLocal< _RAIter >::_M_num_threads, __gnu_parallel::_Settings::get(), std::make_pair(), and __gnu_parallel::_Settings::sort_qsb_base_case_maximal_n. Referenced by __qsb_conquer(). template int __gnu_parallel::__random_number_pow2 (int __logp, _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. Referenced by __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle(). template _Size __gnu_parallel::__rd_log2 (_Size __n) [inline] Calculates the rounded-down logarithm of __n for base 2. Parameters __n Argument. Returns Returns 0 for any argument <1. Referenced by __gnu_parallel::_LoserTreeBase< _Tp, _Compare >::_LoserTreeBase(), __parallel_random_shuffle_drs(), __parallel_sort_qsb(), __round_up_to_pow2(), __sequential_random_shuffle(), multiseq_partition(), and multiseq_selection(). template _Tp __gnu_parallel::__round_up_to_pow2 (_Tp __x) Round up to the next greater power of 2. Parameters __x _Integer to round up References __rd_log2(). Referenced by __parallel_random_shuffle_drs(), __sequential_random_shuffle(), and multiseq_selection(). template __RAIter1 __gnu_parallel::__search_template (__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred) 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. References __calc_borders(), __equally_split(), _GLIBCXX_CALL, std::max(), and std::min(). template _RAIter3 __gnu_parallel::__sequential_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & __sentinel, _DifferenceTp __length, _Compare __comp) 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 of output sequence. __comp Comparator. __length Maximum length to merge, possibly larger than the number of elements available. __sentinel The sequences have __a __sentinel element. Returns End iterator of output sequence. References __is_sorted(), __merge_advance(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, and std::min(). Referenced by multiway_merge(), multiway_merge_sentinels(), and parallel_multiway_merge(). template void __gnu_parallel::__sequential_random_shuffle (_RAIter __begin, _RAIter __end, _RandomNumberGenerator & __rng) Sequential cache-efficient random shuffle. Parameters __begin Begin iterator of sequence. __end End iterator of sequence. __rng Random number generator to use. References __random_number_pow2(), __rd_log2(), __round_up_to_pow2(), __sequential_random_shuffle(), __gnu_parallel::_Settings::get(), __gnu_parallel::_Settings::L2_cache_size, std::max(), std::min(), std::partial_sum(), and __gnu_parallel::_Settings::TLB_size. Referenced by __parallel_random_shuffle_drs(), __parallel_random_shuffle_drs_pu(), and __sequential_random_shuffle(). template void __gnu_parallel::__shrink (std::vector< _IIter > & __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. References std::vector< _Tp, _Alloc >::size(). Referenced by __shrink_and_double(). template void __gnu_parallel::__shrink_and_double (std::vector< _IIter > & __os_starts, size_t & __count_to_two, size_t & __range_length, const bool __make_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 References __shrink(), std::vector< _Tp, _Alloc >::resize(), and std::vector< _Tp, _Alloc >::size(). Referenced by list_partition(). void __gnu_parallel::__yield () [inline] Yield control to another thread, without waiting for the end of the time slice. Referenced by __for_each_template_random_access_workstealing(), and __qsb_local_sort_with_helping(). template size_t __gnu_parallel::list_partition (const _IIter __begin, const _IIter __end, _IIter * __starts, size_t * __lengths, const int __num_parts, _FunctorType & __f, int __oversampling = 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. References __shrink_and_double(), and std::vector< _Tp, _Alloc >::size(). template const _Tp & __gnu_parallel::max (const _Tp & __a, const _Tp & __b) [inline] Equivalent to std::max. Referenced by __for_each_template_random_access_workstealing(). template const _Tp & __gnu_parallel::min (const _Tp & __a, const _Tp & __b) [inline] Equivalent to std::min. Referenced by __for_each_template_random_access_ed(), __for_each_template_random_access_omp_loop(), and __for_each_template_random_access_workstealing(). template void __gnu_parallel::multiseq_partition (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp = std::less< typename std::iterator_traits::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<_Tp>. References __rd_log2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::make_pair(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top(). Referenced by multiway_merge_exact_splitting(). template _Tp __gnu_parallel::multiseq_selection (_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType & __offset, _Compare __comp = std::less<_Tp>()) 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. References __rd_log2(), __round_up_to_pow2(), _GLIBCXX_CALL, std::distance(), std::priority_queue< _Tp, _Sequence, _Compare >::empty(), std::make_pair(), std::max(), std::min(), std::priority_queue< _Tp, _Sequence, _Compare >::pop(), std::priority_queue< _Tp, _Sequence, _Compare >::push(), and std::priority_queue< _Tp, _Sequence, _Compare >::top(). template _RAIterOut __gnu_parallel::multiway_merge (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __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 _M_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: o not stable o parallel, depending on the input size and Settings o using sampling for splitting o not using sentinels Example: 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 > seqs; for (int __i = 0; __i < 10; ++__i) { seqs.push(std::make_pair(sequences[__i], sequences[__i] + 10)) } multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 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). Template Parameters _RAIterPairIterator iterator over sequence of pairs of iterators _RAIterOut iterator over target sequence _DifferenceTp difference type for the sequence _Compare strict weak ordering type to compare elements in sequences Parameters __seqs_begin __begin of sequence __sequence __seqs_end _M_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 _M_end iterator of output sequence References __sequential_multiway_merge(), and _GLIBCXX_CALL. template class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_3_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) 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 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 of output sequence. __comp Comparator. __length Maximum length to merge, less equal than the total number of elements available. Returns End iterator of output sequence. References _GLIBCXX_CALL. template class iterator, typename _RAIterIterator , typename _RAIter3 , typename _DifferenceTp , typename _Compare > _RAIter3 __gnu_parallel::multiway_merge_4_variant (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) 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 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 of output sequence. __comp Comparator. __length Maximum length to merge, less equal than the total number of elements available. Returns End iterator of output sequence. References _GLIBCXX_CALL. template void __gnu_parallel::multiway_merge_exact_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > * __pieces) Exact splitting for parallel multiway-merge routine. None of the passed sequences may be empty. References __equally_split(), _GLIBCXX_PARALLEL_LENGTH, std::vector< _Tp, _Alloc >::begin(), std::vector< _Tp, _Alloc >::end(), multiseq_partition(), and std::vector< _Tp, _Alloc >::resize(). Referenced by __parallel_merge_advance(). template _RAIter3 __gnu_parallel::multiway_merge_loser_tree (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _DifferenceTp __length, _Compare __comp) 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 of output sequence. __comp Comparator. __length Maximum length to merge, less equal than the total number of elements available. Returns End iterator of output sequence. References _GLIBCXX_CALL, and _GLIBCXX_PARALLEL_LENGTH. template _RAIter3 __gnu_parallel::multiway_merge_loser_tree_sentinel (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & __sentinel, _DifferenceTp __length, _Compare __comp) Multi-way merging procedure for a high branching factor, requiring sentinels to exist. Template Parameters _UnguardedLoserTree Loser Tree variant to use for the unguarded merging. Parameters __seqs_begin Begin iterator of iterator pair input sequence. __seqs_end End iterator of iterator pair input sequence. __target Begin iterator of output sequence. __comp Comparator. __length Maximum length to merge, less equal than the total number of elements available. Returns End iterator of output sequence. References __is_sorted(), _GLIBCXX_CALL, and multiway_merge_loser_tree_unguarded(). template _RAIter3 __gnu_parallel::multiway_merge_loser_tree_unguarded (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, const typename std::iterator_traits< typename std::iterator_traits< _RAIterIterator >::value_type::first_type >::value_type & __sentinel, _DifferenceTp __length, _Compare __comp) 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 of output sequence. __comp Comparator. __length Maximum length to merge, less equal than the total number of elements available. Returns End iterator of output sequence. References _GLIBCXX_CALL. Referenced by multiway_merge_loser_tree_sentinel(). template void __gnu_parallel::multiway_merge_sampling_splitting (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _DifferenceType __length, _DifferenceType __total_length, _Compare __comp, std::vector< std::pair< _DifferenceType, _DifferenceType > > * __pieces) Sampling based splitting for parallel multiway-merge routine. References _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), and __gnu_parallel::_Settings::merge_oversampling. template _RAIterOut __gnu_parallel::multiway_merge_sentinels (_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __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 _M_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: o not stable o parallel, depending on the input size and Settings o using sampling for splitting o using sentinels You have to take care that the element the _M_end iterator points to is readable and contains a value that is greater than any other non- sentinel value in all sequences. Example: 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 > seqs; for (int __i = 0; __i < 10; ++__i) { seqs.push(std::make_pair(sequences[__i], sequences[__i] + 10)) } multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 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 Template Parameters _RAIterPairIterator iterator over sequence of pairs of iterators _RAIterOut iterator over target sequence _DifferenceTp difference type for the sequence _Compare strict weak ordering type to compare elements in sequences Parameters __seqs_begin __begin of sequence __sequence __seqs_end _M_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 _M_end iterator of output sequence References __sequential_multiway_merge(), and _GLIBCXX_CALL. template _RAIter3 __gnu_parallel::parallel_multiway_merge (_RAIterIterator __seqs_begin, _RAIterIterator __seqs_end, _RAIter3 __target, _Splitter __splitter, _DifferenceTp __length, _Compare __comp, _ThreadIndex __num_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. Template Parameters _Splitter functor to split input (either __exact or sampling based) __stable Stable merging incurs a performance penalty. __sentinel Ignored. Parameters __seqs_begin Begin iterator of iterator pair input sequence. __seqs_end End iterator of iterator pair input sequence. __target Begin iterator of output sequence. __comp Comparator. __length Maximum length to merge, possibly larger than the number of elements available. Returns End iterator of output sequence. References __is_sorted(), __sequential_multiway_merge(), _GLIBCXX_CALL, _GLIBCXX_PARALLEL_LENGTH, __gnu_parallel::_Settings::get(), std::make_pair(), __gnu_parallel::_Settings::merge_oversampling, and std::min(). Referenced by __parallel_merge_advance(). template void __gnu_parallel::parallel_sort_mwms (_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads) PMWMS main call. Parameters __begin Begin iterator of sequence. __end End iterator of sequence. __comp Comparator. __num_threads Number of threads to use. References _GLIBCXX_CALL, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_offsets, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_samples, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), parallel_sort_mwms_pu(), and __gnu_parallel::_Settings::sort_mwms_oversampling. Referenced by __parallel_sort(), __parallel_sort(), __parallel_sort(), and __parallel_sort(). template void __gnu_parallel::parallel_sort_mwms_pu (_PMWMSSortingData< _RAIter > * __sd, _Compare & __comp) PMWMS code executed by each thread. Parameters __sd Pointer to algorithm data. __comp Comparator. References __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_num_threads, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_pieces, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_source, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_starts, __gnu_parallel::_PMWMSSortingData< _RAIter >::_M_temporary, __gnu_parallel::_Settings::get(), std::make_pair(), __gnu_parallel::_Settings::sort_mwms_oversampling, and std::uninitialized_copy(). Referenced by parallel_sort_mwms(). Variable Documentation const int __gnu_parallel::_CASable_bits [static] Number of bits of _CASable. Referenced by __decode2(), and __encode2(). const _CASable __gnu_parallel::_CASable_mask [static] _CASable with the right half of bits set to 1. Referenced by __decode2(). Author Generated automatically by Doxygen for libstdc++ from the source code. libstdc++ __gnu_parallel(3)