multiway_merge.h File Reference
Detailed Description
Implementation of sequential and parallel multiway merge.
Explanations on the high-speed merging routines in the appendix of
P. Sanders. Fast priority queues for cached memory. ACM Journal of Experimental Algorithmics, 5, 2000.
This file is a GNU parallel extension to the Standard C++ Library.
Definition in file multiway_merge.h.
Go to the source code of this file.
Namespaces
Classes
- class __gnu_parallel::guarded_iterator< RandomAccessIterator, Comparator >
- Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. More...
- struct __gnu_parallel::loser_tree_traits< T >
- Traits for determining whether the loser tree should use pointers or copies. More...
- struct __gnu_parallel::multiway_merge_3_variant_sentinel_switch< sentinels, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for 3-way merging with sentinels turned off. More...
- struct __gnu_parallel::multiway_merge_3_variant_sentinel_switch< true, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for 3-way merging with sentinels turned on. More...
- struct __gnu_parallel::multiway_merge_4_variant_sentinel_switch< sentinels, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for 4-way merging with sentinels turned off. More...
- struct __gnu_parallel::multiway_merge_4_variant_sentinel_switch< true, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for 4-way merging with sentinels turned on. More...
- struct __gnu_parallel::multiway_merge_k_variant_sentinel_switch< sentinels, stable, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for k-way merging with sentinels turned on. More...
- struct __gnu_parallel::multiway_merge_k_variant_sentinel_switch< false, stable, RandomAccessIteratorIterator, RandomAccessIterator3, _DifferenceTp, Comparator >
- Switch for k-way merging with sentinels turned off. More...
- struct __gnu_parallel::sampling_sorter< stable, RandomAccessIterator, StrictWeakOrdering >
- Stable sorting functor. More...
- struct __gnu_parallel::sampling_sorter< false, RandomAccessIterator, StrictWeakOrdering >
- Non-stable sorting functor. More...
Defines
-
#define _GLIBCXX_PARALLEL_DECISION(a, b, c, d)
- #define _GLIBCXX_PARALLEL_LENGTH(s)
-
#define _GLIBCXX_PARALLEL_MERGE_3_CASE(a, b, c, c0, c1)
-
#define _GLIBCXX_PARALLEL_MERGE_4_CASE(a, b, c, d, c0, c1, c2)
Functions
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::exact_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::sequential_tag)
- template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length)
- template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_3_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length)
- template<template< typename RAI, typename C > class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_4_variant (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length)
- template<bool stable, typename RandomAccessIteratorIterator, typename Comparator, typename difference_type> void __gnu_parallel::multiway_merge_exact_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, difference_type length, difference_type total_length, std::vector< std::pair< difference_type, difference_type > > *pieces)
- template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length)
- template<typename UnguardedLoserTree, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, Comparator comp, _DifferenceTp length)
- template<typename LT, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, Comparator comp, _DifferenceTp length)
- template<bool stable, typename RandomAccessIteratorIterator, typename Comparator, typename difference_type> void __gnu_parallel::multiway_merge_sampling_splitting (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, difference_type length, difference_type total_length, std::vector< std::pair< difference_type, difference_type > > *pieces)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::exact_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::sequential_tag)
- template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length)
- template<typename RandomAccessIterator, typename Comparator> bool __gnu_parallel::operator< (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
- template<typename RandomAccessIterator, typename Comparator> bool __gnu_parallel::operator< (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
- template<typename RandomAccessIterator, typename Comparator> bool __gnu_parallel::operator<= (unguarded_iterator< RandomAccessIterator, Comparator > &bi1, unguarded_iterator< RandomAccessIterator, Comparator > &bi2)
- template<typename RandomAccessIterator, typename Comparator> bool __gnu_parallel::operator<= (guarded_iterator< RandomAccessIterator, Comparator > &bi1, guarded_iterator< RandomAccessIterator, Comparator > &bi2)
- template<bool stable, bool sentinels, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Splitter, typename Comparator> RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, Splitter splitter, _DifferenceTp length)
- template<bool stable, bool sentinels, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::sequential_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, const typename std::iterator_traits< typename std::iterator_traits< RandomAccessIteratorIterator >::value_type::first_type >::value_type &sentinel, Comparator comp, _DifferenceTp length)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::exact_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::sequential_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::exact_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length, __gnu_parallel::sequential_tag)
-
template<typename RandomAccessIteratorPairIterator, typename RandomAccessIteratorOut, typename _DifferenceTp, typename Comparator> RandomAccessIteratorOut __gnu_parallel::stable_multiway_merge_sentinels (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIteratorOut target, Comparator comp, _DifferenceTp length)
Define Documentation
#define _GLIBCXX_PARALLEL_LENGTH |
( |
s |
|
) |
|