multiseq_selection.h File Reference

Functions to find elements of a certain global __rank in multiple sorted sequences. Also serves for splitting such sequence sets. More...

#include <vector>
#include <queue>
#include <bits/stl_algo.h>

Go to the source code of this file.

Classes
class	__gnu_parallel::_Lexicographic< _T1, _T2, _Compare >
	Compare __a pair of types lexicographically, ascending. More...
class	__gnu_parallel::_LexicographicReverse< _T1, _T2, _Compare >
	Compare __a pair of types lexicographically, descending. More...

Namespaces
	__gnu_parallel
	GNU parallel code for public use.

Macros
#define	__S(__i)   (__begin_seqs[__i].first)
#define	__S(__i)   (__begin_seqs[__i].first)

Functions
template<typename _RanSeqs , typename _RankType , typename _RankIterator , typename _Compare >
void	__gnu_parallel::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. More...
template<typename _Tp , typename _RanSeqs , typename _RankType , typename _Compare >
_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. More...

Detailed Description

Functions to find elements of a certain global __rank in multiple sorted sequences. Also serves for splitting such sequence sets.

The algorithm description can be found in

P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. Merging Multiple Lists on Hierarchical-Memory Multiprocessors. Journal of Parallel and Distributed Computing, 12(2):171–177, 1991.

This file is a GNU parallel extension to the Standard C++ Library.

Macro Definition Documentation

#define __S

(

__i

)

(__begin_seqs[__i].first)

#define __S

(

__i

)

(__begin_seqs[__i].first)