3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file parallel/multiway_merge.h
26 * @brief Implementation of sequential and parallel multiway merge.
28 * Explanations on the high-speed merging routines in the appendix of
31 * Fast priority queues for cached memory.
32 * ACM Journal of Experimental Algorithmics, 5, 2000.
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Johannes Singler and Manuel Holtgrewe.
39 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
40 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
44 #include <bits/stl_algo.h>
45 #include <parallel/features.h>
46 #include <parallel/parallel.h>
47 #include <parallel/losertree.h>
48 #if _GLIBCXX_ASSERTIONS
49 #include <parallel/checkers.h>
52 /** @brief Length of a sequence described by a pair of iterators. */
53 #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
55 namespace __gnu_parallel
57 /** @brief _Iterator wrapper supporting an implicit supremum at the end
58 * of the sequence, dominating all comparisons.
60 * The implicit supremum comes with a performance cost.
62 * Deriving from _RAIter is not possible since
63 * _RAIter need not be a class.
65 template<typename _RAIter
, typename _Compare
>
66 class _GuardedIterator
69 /** @brief Current iterator __position. */
72 /** @brief End iterator of the sequence. */
75 /** @brief _Compare. */
79 /** @brief Constructor. Sets iterator to beginning of sequence.
80 * @param __begin Begin iterator of sequence.
81 * @param __end End iterator of sequence.
82 * @param __comp Comparator provided for associated overloaded
83 * compare operators. */
84 _GuardedIterator(_RAIter __begin
, _RAIter __end
, _Compare
& __comp
)
85 : _M_current(__begin
), _M_end(__end
), __comp(__comp
)
88 /** @brief Pre-increment operator.
90 _GuardedIterator
<_RAIter
, _Compare
>&
97 /** @brief Dereference operator.
98 * @return Referenced element. */
99 typename
std::iterator_traits
<_RAIter
>::value_type
&
101 { return *_M_current
; }
103 /** @brief Convert to wrapped iterator.
104 * @return Wrapped iterator. */
106 { return _M_current
; }
108 /** @brief Compare two elements referenced by guarded iterators.
109 * @param __bi1 First iterator.
110 * @param __bi2 Second iterator.
111 * @return @c true if less. */
113 operator<(_GuardedIterator
<_RAIter
, _Compare
>& __bi1
,
114 _GuardedIterator
<_RAIter
, _Compare
>& __bi2
)
116 if (__bi1
._M_current
== __bi1
._M_end
) // __bi1 is sup
117 return __bi2
._M_current
== __bi2
._M_end
; // __bi2 is not sup
118 if (__bi2
._M_current
== __bi2
._M_end
) // __bi2 is sup
120 return (__bi1
.__comp
)(*__bi1
, *__bi2
); // normal compare
123 /** @brief Compare two elements referenced by guarded iterators.
124 * @param __bi1 First iterator.
125 * @param __bi2 Second iterator.
126 * @return @c True if less equal. */
128 operator<=(_GuardedIterator
<_RAIter
, _Compare
>& __bi1
,
129 _GuardedIterator
<_RAIter
, _Compare
>& __bi2
)
131 if (__bi2
._M_current
== __bi2
._M_end
) // __bi1 is sup
132 return __bi1
._M_current
!= __bi1
._M_end
; // __bi2 is not sup
133 if (__bi1
._M_current
== __bi1
._M_end
) // __bi2 is sup
135 return !(__bi1
.__comp
)(*__bi2
, *__bi1
); // normal compare
139 template<typename _RAIter
, typename _Compare
>
140 class _UnguardedIterator
143 /** @brief Current iterator __position. */
145 /** @brief _Compare. */
146 mutable _Compare
& __comp
;
149 /** @brief Constructor. Sets iterator to beginning of sequence.
150 * @param __begin Begin iterator of sequence.
151 * @param __end Unused, only for compatibility.
152 * @param __comp Unused, only for compatibility. */
153 _UnguardedIterator(_RAIter __begin
,
154 _RAIter
/* __end */, _Compare
& __comp
)
155 : _M_current(__begin
), __comp(__comp
)
158 /** @brief Pre-increment operator.
160 _UnguardedIterator
<_RAIter
, _Compare
>&
167 /** @brief Dereference operator.
168 * @return Referenced element. */
169 typename
std::iterator_traits
<_RAIter
>::value_type
&
171 { return *_M_current
; }
173 /** @brief Convert to wrapped iterator.
174 * @return Wrapped iterator. */
176 { return _M_current
; }
178 /** @brief Compare two elements referenced by unguarded iterators.
179 * @param __bi1 First iterator.
180 * @param __bi2 Second iterator.
181 * @return @c true if less. */
183 operator<(_UnguardedIterator
<_RAIter
, _Compare
>& __bi1
,
184 _UnguardedIterator
<_RAIter
, _Compare
>& __bi2
)
187 return (__bi1
.__comp
)(*__bi1
, *__bi2
);
190 /** @brief Compare two elements referenced by unguarded iterators.
191 * @param __bi1 First iterator.
192 * @param __bi2 Second iterator.
193 * @return @c True if less equal. */
195 operator<=(_UnguardedIterator
<_RAIter
, _Compare
>& __bi1
,
196 _UnguardedIterator
<_RAIter
, _Compare
>& __bi2
)
199 return !(__bi1
.__comp
)(*__bi2
, *__bi1
);
203 /** @brief Highly efficient 3-way merging procedure.
205 * Merging is done with the algorithm implementation described by Peter
206 * Sanders. Basically, the idea is to minimize the number of necessary
207 * comparison after merging an element. The implementation trick
208 * that makes this fast is that the order of the sequences is stored
209 * in the instruction pointer (translated into labels in C++).
211 * This works well for merging up to 4 sequences.
213 * Note that making the merging stable does <em>not</em> come at a
216 * Whether the merging is done guarded or unguarded is selected by the
217 * used iterator class.
219 * @param __seqs_begin Begin iterator of iterator pair input sequence.
220 * @param __seqs_end End iterator of iterator pair input sequence.
221 * @param __target Begin iterator of output sequence.
222 * @param __comp Comparator.
223 * @param __length Maximum length to merge, less equal than the
224 * total number of elements available.
226 * @return End iterator of output sequence.
228 template<template<typename RAI
, typename C
> class iterator
,
229 typename _RAIterIterator
,
231 typename _DifferenceTp
,
234 multiway_merge_3_variant(_RAIterIterator __seqs_begin
,
235 _RAIterIterator __seqs_end
,
237 _DifferenceTp __length
, _Compare __comp
)
239 _GLIBCXX_CALL(__length
);
241 typedef _DifferenceTp _DifferenceType
;
243 typedef typename
std::iterator_traits
<_RAIterIterator
>
244 ::value_type::first_type
246 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
252 #if _GLIBCXX_ASSERTIONS
253 _DifferenceTp __orig_length
= __length
;
256 iterator
<_RAIter1
, _Compare
>
257 __seq0(__seqs_begin
[0].first
, __seqs_begin
[0].second
, __comp
),
258 __seq1(__seqs_begin
[1].first
, __seqs_begin
[1].second
, __comp
),
259 __seq2(__seqs_begin
[2].first
, __seqs_begin
[2].second
, __comp
);
261 if (__seq0
<= __seq1
)
263 if (__seq1
<= __seq2
)
273 if (__seq1
<= __seq2
)
275 if (__seq0
<= __seq2
)
283 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
284 __s ## __a ## __b ## __c : \
285 *__target = *__seq ## __a; \
289 if (__length == 0) goto __finish; \
290 if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
291 if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
292 goto __s ## __b ## __c ## __a;
294 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
295 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
296 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
297 _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
298 _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
299 _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
301 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
306 #if _GLIBCXX_ASSERTIONS
307 _GLIBCXX_PARALLEL_ASSERT(
308 ((_RAIter1
)__seq0
- __seqs_begin
[0].first
) +
309 ((_RAIter1
)__seq1
- __seqs_begin
[1].first
) +
310 ((_RAIter1
)__seq2
- __seqs_begin
[2].first
)
314 __seqs_begin
[0].first
= __seq0
;
315 __seqs_begin
[1].first
= __seq1
;
316 __seqs_begin
[2].first
= __seq2
;
322 * @brief Highly efficient 4-way merging procedure.
324 * Merging is done with the algorithm implementation described by Peter
325 * Sanders. Basically, the idea is to minimize the number of necessary
326 * comparison after merging an element. The implementation trick
327 * that makes this fast is that the order of the sequences is stored
328 * in the instruction pointer (translated into goto labels in C++).
330 * This works well for merging up to 4 sequences.
332 * Note that making the merging stable does <em>not</em> come at a
335 * Whether the merging is done guarded or unguarded is selected by the
336 * used iterator class.
338 * @param __seqs_begin Begin iterator of iterator pair input sequence.
339 * @param __seqs_end End iterator of iterator pair input sequence.
340 * @param __target Begin iterator of output sequence.
341 * @param __comp Comparator.
342 * @param __length Maximum length to merge, less equal than the
343 * total number of elements available.
345 * @return End iterator of output sequence.
347 template<template<typename RAI
, typename C
> class iterator
,
348 typename _RAIterIterator
,
350 typename _DifferenceTp
,
353 multiway_merge_4_variant(_RAIterIterator __seqs_begin
,
354 _RAIterIterator __seqs_end
,
356 _DifferenceTp __length
, _Compare __comp
)
358 _GLIBCXX_CALL(__length
);
359 typedef _DifferenceTp _DifferenceType
;
361 typedef typename
std::iterator_traits
<_RAIterIterator
>
362 ::value_type::first_type
364 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
367 iterator
<_RAIter1
, _Compare
>
368 __seq0(__seqs_begin
[0].first
, __seqs_begin
[0].second
, __comp
),
369 __seq1(__seqs_begin
[1].first
, __seqs_begin
[1].second
, __comp
),
370 __seq2(__seqs_begin
[2].first
, __seqs_begin
[2].second
, __comp
),
371 __seq3(__seqs_begin
[3].first
, __seqs_begin
[3].second
, __comp
);
373 #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
374 if (__seq ## __d < __seq ## __a) \
375 goto __s ## __d ## __a ## __b ## __c; \
376 if (__seq ## __d < __seq ## __b) \
377 goto __s ## __a ## __d ## __b ## __c; \
378 if (__seq ## __d < __seq ## __c) \
379 goto __s ## __a ## __b ## __d ## __c; \
380 goto __s ## __a ## __b ## __c ## __d; }
382 if (__seq0
<= __seq1
)
384 if (__seq1
<= __seq2
)
385 _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
388 _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
390 _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
394 if (__seq1
<= __seq2
)
396 if (__seq0
<= __seq2
)
397 _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
399 _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
402 _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
405 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
407 __s ## __a ## __b ## __c ## __d: \
408 if (__length == 0) goto __finish; \
409 *__target = *__seq ## __a; \
413 if (__seq ## __a __c0 __seq ## __b) \
414 goto __s ## __a ## __b ## __c ## __d; \
415 if (__seq ## __a __c1 __seq ## __c) \
416 goto __s ## __b ## __a ## __c ## __d; \
417 if (__seq ## __a __c2 __seq ## __d) \
418 goto __s ## __b ## __c ## __a ## __d; \
419 goto __s ## __b ## __c ## __d ## __a;
421 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
422 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
423 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
424 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
425 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
426 _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
427 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
428 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
429 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
430 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
431 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
432 _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
433 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
434 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
435 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
436 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
437 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
438 _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
439 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
440 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
441 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
442 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
443 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
444 _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
446 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
447 #undef _GLIBCXX_PARALLEL_DECISION
452 __seqs_begin
[0].first
= __seq0
;
453 __seqs_begin
[1].first
= __seq1
;
454 __seqs_begin
[2].first
= __seq2
;
455 __seqs_begin
[3].first
= __seq3
;
460 /** @brief Multi-way merging procedure for a high branching factor,
463 * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>.
465 * Stability is selected through the used LoserTree class <tt>_LT</tt>.
467 * At least one non-empty sequence is required.
469 * @param __seqs_begin Begin iterator of iterator pair input sequence.
470 * @param __seqs_end End iterator of iterator pair input sequence.
471 * @param __target Begin iterator of output sequence.
472 * @param __comp Comparator.
473 * @param __length Maximum length to merge, less equal than the
474 * total number of elements available.
476 * @return End iterator of output sequence.
478 template<typename _LT
,
479 typename _RAIterIterator
,
481 typename _DifferenceTp
,
484 multiway_merge_loser_tree(_RAIterIterator __seqs_begin
,
485 _RAIterIterator __seqs_end
,
487 _DifferenceTp __length
, _Compare __comp
)
489 _GLIBCXX_CALL(__length
)
491 typedef _DifferenceTp _DifferenceType
;
492 typedef typename
std::iterator_traits
<_RAIterIterator
>
493 ::difference_type _SeqNumber
;
494 typedef typename
std::iterator_traits
<_RAIterIterator
>
495 ::value_type::first_type
497 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
500 _SeqNumber __k
= static_cast<_SeqNumber
>(__seqs_end
- __seqs_begin
);
502 _LT
__lt(__k
, __comp
);
504 // Default value for potentially non-default-constructible types.
505 _ValueType
* __arbitrary_element
= NULL
;
507 for (_SeqNumber __t
= 0; __t
< __k
; ++__t
)
509 if(__arbitrary_element
== NULL
510 && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin
[__t
]) > 0)
511 __arbitrary_element
= &(*__seqs_begin
[__t
].first
);
514 for (_SeqNumber __t
= 0; __t
< __k
; ++__t
)
516 if (__seqs_begin
[__t
].first
== __seqs_begin
[__t
].second
)
517 __lt
.__insert_start(*__arbitrary_element
, __t
, true);
519 __lt
.__insert_start(*__seqs_begin
[__t
].first
, __t
, false);
526 for (_DifferenceType __i
= 0; __i
< __length
; ++__i
)
529 __source
= __lt
.__get_min_source();
531 *(__target
++) = *(__seqs_begin
[__source
].first
++);
534 if (__seqs_begin
[__source
].first
== __seqs_begin
[__source
].second
)
535 __lt
.__delete_min_insert(*__arbitrary_element
, true);
537 // Replace from same __source.
538 __lt
.__delete_min_insert(*__seqs_begin
[__source
].first
, false);
544 /** @brief Multi-way merging procedure for a high branching factor,
547 * Merging is done using the LoserTree class <tt>_LT</tt>.
549 * Stability is selected by the used LoserTrees.
551 * @pre No input will run out of elements during the merge.
553 * @param __seqs_begin Begin iterator of iterator pair input sequence.
554 * @param __seqs_end End iterator of iterator pair input sequence.
555 * @param __target Begin iterator of output sequence.
556 * @param __comp Comparator.
557 * @param __length Maximum length to merge, less equal than the
558 * total number of elements available.
560 * @return End iterator of output sequence.
562 template<typename _LT
,
563 typename _RAIterIterator
,
565 typename _DifferenceTp
, typename _Compare
>
567 multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin
,
568 _RAIterIterator __seqs_end
,
570 const typename
std::iterator_traits
<typename
std::iterator_traits
<
571 _RAIterIterator
>::value_type::first_type
>::value_type
&
573 _DifferenceTp __length
,
576 _GLIBCXX_CALL(__length
)
577 typedef _DifferenceTp _DifferenceType
;
579 typedef typename
std::iterator_traits
<_RAIterIterator
>
580 ::difference_type _SeqNumber
;
581 typedef typename
std::iterator_traits
<_RAIterIterator
>
582 ::value_type::first_type
584 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
587 _SeqNumber __k
= __seqs_end
- __seqs_begin
;
589 _LT
__lt(__k
, __sentinel
, __comp
);
591 for (_SeqNumber __t
= 0; __t
< __k
; ++__t
)
593 #if _GLIBCXX_ASSERTIONS
594 _GLIBCXX_PARALLEL_ASSERT(__seqs_begin
[__t
].first
595 != __seqs_begin
[__t
].second
);
597 __lt
.__insert_start(*__seqs_begin
[__t
].first
, __t
, false);
604 #if _GLIBCXX_ASSERTIONS
605 _DifferenceType __i
= 0;
608 _RAIter3 __target_end
= __target
+ __length
;
609 while (__target
< __target_end
)
612 __source
= __lt
.__get_min_source();
614 #if _GLIBCXX_ASSERTIONS
615 _GLIBCXX_PARALLEL_ASSERT(0 <= __source
&& __source
< __k
);
616 _GLIBCXX_PARALLEL_ASSERT(__i
== 0
617 || !__comp(*(__seqs_begin
[__source
].first
), *(__target
- 1)));
621 *(__target
++) = *(__seqs_begin
[__source
].first
++);
623 #if _GLIBCXX_ASSERTIONS
626 // Replace from same __source.
627 __lt
.__delete_min_insert(*__seqs_begin
[__source
].first
, false);
634 /** @brief Multi-way merging procedure for a high branching factor,
635 * requiring sentinels to exist.
637 * @param __stable The value must the same as for the used LoserTrees.
638 * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded
640 * @param GuardedLoserTree _Loser Tree variant to use for the guarded
643 * @param __seqs_begin Begin iterator of iterator pair input sequence.
644 * @param __seqs_end End iterator of iterator pair input sequence.
645 * @param __target Begin iterator of output sequence.
646 * @param __comp Comparator.
647 * @param __length Maximum length to merge, less equal than the
648 * total number of elements available.
650 * @return End iterator of output sequence.
652 template<typename UnguardedLoserTree
,
653 typename _RAIterIterator
,
655 typename _DifferenceTp
,
658 multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin
,
659 _RAIterIterator __seqs_end
,
661 const typename
std::iterator_traits
<typename
std::iterator_traits
<
662 _RAIterIterator
>::value_type::first_type
>::value_type
&
664 _DifferenceTp __length
,
667 _GLIBCXX_CALL(__length
)
669 typedef _DifferenceTp _DifferenceType
;
670 typedef std::iterator_traits
<_RAIterIterator
> _TraitsType
;
671 typedef typename
std::iterator_traits
<_RAIterIterator
>
672 ::value_type::first_type
674 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
677 _RAIter3 __target_end
;
679 for (_RAIterIterator __s
= __seqs_begin
; __s
!= __seqs_end
; ++__s
)
680 // Move the sequence ends to the sentinel. This has the
681 // effect that the sentinel appears to be within the sequence. Then,
682 // we can use the unguarded variant if we merge out as many
683 // non-sentinel elements as we have.
686 __target_end
= multiway_merge_loser_tree_unguarded
<UnguardedLoserTree
>
687 (__seqs_begin
, __seqs_end
, __target
, __sentinel
, __length
, __comp
);
689 #if _GLIBCXX_ASSERTIONS
690 _GLIBCXX_PARALLEL_ASSERT(__target_end
== __target
+ __length
);
691 _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target
, __target_end
, __comp
));
694 // Restore the sequence ends so the sentinels are not contained in the
695 // sequence any more (see comment in loop above).
696 for (_RAIterIterator __s
= __seqs_begin
; __s
!= __seqs_end
; ++__s
)
703 * @brief Traits for determining whether the loser tree should
704 * use pointers or copies.
706 * The field "_M_use_pointer" is used to determine whether to use pointers
707 * in he loser trees or whether to copy the values into the loser tree.
709 * The default behavior is to use pointers if the data type is 4 times as
710 * big as the pointer to it.
712 * Specialize for your data type to customize the behavior.
717 * struct _LoserTreeTraits<int>
718 * { static const bool _M_use_pointer = false; };
721 * struct _LoserTreeTraits<heavyweight_type>
722 * { static const bool _M_use_pointer = true; };
724 * @param _Tp type to give the loser tree traits for.
726 template <typename _Tp
>
727 struct _LoserTreeTraits
730 * @brief True iff to use pointers instead of values in loser trees.
732 * The default behavior is to use pointers if the data type is four
733 * times as big as the pointer to it.
735 static const bool _M_use_pointer
= (sizeof(_Tp
) > 4 * sizeof(_Tp
*));
739 * @brief Switch for 3-way merging with __sentinels turned off.
741 * Note that 3-way merging is always stable!
743 template<bool __sentinels
/*default == false*/,
744 typename _RAIterIterator
,
746 typename _DifferenceTp
,
748 struct __multiway_merge_3_variant_sentinel_switch
751 operator()(_RAIterIterator __seqs_begin
,
752 _RAIterIterator __seqs_end
,
754 _DifferenceTp __length
, _Compare __comp
)
755 { return multiway_merge_3_variant
<_GuardedIterator
>
756 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
); }
760 * @brief Switch for 3-way merging with __sentinels turned on.
762 * Note that 3-way merging is always stable!
764 template<typename _RAIterIterator
,
766 typename _DifferenceTp
,
768 struct __multiway_merge_3_variant_sentinel_switch
<true, _RAIterIterator
,
769 _RAIter3
, _DifferenceTp
,
773 operator()(_RAIterIterator __seqs_begin
,
774 _RAIterIterator __seqs_end
,
776 _DifferenceTp __length
, _Compare __comp
)
777 { return multiway_merge_3_variant
<_UnguardedIterator
>
778 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
); }
782 * @brief Switch for 4-way merging with __sentinels turned off.
784 * Note that 4-way merging is always stable!
786 template<bool __sentinels
/*default == false*/,
787 typename _RAIterIterator
,
789 typename _DifferenceTp
,
791 struct __multiway_merge_4_variant_sentinel_switch
794 operator()(_RAIterIterator __seqs_begin
,
795 _RAIterIterator __seqs_end
,
797 _DifferenceTp __length
, _Compare __comp
)
798 { return multiway_merge_4_variant
<_GuardedIterator
>
799 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
); }
803 * @brief Switch for 4-way merging with __sentinels turned on.
805 * Note that 4-way merging is always stable!
807 template<typename _RAIterIterator
,
809 typename _DifferenceTp
,
811 struct __multiway_merge_4_variant_sentinel_switch
<true, _RAIterIterator
,
812 _RAIter3
, _DifferenceTp
,
816 operator()(_RAIterIterator __seqs_begin
,
817 _RAIterIterator __seqs_end
,
819 _DifferenceTp __length
, _Compare __comp
)
820 { return multiway_merge_4_variant
<_UnguardedIterator
>
821 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
); }
825 * @brief Switch for k-way merging with __sentinels turned on.
827 template<bool __sentinels
,
829 typename _RAIterIterator
,
831 typename _DifferenceTp
,
833 struct __multiway_merge_k_variant_sentinel_switch
836 operator()(_RAIterIterator __seqs_begin
,
837 _RAIterIterator __seqs_end
,
839 const typename
std::iterator_traits
<typename
std::iterator_traits
<
840 _RAIterIterator
>::value_type::first_type
>::value_type
&
842 _DifferenceTp __length
, _Compare __comp
)
844 typedef typename
std::iterator_traits
<_RAIterIterator
>
845 ::value_type::first_type
847 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
850 return multiway_merge_loser_tree_sentinel
<
851 typename
__gnu_cxx::__conditional_type
<
852 _LoserTreeTraits
<_ValueType
>::_M_use_pointer
,
853 _LoserTreePointerUnguarded
<__stable
, _ValueType
, _Compare
>,
854 _LoserTreeUnguarded
<__stable
, _ValueType
, _Compare
>
856 (__seqs_begin
, __seqs_end
, __target
, __sentinel
, __length
, __comp
);
861 * @brief Switch for k-way merging with __sentinels turned off.
863 template<bool __stable
,
864 typename _RAIterIterator
,
866 typename _DifferenceTp
,
868 struct __multiway_merge_k_variant_sentinel_switch
<false, __stable
,
870 _RAIter3
, _DifferenceTp
,
874 operator()(_RAIterIterator __seqs_begin
,
875 _RAIterIterator __seqs_end
,
877 const typename
std::iterator_traits
<typename
std::iterator_traits
<
878 _RAIterIterator
>::value_type::first_type
>::value_type
&
880 _DifferenceTp __length
, _Compare __comp
)
882 typedef typename
std::iterator_traits
<_RAIterIterator
>
883 ::value_type::first_type
885 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
888 return multiway_merge_loser_tree
<
889 typename
__gnu_cxx::__conditional_type
<
890 _LoserTreeTraits
<_ValueType
>::_M_use_pointer
,
891 _LoserTreePointer
<__stable
, _ValueType
, _Compare
>,
892 _LoserTree
<__stable
, _ValueType
, _Compare
>
893 >::__type
>(__seqs_begin
, __seqs_end
, __target
, __length
, __comp
);
897 /** @brief Sequential multi-way merging switch.
899 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
901 * @param __seqs_begin Begin iterator of iterator pair input sequence.
902 * @param __seqs_end End iterator of iterator pair input sequence.
903 * @param __target Begin iterator of output sequence.
904 * @param __comp Comparator.
905 * @param __length Maximum length to merge, possibly larger than the
906 * number of elements available.
907 * @param __stable Stable merging incurs a performance penalty.
908 * @param __sentinel The sequences have __a __sentinel element.
909 * @return End iterator of output sequence. */
910 template<bool __stable
,
912 typename _RAIterIterator
,
914 typename _DifferenceTp
,
917 __sequential_multiway_merge(_RAIterIterator __seqs_begin
,
918 _RAIterIterator __seqs_end
,
920 const typename
std::iterator_traits
<typename
std::iterator_traits
<
921 _RAIterIterator
>::value_type::first_type
>::value_type
&
923 _DifferenceTp __length
, _Compare __comp
)
925 _GLIBCXX_CALL(__length
)
927 typedef _DifferenceTp _DifferenceType
;
928 typedef typename
std::iterator_traits
<_RAIterIterator
>
929 ::difference_type _SeqNumber
;
930 typedef typename
std::iterator_traits
<_RAIterIterator
>
931 ::value_type::first_type
933 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
936 #if _GLIBCXX_ASSERTIONS
937 for (_RAIterIterator __s
= __seqs_begin
; __s
!= __seqs_end
; ++__s
)
939 _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s
).first
,
940 (*__s
).second
, __comp
));
944 _DifferenceTp __total_length
= 0;
945 for (_RAIterIterator __s
= __seqs_begin
; __s
!= __seqs_end
; ++__s
)
946 __total_length
+= _GLIBCXX_PARALLEL_LENGTH(*__s
);
948 __length
= std::min
<_DifferenceTp
>(__length
, __total_length
);
953 _RAIter3 __return_target
= __target
;
954 _SeqNumber __k
= static_cast<_SeqNumber
>(__seqs_end
- __seqs_begin
);
961 __return_target
= std::copy(__seqs_begin
[0].first
,
962 __seqs_begin
[0].first
+ __length
,
964 __seqs_begin
[0].first
+= __length
;
967 __return_target
= __merge_advance(__seqs_begin
[0].first
,
968 __seqs_begin
[0].second
,
969 __seqs_begin
[1].first
,
970 __seqs_begin
[1].second
,
971 __target
, __length
, __comp
);
974 __return_target
= __multiway_merge_3_variant_sentinel_switch
975 <__sentinels
, _RAIterIterator
, _RAIter3
, _DifferenceTp
, _Compare
>()
976 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
);
979 __return_target
= __multiway_merge_4_variant_sentinel_switch
980 <__sentinels
, _RAIterIterator
, _RAIter3
, _DifferenceTp
, _Compare
>()
981 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
);
984 __return_target
= __multiway_merge_k_variant_sentinel_switch
985 <__sentinels
, __stable
, _RAIterIterator
, _RAIter3
, _DifferenceTp
,
987 (__seqs_begin
, __seqs_end
, __target
, __sentinel
, __length
, __comp
);
990 #if _GLIBCXX_ASSERTIONS
991 _GLIBCXX_PARALLEL_ASSERT(
992 __is_sorted(__target
, __target
+ __length
, __comp
));
995 return __return_target
;
999 * @brief Stable sorting functor.
1001 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
1003 template<bool __stable
, class _RAIter
, class _StrictWeakOrdering
>
1004 struct _SamplingSorter
1007 operator()(_RAIter __first
, _RAIter __last
, _StrictWeakOrdering __comp
)
1008 { __gnu_sequential::stable_sort(__first
, __last
, __comp
); }
1012 * @brief Non-__stable sorting functor.
1014 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
1016 template<class _RAIter
, class _StrictWeakOrdering
>
1017 struct _SamplingSorter
<false, _RAIter
, _StrictWeakOrdering
>
1020 operator()(_RAIter __first
, _RAIter __last
, _StrictWeakOrdering __comp
)
1021 { __gnu_sequential::sort(__first
, __last
, __comp
); }
1025 * @brief Sampling based splitting for parallel multiway-merge routine.
1027 template<bool __stable
,
1028 typename _RAIterIterator
,
1030 typename _DifferenceType
>
1032 multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin
,
1033 _RAIterIterator __seqs_end
,
1034 _DifferenceType __length
,
1035 _DifferenceType __total_length
,
1037 std::vector
<std::pair
<_DifferenceType
, _DifferenceType
> > *__pieces
)
1039 typedef typename
std::iterator_traits
<_RAIterIterator
>
1040 ::difference_type _SeqNumber
;
1041 typedef typename
std::iterator_traits
<_RAIterIterator
>
1042 ::value_type::first_type
1044 typedef typename
std::iterator_traits
<_RAIter1
>::value_type
1048 _SeqNumber __k
= static_cast<_SeqNumber
>(__seqs_end
- __seqs_begin
);
1050 _ThreadIndex __num_threads
= omp_get_num_threads();
1052 _DifferenceType __num_samples
=
1053 __gnu_parallel::_Settings::get().merge_oversampling
* __num_threads
;
1055 _ValueType
* __samples
= static_cast<_ValueType
*>
1056 (::operator new(sizeof(_ValueType
) * __k
* __num_samples
));
1058 for (_SeqNumber __s
= 0; __s
< __k
; ++__s
)
1059 for (_DifferenceType __i
= 0; __i
< __num_samples
; ++__i
)
1061 _DifferenceType sample_index
= static_cast<_DifferenceType
>
1062 (_GLIBCXX_PARALLEL_LENGTH(__seqs_begin
[__s
])
1063 * (double(__i
+ 1) / (__num_samples
+ 1))
1064 * (double(__length
) / __total_length
));
1065 new(&(__samples
[__s
* __num_samples
+ __i
]))
1066 _ValueType(__seqs_begin
[__s
].first
[sample_index
]);
1069 // Sort stable or non-stable, depending on value of template parameter
1071 _SamplingSorter
<__stable
, _ValueType
*, _Compare
>()
1072 (__samples
, __samples
+ (__num_samples
* __k
), __comp
);
1074 for (_ThreadIndex __slab
= 0; __slab
< __num_threads
; ++__slab
)
1075 // For each slab / processor.
1076 for (_SeqNumber __seq
= 0; __seq
< __k
; ++__seq
)
1078 // For each sequence.
1080 __pieces
[__slab
][__seq
].first
= std::upper_bound
1081 (__seqs_begin
[__seq
].first
, __seqs_begin
[__seq
].second
,
1082 __samples
[__num_samples
* __k
* __slab
/ __num_threads
],
1084 - __seqs_begin
[__seq
].first
;
1086 // Absolute beginning.
1087 __pieces
[__slab
][__seq
].first
= 0;
1088 if ((__slab
+ 1) < __num_threads
)
1089 __pieces
[__slab
][__seq
].second
= std::upper_bound
1090 (__seqs_begin
[__seq
].first
, __seqs_begin
[__seq
].second
,
1091 __samples
[__num_samples
* __k
* (__slab
+ 1) / __num_threads
],
1093 - __seqs_begin
[__seq
].first
;
1096 __pieces
[__slab
][__seq
].second
=
1097 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin
[__seq
]);
1099 ::operator delete(__samples
);
1103 * @brief Exact splitting for parallel multiway-merge routine.
1105 * None of the passed sequences may be empty.
1107 template<bool __stable
,
1108 typename _RAIterIterator
,
1110 typename _DifferenceType
>
1112 multiway_merge_exact_splitting(_RAIterIterator __seqs_begin
,
1113 _RAIterIterator __seqs_end
,
1114 _DifferenceType __length
,
1115 _DifferenceType __total_length
,
1117 std::vector
<std::pair
<_DifferenceType
, _DifferenceType
> > *__pieces
)
1119 typedef typename
std::iterator_traits
<_RAIterIterator
>
1120 ::difference_type _SeqNumber
;
1121 typedef typename
std::iterator_traits
<_RAIterIterator
>
1122 ::value_type::first_type
1125 const bool __tight
= (__total_length
== __length
);
1128 const _SeqNumber __k
= __seqs_end
- __seqs_begin
;
1130 const _ThreadIndex __num_threads
= omp_get_num_threads();
1132 // (Settings::multiway_merge_splitting
1133 // == __gnu_parallel::_Settings::EXACT).
1134 std::vector
<_RAIter1
>* __offsets
=
1135 new std::vector
<_RAIter1
>[__num_threads
];
1136 std::vector
<std::pair
<_RAIter1
, _RAIter1
> > __se(__k
);
1138 copy(__seqs_begin
, __seqs_end
, __se
.begin());
1140 _DifferenceType
* __borders
=
1141 new _DifferenceType
[__num_threads
+ 1];
1142 equally_split(__length
, __num_threads
, __borders
);
1144 for (_ThreadIndex __s
= 0; __s
< (__num_threads
- 1); ++__s
)
1146 __offsets
[__s
].resize(__k
);
1147 multiseq_partition(__se
.begin(), __se
.end(), __borders
[__s
+ 1],
1148 __offsets
[__s
].begin(), __comp
);
1150 // Last one also needed and available.
1153 __offsets
[__num_threads
- 1].resize(__k
);
1154 multiseq_partition(__se
.begin(), __se
.end(),
1155 _DifferenceType(__length
),
1156 __offsets
[__num_threads
- 1].begin(),
1162 for (_ThreadIndex __slab
= 0; __slab
< __num_threads
; ++__slab
)
1164 // For each slab / processor.
1165 for (_SeqNumber __seq
= 0; __seq
< __k
; ++__seq
)
1167 // For each sequence.
1170 // Absolute beginning.
1171 __pieces
[__slab
][__seq
].first
= 0;
1174 __pieces
[__slab
][__seq
].first
=
1175 __pieces
[__slab
- 1][__seq
].second
;
1176 if (!__tight
|| __slab
< (__num_threads
- 1))
1177 __pieces
[__slab
][__seq
].second
=
1178 __offsets
[__slab
][__seq
] - __seqs_begin
[__seq
].first
;
1181 // __slab == __num_threads - 1
1182 __pieces
[__slab
][__seq
].second
=
1183 _GLIBCXX_PARALLEL_LENGTH(__seqs_begin
[__seq
]);
1190 /** @brief Parallel multi-way merge routine.
1192 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
1193 * and runtime settings.
1195 * Must not be called if the number of sequences is 1.
1197 * @param _Splitter functor to split input (either __exact or sampling based)
1199 * @param __seqs_begin Begin iterator of iterator pair input sequence.
1200 * @param __seqs_end End iterator of iterator pair input sequence.
1201 * @param __target Begin iterator of output sequence.
1202 * @param __comp Comparator.
1203 * @param __length Maximum length to merge, possibly larger than the
1204 * number of elements available.
1205 * @param __stable Stable merging incurs a performance penalty.
1206 * @param __sentinel Ignored.
1207 * @return End iterator of output sequence.
1209 template<bool __stable
,
1211 typename _RAIterIterator
,
1213 typename _DifferenceTp
,
1217 parallel_multiway_merge(_RAIterIterator __seqs_begin
,
1218 _RAIterIterator __seqs_end
,
1220 _Splitter __splitter
,
1221 _DifferenceTp __length
,
1223 _ThreadIndex __num_threads
)
1225 #if _GLIBCXX_ASSERTIONS
1226 _GLIBCXX_PARALLEL_ASSERT(__seqs_end
- __seqs_begin
> 1);
1229 _GLIBCXX_CALL(__length
)
1231 typedef _DifferenceTp _DifferenceType
;
1232 typedef typename
std::iterator_traits
<_RAIterIterator
>
1233 ::difference_type _SeqNumber
;
1234 typedef typename
std::iterator_traits
<_RAIterIterator
>
1235 ::value_type::first_type
1238 std::iterator_traits
<_RAIter1
>::value_type _ValueType
;
1240 // Leave only non-empty sequences.
1241 typedef std::pair
<_RAIter1
, _RAIter1
> seq_type
;
1242 seq_type
* __ne_seqs
= new seq_type
[__seqs_end
- __seqs_begin
];
1244 _DifferenceType __total_length
= 0;
1245 for (_RAIterIterator __raii
= __seqs_begin
;
1246 __raii
!= __seqs_end
; ++__raii
)
1248 _DifferenceTp __seq_length
= _GLIBCXX_PARALLEL_LENGTH(*__raii
);
1249 if(__seq_length
> 0)
1251 __total_length
+= __seq_length
;
1252 __ne_seqs
[__k
++] = *__raii
;
1256 _GLIBCXX_CALL(__total_length
)
1258 __length
= std::min
<_DifferenceTp
>(__length
, __total_length
);
1260 if (__total_length
== 0 || __k
== 0)
1266 std::vector
<std::pair
<_DifferenceType
, _DifferenceType
> >* __pieces
;
1268 __num_threads
= static_cast<_ThreadIndex
>
1269 (std::min
<_DifferenceType
>(__num_threads
, __total_length
));
1271 # pragma omp parallel num_threads (__num_threads)
1275 __num_threads
= omp_get_num_threads();
1276 // Thread __t will have to merge pieces[__iam][0..__k - 1]
1277 __pieces
= new std::vector
<
1278 std::pair
<_DifferenceType
, _DifferenceType
> >[__num_threads
];
1279 for (_ThreadIndex __s
= 0; __s
< __num_threads
; ++__s
)
1280 __pieces
[__s
].resize(__k
);
1282 _DifferenceType __num_samples
=
1283 __gnu_parallel::_Settings::get().merge_oversampling
1286 __splitter(__ne_seqs
, __ne_seqs
+ __k
, __length
, __total_length
,
1290 _ThreadIndex __iam
= omp_get_thread_num();
1292 _DifferenceType __target_position
= 0;
1294 for (_SeqNumber __c
= 0; __c
< __k
; ++__c
)
1295 __target_position
+= __pieces
[__iam
][__c
].first
;
1297 seq_type
* __chunks
= new seq_type
[__k
];
1299 for (_SeqNumber __s
= 0; __s
< __k
; ++__s
)
1300 __chunks
[__s
] = std::make_pair(__ne_seqs
[__s
].first
1301 + __pieces
[__iam
][__s
].first
,
1302 __ne_seqs
[__s
].first
1303 + __pieces
[__iam
][__s
].second
);
1305 if(__length
> __target_position
)
1306 __sequential_multiway_merge
<__stable
, __sentinels
>
1307 (__chunks
, __chunks
+ __k
, __target
+ __target_position
,
1308 *(__seqs_begin
->second
), __length
- __target_position
, __comp
);
1313 #if _GLIBCXX_ASSERTIONS
1314 _GLIBCXX_PARALLEL_ASSERT(
1315 __is_sorted(__target
, __target
+ __length
, __comp
));
1319 // Update ends of sequences.
1320 for (_RAIterIterator __raii
= __seqs_begin
;
1321 __raii
!= __seqs_end
; ++__raii
)
1323 _DifferenceTp __length
= _GLIBCXX_PARALLEL_LENGTH(*__raii
);
1325 (*__raii
).first
+= __pieces
[__num_threads
- 1][__k
++].second
;
1331 return __target
+ __length
;
1335 * @brief Multiway Merge Frontend.
1337 * Merge the sequences specified by seqs_begin and __seqs_end into
1338 * __target. __seqs_begin and __seqs_end must point to a sequence of
1339 * pairs. These pairs must contain an iterator to the beginning
1340 * of a sequence in their first entry and an iterator the _M_end of
1341 * the same sequence in their second entry.
1343 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1344 * that breaks ties by sequence number but is slower.
1346 * The first entries of the pairs (i.e. the begin iterators) will be moved
1349 * The output sequence has to provide enough space for all elements
1350 * that are written to it.
1352 * This function will merge the input sequences:
1355 * - parallel, depending on the input size and Settings
1356 * - using sampling for splitting
1357 * - not using sentinels
1362 * int sequences[10][10];
1363 * for (int __i = 0; __i < 10; ++__i)
1364 * for (int __j = 0; __i < 10; ++__j)
1365 * sequences[__i][__j] = __j;
1368 * std::vector<std::pair<int*> > seqs;
1369 * for (int __i = 0; __i < 10; ++__i)
1370 * { seqs.push(std::make_pair<int*>(sequences[__i],
1371 * sequences[__i] + 10)) }
1373 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1376 * @see stable_multiway_merge
1378 * @pre All input sequences must be sorted.
1379 * @pre Target must provide enough space to merge out length elements or
1380 * the number of elements in all sequences, whichever is smaller.
1382 * @post [__target, return __value) contains merged __elements from the
1384 * @post return __value - __target = min(__length, number of elements in all
1387 * @param _RAIterPairIterator iterator over sequence
1388 * of pairs of iterators
1389 * @param _RAIterOut iterator over target sequence
1390 * @param _DifferenceTp difference type for the sequence
1391 * @param _Compare strict weak ordering type to compare elements
1394 * @param __seqs_begin __begin of sequence __sequence
1395 * @param __seqs_end _M_end of sequence __sequence
1396 * @param __target target sequence to merge to.
1397 * @param __comp strict weak ordering to use for element comparison.
1398 * @param __length Maximum length to merge, possibly larger than the
1399 * number of elements available.
1401 * @return _M_end iterator of output sequence
1405 template<typename _RAIterPairIterator
,
1406 typename _RAIterOut
,
1407 typename _DifferenceTp
,
1410 multiway_merge(_RAIterPairIterator __seqs_begin
,
1411 _RAIterPairIterator __seqs_end
,
1412 _RAIterOut __target
,
1413 _DifferenceTp __length
, _Compare __comp
,
1414 __gnu_parallel::sequential_tag
)
1416 typedef _DifferenceTp _DifferenceType
;
1417 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1419 // catch special case: no sequences
1420 if (__seqs_begin
== __seqs_end
)
1423 // Execute multiway merge *sequentially*.
1424 return __sequential_multiway_merge
1425 </* __stable = */ false, /* __sentinels = */ false>
1426 (__seqs_begin
, __seqs_end
, __target
,
1427 *(__seqs_begin
->second
), __length
, __comp
);
1431 template<typename _RAIterPairIterator
,
1432 typename _RAIterOut
,
1433 typename _DifferenceTp
,
1436 multiway_merge(_RAIterPairIterator __seqs_begin
,
1437 _RAIterPairIterator __seqs_end
,
1438 _RAIterOut __target
,
1439 _DifferenceTp __length
, _Compare __comp
,
1440 __gnu_parallel::exact_tag __tag
)
1442 typedef _DifferenceTp _DifferenceType
;
1443 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1445 // catch special case: no sequences
1446 if (__seqs_begin
== __seqs_end
)
1449 // Execute merge; maybe parallel, depending on the number of merged
1450 // elements and the number of sequences and global thresholds in
1452 if ((__seqs_end
- __seqs_begin
> 1)
1453 && _GLIBCXX_PARALLEL_CONDITION(
1454 ((__seqs_end
- __seqs_begin
) >=
1455 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1456 && ((_SequenceIndex
)__length
>=
1457 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1458 return parallel_multiway_merge
1459 </* __stable = */ false, /* __sentinels = */ false>
1460 (__seqs_begin
, __seqs_end
, __target
,
1461 multiway_merge_exact_splitting
</* __stable = */ false,
1462 typename
std::iterator_traits
<_RAIterPairIterator
>
1463 ::value_type
*, _Compare
, _DifferenceTp
>,
1464 static_cast<_DifferenceType
>(__length
), __comp
,
1465 __tag
.__get_num_threads());
1467 return __sequential_multiway_merge
1468 </* __stable = */ false, /* __sentinels = */ false>
1469 (__seqs_begin
, __seqs_end
, __target
,
1470 *(__seqs_begin
->second
), __length
, __comp
);
1474 template<typename _RAIterPairIterator
,
1475 typename _RAIterOut
,
1476 typename _DifferenceTp
,
1479 multiway_merge(_RAIterPairIterator __seqs_begin
,
1480 _RAIterPairIterator __seqs_end
,
1481 _RAIterOut __target
,
1482 _DifferenceTp __length
, _Compare __comp
,
1483 __gnu_parallel::sampling_tag __tag
)
1485 typedef _DifferenceTp _DifferenceType
;
1486 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1488 // catch special case: no sequences
1489 if (__seqs_begin
== __seqs_end
)
1492 // Execute merge; maybe parallel, depending on the number of merged
1493 // elements and the number of sequences and global thresholds in
1495 if ((__seqs_end
- __seqs_begin
> 1)
1496 && _GLIBCXX_PARALLEL_CONDITION(
1497 ((__seqs_end
- __seqs_begin
) >=
1498 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1499 && ((_SequenceIndex
)__length
>=
1500 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1501 return parallel_multiway_merge
1502 </* __stable = */ false, /* __sentinels = */ false>
1503 (__seqs_begin
, __seqs_end
, __target
,
1504 multiway_merge_exact_splitting
</* __stable = */ false,
1505 typename
std::iterator_traits
<_RAIterPairIterator
>
1506 ::value_type
*, _Compare
, _DifferenceTp
>,
1507 static_cast<_DifferenceType
>(__length
), __comp
,
1508 __tag
.__get_num_threads());
1510 return __sequential_multiway_merge
1511 </* __stable = */ false, /* __sentinels = */ false>
1512 (__seqs_begin
, __seqs_end
, __target
,
1513 *(__seqs_begin
->second
), __length
, __comp
);
1517 template<typename _RAIterPairIterator
,
1518 typename _RAIterOut
,
1519 typename _DifferenceTp
,
1522 multiway_merge(_RAIterPairIterator __seqs_begin
,
1523 _RAIterPairIterator __seqs_end
,
1524 _RAIterOut __target
,
1525 _DifferenceTp __length
, _Compare __comp
,
1526 parallel_tag __tag
= parallel_tag(0))
1527 { return multiway_merge(__seqs_begin
, __seqs_end
, __target
, __length
,
1528 __comp
, exact_tag(__tag
.__get_num_threads())); }
1531 template<typename _RAIterPairIterator
,
1532 typename _RAIterOut
,
1533 typename _DifferenceTp
,
1536 multiway_merge(_RAIterPairIterator __seqs_begin
,
1537 _RAIterPairIterator __seqs_end
,
1538 _RAIterOut __target
,
1539 _DifferenceTp __length
, _Compare __comp
,
1540 default_parallel_tag __tag
)
1541 { return multiway_merge(__seqs_begin
, __seqs_end
, __target
, __length
,
1542 __comp
, exact_tag(__tag
.__get_num_threads())); }
1544 // stable_multiway_merge
1546 template<typename _RAIterPairIterator
,
1547 typename _RAIterOut
,
1548 typename _DifferenceTp
,
1551 stable_multiway_merge(_RAIterPairIterator __seqs_begin
,
1552 _RAIterPairIterator __seqs_end
,
1553 _RAIterOut __target
,
1554 _DifferenceTp __length
, _Compare __comp
,
1555 __gnu_parallel::sequential_tag
)
1557 typedef _DifferenceTp _DifferenceType
;
1558 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1560 // catch special case: no sequences
1561 if (__seqs_begin
== __seqs_end
)
1564 // Execute multiway merge *sequentially*.
1565 return __sequential_multiway_merge
1566 </* __stable = */ true, /* __sentinels = */ false>
1567 (__seqs_begin
, __seqs_end
, __target
,
1568 *(__seqs_begin
->second
), __length
, __comp
);
1572 template<typename _RAIterPairIterator
,
1573 typename _RAIterOut
,
1574 typename _DifferenceTp
,
1577 stable_multiway_merge(_RAIterPairIterator __seqs_begin
,
1578 _RAIterPairIterator __seqs_end
,
1579 _RAIterOut __target
,
1580 _DifferenceTp __length
, _Compare __comp
,
1581 __gnu_parallel::exact_tag __tag
)
1583 typedef _DifferenceTp _DifferenceType
;
1584 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1586 // catch special case: no sequences
1587 if (__seqs_begin
== __seqs_end
)
1590 // Execute merge; maybe parallel, depending on the number of merged
1591 // elements and the number of sequences and global thresholds in
1593 if ((__seqs_end
- __seqs_begin
> 1)
1594 && _GLIBCXX_PARALLEL_CONDITION(
1595 ((__seqs_end
- __seqs_begin
) >=
1596 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1597 && ((_SequenceIndex
)__length
>=
1598 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1599 return parallel_multiway_merge
1600 </* __stable = */ true, /* __sentinels = */ false>
1601 (__seqs_begin
, __seqs_end
, __target
,
1602 multiway_merge_exact_splitting
</* __stable = */ true,
1603 typename
std::iterator_traits
<_RAIterPairIterator
>
1604 ::value_type
*, _Compare
, _DifferenceTp
>,
1605 static_cast<_DifferenceType
>(__length
), __comp
,
1606 __tag
.__get_num_threads());
1608 return __sequential_multiway_merge
1609 </* __stable = */ true, /* __sentinels = */ false>
1610 (__seqs_begin
, __seqs_end
, __target
,
1611 *(__seqs_begin
->second
), __length
, __comp
);
1615 template<typename _RAIterPairIterator
,
1616 typename _RAIterOut
,
1617 typename _DifferenceTp
,
1620 stable_multiway_merge(_RAIterPairIterator __seqs_begin
,
1621 _RAIterPairIterator __seqs_end
,
1622 _RAIterOut __target
,
1623 _DifferenceTp __length
, _Compare __comp
,
1626 typedef _DifferenceTp _DifferenceType
;
1627 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1629 // catch special case: no sequences
1630 if (__seqs_begin
== __seqs_end
)
1633 // Execute merge; maybe parallel, depending on the number of merged
1634 // elements and the number of sequences and global thresholds in
1636 if ((__seqs_end
- __seqs_begin
> 1)
1637 && _GLIBCXX_PARALLEL_CONDITION(
1638 ((__seqs_end
- __seqs_begin
) >=
1639 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1640 && ((_SequenceIndex
)__length
>=
1641 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1642 return parallel_multiway_merge
1643 </* __stable = */ true, /* __sentinels = */ false>
1644 (__seqs_begin
, __seqs_end
, __target
,
1645 multiway_merge_sampling_splitting
</* __stable = */ true,
1646 typename
std::iterator_traits
<_RAIterPairIterator
>
1647 ::value_type
*, _Compare
, _DifferenceTp
>,
1648 static_cast<_DifferenceType
>(__length
), __comp
,
1649 __tag
.__get_num_threads());
1651 return __sequential_multiway_merge
1652 </* __stable = */ true, /* __sentinels = */ false>
1653 (__seqs_begin
, __seqs_end
, __target
,
1654 *(__seqs_begin
->second
), __length
, __comp
);
1658 template<typename _RAIterPairIterator
,
1659 typename _RAIterOut
,
1660 typename _DifferenceTp
,
1663 stable_multiway_merge(_RAIterPairIterator __seqs_begin
,
1664 _RAIterPairIterator __seqs_end
,
1665 _RAIterOut __target
,
1666 _DifferenceTp __length
, _Compare __comp
,
1667 parallel_tag __tag
= parallel_tag(0))
1669 return stable_multiway_merge
1670 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
1671 exact_tag(__tag
.__get_num_threads()));
1675 template<typename _RAIterPairIterator
,
1676 typename _RAIterOut
,
1677 typename _DifferenceTp
,
1680 stable_multiway_merge(_RAIterPairIterator __seqs_begin
,
1681 _RAIterPairIterator __seqs_end
,
1682 _RAIterOut __target
,
1683 _DifferenceTp __length
, _Compare __comp
,
1684 default_parallel_tag __tag
)
1686 return stable_multiway_merge
1687 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
1688 exact_tag(__tag
.__get_num_threads()));
1692 * @brief Multiway Merge Frontend.
1694 * Merge the sequences specified by seqs_begin and __seqs_end into
1695 * __target. __seqs_begin and __seqs_end must point to a sequence of
1696 * pairs. These pairs must contain an iterator to the beginning
1697 * of a sequence in their first entry and an iterator the _M_end of
1698 * the same sequence in their second entry.
1700 * Ties are broken arbitrarily. See stable_multiway_merge for a variant
1701 * that breaks ties by sequence number but is slower.
1703 * The first entries of the pairs (i.e. the begin iterators) will be moved
1704 * forward accordingly.
1706 * The output sequence has to provide enough space for all elements
1707 * that are written to it.
1709 * This function will merge the input sequences:
1712 * - parallel, depending on the input size and Settings
1713 * - using sampling for splitting
1716 * You have to take care that the element the _M_end iterator points to is
1717 * readable and contains a value that is greater than any other non-sentinel
1718 * value in all sequences.
1723 * int sequences[10][11];
1724 * for (int __i = 0; __i < 10; ++__i)
1725 * for (int __j = 0; __i < 11; ++__j)
1726 * sequences[__i][__j] = __j; // __last one is sentinel!
1729 * std::vector<std::pair<int*> > seqs;
1730 * for (int __i = 0; __i < 10; ++__i)
1731 * { seqs.push(std::make_pair<int*>(sequences[__i],
1732 * sequences[__i] + 10)) }
1734 * multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
1737 * @pre All input sequences must be sorted.
1738 * @pre Target must provide enough space to merge out length elements or
1739 * the number of elements in all sequences, whichever is smaller.
1740 * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
1741 * marker of the sequence, but also reference the one more __sentinel
1744 * @post [__target, return __value) contains merged __elements from the
1746 * @post return __value - __target = min(__length, number of elements in all
1749 * @see stable_multiway_merge_sentinels
1751 * @param _RAIterPairIterator iterator over sequence
1752 * of pairs of iterators
1753 * @param _RAIterOut iterator over target sequence
1754 * @param _DifferenceTp difference type for the sequence
1755 * @param _Compare strict weak ordering type to compare elements
1758 * @param __seqs_begin __begin of sequence __sequence
1759 * @param __seqs_end _M_end of sequence __sequence
1760 * @param __target target sequence to merge to.
1761 * @param __comp strict weak ordering to use for element comparison.
1762 * @param __length Maximum length to merge, possibly larger than the
1763 * number of elements available.
1765 * @return _M_end iterator of output sequence
1767 // multiway_merge_sentinels
1769 template<typename _RAIterPairIterator
,
1770 typename _RAIterOut
,
1771 typename _DifferenceTp
,
1774 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1775 _RAIterPairIterator __seqs_end
,
1776 _RAIterOut __target
,
1777 _DifferenceTp __length
, _Compare __comp
,
1778 __gnu_parallel::sequential_tag
)
1780 typedef _DifferenceTp _DifferenceType
;
1781 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1783 // catch special case: no sequences
1784 if (__seqs_begin
== __seqs_end
)
1787 // Execute multiway merge *sequentially*.
1788 return __sequential_multiway_merge
1789 </* __stable = */ false, /* __sentinels = */ true>
1790 (__seqs_begin
, __seqs_end
,
1791 __target
, *(__seqs_begin
->second
), __length
, __comp
);
1795 template<typename _RAIterPairIterator
,
1796 typename _RAIterOut
,
1797 typename _DifferenceTp
,
1800 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1801 _RAIterPairIterator __seqs_end
,
1802 _RAIterOut __target
,
1803 _DifferenceTp __length
, _Compare __comp
,
1804 __gnu_parallel::exact_tag __tag
)
1806 typedef _DifferenceTp _DifferenceType
;
1807 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1809 // catch special case: no sequences
1810 if (__seqs_begin
== __seqs_end
)
1813 // Execute merge; maybe parallel, depending on the number of merged
1814 // elements and the number of sequences and global thresholds in
1816 if ((__seqs_end
- __seqs_begin
> 1)
1817 && _GLIBCXX_PARALLEL_CONDITION(
1818 ((__seqs_end
- __seqs_begin
) >=
1819 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1820 && ((_SequenceIndex
)__length
>=
1821 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1822 return parallel_multiway_merge
1823 </* __stable = */ false, /* __sentinels = */ true>
1824 (__seqs_begin
, __seqs_end
, __target
,
1825 multiway_merge_exact_splitting
</* __stable = */ false,
1826 typename
std::iterator_traits
<_RAIterPairIterator
>
1827 ::value_type
*, _Compare
, _DifferenceTp
>,
1828 static_cast<_DifferenceType
>(__length
), __comp
,
1829 __tag
.__get_num_threads());
1831 return __sequential_multiway_merge
1832 </* __stable = */ false, /* __sentinels = */ true>
1833 (__seqs_begin
, __seqs_end
, __target
,
1834 *(__seqs_begin
->second
), __length
, __comp
);
1838 template<typename _RAIterPairIterator
,
1839 typename _RAIterOut
,
1840 typename _DifferenceTp
,
1843 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1844 _RAIterPairIterator __seqs_end
,
1845 _RAIterOut __target
,
1846 _DifferenceTp __length
, _Compare __comp
,
1849 typedef _DifferenceTp _DifferenceType
;
1850 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1852 // catch special case: no sequences
1853 if (__seqs_begin
== __seqs_end
)
1856 // Execute merge; maybe parallel, depending on the number of merged
1857 // elements and the number of sequences and global thresholds in
1859 if ((__seqs_end
- __seqs_begin
> 1)
1860 && _GLIBCXX_PARALLEL_CONDITION(
1861 ((__seqs_end
- __seqs_begin
) >=
1862 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1863 && ((_SequenceIndex
)__length
>=
1864 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1865 return parallel_multiway_merge
1866 </* __stable = */ false, /* __sentinels = */ true>
1867 (__seqs_begin
, __seqs_end
, __target
,
1868 multiway_merge_sampling_splitting
</* __stable = */ false,
1869 typename
std::iterator_traits
<_RAIterPairIterator
>
1870 ::value_type
*, _Compare
, _DifferenceTp
>,
1871 static_cast<_DifferenceType
>(__length
), __comp
,
1872 __tag
.__get_num_threads());
1874 return __sequential_multiway_merge
1875 </* __stable = */false, /* __sentinels = */ true>(
1876 __seqs_begin
, __seqs_end
, __target
,
1877 *(__seqs_begin
->second
), __length
, __comp
);
1881 template<typename _RAIterPairIterator
,
1882 typename _RAIterOut
,
1883 typename _DifferenceTp
,
1886 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1887 _RAIterPairIterator __seqs_end
,
1888 _RAIterOut __target
,
1889 _DifferenceTp __length
, _Compare __comp
,
1890 parallel_tag __tag
= parallel_tag(0))
1892 return multiway_merge_sentinels
1893 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
1894 exact_tag(__tag
.__get_num_threads()));
1898 template<typename _RAIterPairIterator
,
1899 typename _RAIterOut
,
1900 typename _DifferenceTp
,
1903 multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1904 _RAIterPairIterator __seqs_end
,
1905 _RAIterOut __target
,
1906 _DifferenceTp __length
, _Compare __comp
,
1907 default_parallel_tag __tag
)
1909 return multiway_merge_sentinels
1910 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
1911 exact_tag(__tag
.__get_num_threads()));
1914 // stable_multiway_merge_sentinels
1916 template<typename _RAIterPairIterator
,
1917 typename _RAIterOut
,
1918 typename _DifferenceTp
,
1921 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1922 _RAIterPairIterator __seqs_end
,
1923 _RAIterOut __target
,
1924 _DifferenceTp __length
, _Compare __comp
,
1925 __gnu_parallel::sequential_tag
)
1927 typedef _DifferenceTp _DifferenceType
;
1928 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1930 // catch special case: no sequences
1931 if (__seqs_begin
== __seqs_end
)
1934 // Execute multiway merge *sequentially*.
1935 return __sequential_multiway_merge
1936 </* __stable = */ true, /* __sentinels = */ true>
1937 (__seqs_begin
, __seqs_end
, __target
,
1938 *(__seqs_begin
->second
), __length
, __comp
);
1942 template<typename _RAIterPairIterator
,
1943 typename _RAIterOut
,
1944 typename _DifferenceTp
,
1947 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1948 _RAIterPairIterator __seqs_end
,
1949 _RAIterOut __target
,
1950 _DifferenceTp __length
, _Compare __comp
,
1951 __gnu_parallel::exact_tag __tag
)
1953 typedef _DifferenceTp _DifferenceType
;
1954 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
1956 // catch special case: no sequences
1957 if (__seqs_begin
== __seqs_end
)
1960 // Execute merge; maybe parallel, depending on the number of merged
1961 // elements and the number of sequences and global thresholds in
1963 if ((__seqs_end
- __seqs_begin
> 1)
1964 && _GLIBCXX_PARALLEL_CONDITION(
1965 ((__seqs_end
- __seqs_begin
) >=
1966 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
1967 && ((_SequenceIndex
)__length
>=
1968 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
1969 return parallel_multiway_merge
1970 </* __stable = */ true, /* __sentinels = */ true>
1971 (__seqs_begin
, __seqs_end
, __target
,
1972 multiway_merge_exact_splitting
</* __stable = */ true,
1973 typename
std::iterator_traits
<_RAIterPairIterator
>
1974 ::value_type
*, _Compare
, _DifferenceTp
>,
1975 static_cast<_DifferenceType
>(__length
), __comp
,
1976 __tag
.__get_num_threads());
1978 return __sequential_multiway_merge
1979 </* __stable = */ true, /* __sentinels = */ true>
1980 (__seqs_begin
, __seqs_end
, __target
,
1981 *(__seqs_begin
->second
), __length
, __comp
);
1985 template<typename _RAIterPairIterator
,
1986 typename _RAIterOut
,
1987 typename _DifferenceTp
,
1990 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
1991 _RAIterPairIterator __seqs_end
,
1992 _RAIterOut __target
,
1993 _DifferenceTp __length
,
1997 typedef _DifferenceTp _DifferenceType
;
1998 _GLIBCXX_CALL(__seqs_end
- __seqs_begin
)
2000 // catch special case: no sequences
2001 if (__seqs_begin
== __seqs_end
)
2004 // Execute merge; maybe parallel, depending on the number of merged
2005 // elements and the number of sequences and global thresholds in
2007 if ((__seqs_end
- __seqs_begin
> 1)
2008 && _GLIBCXX_PARALLEL_CONDITION(
2009 ((__seqs_end
- __seqs_begin
) >=
2010 __gnu_parallel::_Settings::get().multiway_merge_minimal_k
)
2011 && ((_SequenceIndex
)__length
>=
2012 __gnu_parallel::_Settings::get().multiway_merge_minimal_n
)))
2013 return parallel_multiway_merge
2014 </* __stable = */ true, /* __sentinels = */ true>
2015 (__seqs_begin
, __seqs_end
, __target
,
2016 multiway_merge_sampling_splitting
</* __stable = */ true,
2017 typename
std::iterator_traits
<_RAIterPairIterator
>
2018 ::value_type
*, _Compare
, _DifferenceTp
>,
2019 static_cast<_DifferenceType
>(__length
), __comp
,
2020 __tag
.__get_num_threads());
2022 return __sequential_multiway_merge
2023 </* __stable = */ true, /* __sentinels = */ true>
2024 (__seqs_begin
, __seqs_end
, __target
,
2025 *(__seqs_begin
->second
), __length
, __comp
);
2029 template<typename _RAIterPairIterator
,
2030 typename _RAIterOut
,
2031 typename _DifferenceTp
,
2034 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
2035 _RAIterPairIterator __seqs_end
,
2036 _RAIterOut __target
,
2037 _DifferenceTp __length
,
2039 parallel_tag __tag
= parallel_tag(0))
2041 return stable_multiway_merge_sentinels
2042 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
2043 exact_tag(__tag
.__get_num_threads()));
2047 template<typename _RAIterPairIterator
,
2048 typename _RAIterOut
,
2049 typename _DifferenceTp
,
2052 stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin
,
2053 _RAIterPairIterator __seqs_end
,
2054 _RAIterOut __target
,
2055 _DifferenceTp __length
, _Compare __comp
,
2056 default_parallel_tag __tag
)
2058 return stable_multiway_merge_sentinels
2059 (__seqs_begin
, __seqs_end
, __target
, __length
, __comp
,
2060 exact_tag(__tag
.__get_num_threads()));
2062 }; // namespace __gnu_parallel
2064 #endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */