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

• namespace __gnu_parallel

Classes

• class __gnu_parallel::guarded_iterator< RandomAccessIterator, Comparator >

  Iterator wrapper supporting an implicit supremum at the end of the sequence, dominating all comparisons. Deriving from RandomAccessIterator is not possible since RandomAccessIterator need not be a class. More...
  

• class __gnu_parallel::unguarded_iterator< RandomAccessIterator, Comparator >

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 RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable, bool sentinel, sequential_tag)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_3_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• 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, bool stable)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_4_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• 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, bool stable)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_bubble (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• 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, bool stable)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_combined (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• template<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_loser_tree_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• 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, Comparator comp, _DifferenceTp length, bool stable)
• template<typename RandomAccessIteratorPairIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::multiway_merge_sentinel (RandomAccessIteratorPairIterator seqs_begin, RandomAccessIteratorPairIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable)
• 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<typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 __gnu_parallel::parallel_multiway_merge (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length, bool stable, bool sentinel)
• template<typename RandomAccessIteratorIterator, typename Comparator> std::iterator_traits< typename
  std::iterator_traits< RandomAccessIteratorIterator
  >::value_type::first_type
  >::difference_type __gnu_parallel::prepare_unguarded (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp, int &min_sequence, bool stable)
• template<typename RandomAccessIteratorIterator, typename Comparator> std::iterator_traits< typename
  std::iterator_traits< RandomAccessIteratorIterator
  >::value_type::first_type
  >::difference_type __gnu_parallel::prepare_unguarded_sentinel (RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, Comparator comp)

---

Define Documentation

#define _GLIBCXX_PARALLEL_LENGTH

(

s

)

Length of a sequence described by a pair of iterators.

Definition at line 60 of file multiway_merge.h.

Referenced by __gnu_parallel::multiway_merge_3_combined(), __gnu_parallel::multiway_merge_4_combined(), __gnu_parallel::multiway_merge_bubble(), __gnu_parallel::multiway_merge_loser_tree(), __gnu_parallel::multiway_merge_loser_tree_combined(), __gnu_parallel::multiway_merge_loser_tree_sentinel(), __gnu_parallel::multiway_merge_loser_tree_unguarded(), and __gnu_parallel::parallel_multiway_merge().

---