libstdc++
multiway_merge.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2020 Free Software Foundation, Inc.
4 //
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
9 // version.
10 
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.
15 
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.
19 
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/>.
24 
25 /** @file parallel/multiway_merge.h
26 * @brief Implementation of sequential and parallel multiway merge.
27 *
28 * Explanations on the high-speed merging routines in the appendix of
29 *
30 * P. Sanders.
31 * Fast priority queues for cached memory.
32 * ACM Journal of Experimental Algorithmics, 5, 2000.
33 *
34 * This file is a GNU parallel extension to the Standard C++ Library.
35 */
36 
37 // Written by Johannes Singler and Manuel Holtgrewe.
38 
39 #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
40 #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
41 
42 #include <vector>
43 
44 #include <bits/stl_algo.h>
45 #include <parallel/features.h>
46 #include <parallel/parallel.h>
47 #include <parallel/losertree.h>
48 #include <parallel/multiseq_selection.h>
49 #if _GLIBCXX_PARALLEL_ASSERTIONS
50 #include <parallel/checkers.h>
51 #endif
52 
53 /** @brief Length of a sequence described by a pair of iterators. */
54 #define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
55 
56 namespace __gnu_parallel
57 {
58  template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
59  typename _DifferenceTp, typename _Compare>
60  _OutputIterator
61  __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2,
62  _OutputIterator, _DifferenceTp, _Compare);
63 
64  /** @brief _Iterator wrapper supporting an implicit supremum at the end
65  * of the sequence, dominating all comparisons.
66  *
67  * The implicit supremum comes with a performance cost.
68  *
69  * Deriving from _RAIter is not possible since
70  * _RAIter need not be a class.
71  */
72  template<typename _RAIter, typename _Compare>
73  class _GuardedIterator
74  {
75  private:
76  /** @brief Current iterator __position. */
77  _RAIter _M_current;
78 
79  /** @brief End iterator of the sequence. */
80  _RAIter _M_end;
81 
82  /** @brief _Compare. */
83  _Compare& __comp;
84 
85  public:
86  /** @brief Constructor. Sets iterator to beginning of sequence.
87  * @param __begin Begin iterator of sequence.
88  * @param __end End iterator of sequence.
89  * @param __comp Comparator provided for associated overloaded
90  * compare operators. */
91  _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
92  : _M_current(__begin), _M_end(__end), __comp(__comp)
93  { }
94 
95  /** @brief Pre-increment operator.
96  * @return This. */
97  _GuardedIterator<_RAIter, _Compare>&
98  operator++()
99  {
100  ++_M_current;
101  return *this;
102  }
103 
104  /** @brief Dereference operator.
105  * @return Referenced element. */
106  typename std::iterator_traits<_RAIter>::value_type&
107  operator*()
108  { return *_M_current; }
109 
110  /** @brief Convert to wrapped iterator.
111  * @return Wrapped iterator. */
112  operator _RAIter()
113  { return _M_current; }
114 
115  /** @brief Compare two elements referenced by guarded iterators.
116  * @param __bi1 First iterator.
117  * @param __bi2 Second iterator.
118  * @return @c true if less. */
119  friend bool
120  operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
121  _GuardedIterator<_RAIter, _Compare>& __bi2)
122  {
123  if (__bi1._M_current == __bi1._M_end) // __bi1 is sup
124  return __bi2._M_current == __bi2._M_end; // __bi2 is not sup
125  if (__bi2._M_current == __bi2._M_end) // __bi2 is sup
126  return true;
127  return (__bi1.__comp)(*__bi1, *__bi2); // normal compare
128  }
129 
130  /** @brief Compare two elements referenced by guarded iterators.
131  * @param __bi1 First iterator.
132  * @param __bi2 Second iterator.
133  * @return @c True if less equal. */
134  friend bool
135  operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
136  _GuardedIterator<_RAIter, _Compare>& __bi2)
137  {
138  if (__bi2._M_current == __bi2._M_end) // __bi1 is sup
139  return __bi1._M_current != __bi1._M_end; // __bi2 is not sup
140  if (__bi1._M_current == __bi1._M_end) // __bi2 is sup
141  return false;
142  return !(__bi1.__comp)(*__bi2, *__bi1); // normal compare
143  }
144  };
145 
146  template<typename _RAIter, typename _Compare>
147  class _UnguardedIterator
148  {
149  private:
150  /** @brief Current iterator __position. */
151  _RAIter _M_current;
152  /** @brief _Compare. */
153  _Compare& __comp;
154 
155  public:
156  /** @brief Constructor. Sets iterator to beginning of sequence.
157  * @param __begin Begin iterator of sequence.
158  * @param __end Unused, only for compatibility.
159  * @param __comp Unused, only for compatibility. */
160  _UnguardedIterator(_RAIter __begin,
161  _RAIter /* __end */, _Compare& __comp)
162  : _M_current(__begin), __comp(__comp)
163  { }
164 
165  /** @brief Pre-increment operator.
166  * @return This. */
167  _UnguardedIterator<_RAIter, _Compare>&
168  operator++()
169  {
170  ++_M_current;
171  return *this;
172  }
173 
174  /** @brief Dereference operator.
175  * @return Referenced element. */
176  typename std::iterator_traits<_RAIter>::value_type&
177  operator*()
178  { return *_M_current; }
179 
180  /** @brief Convert to wrapped iterator.
181  * @return Wrapped iterator. */
182  operator _RAIter()
183  { return _M_current; }
184 
185  /** @brief Compare two elements referenced by unguarded iterators.
186  * @param __bi1 First iterator.
187  * @param __bi2 Second iterator.
188  * @return @c true if less. */
189  friend bool
190  operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
191  _UnguardedIterator<_RAIter, _Compare>& __bi2)
192  {
193  // Normal compare.
194  return (__bi1.__comp)(*__bi1, *__bi2);
195  }
196 
197  /** @brief Compare two elements referenced by unguarded iterators.
198  * @param __bi1 First iterator.
199  * @param __bi2 Second iterator.
200  * @return @c True if less equal. */
201  friend bool
202  operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
203  _UnguardedIterator<_RAIter, _Compare>& __bi2)
204  {
205  // Normal compare.
206  return !(__bi1.__comp)(*__bi2, *__bi1);
207  }
208  };
209 
210  /** @brief Highly efficient 3-way merging procedure.
211  *
212  * Merging is done with the algorithm implementation described by Peter
213  * Sanders. Basically, the idea is to minimize the number of necessary
214  * comparison after merging an element. The implementation trick
215  * that makes this fast is that the order of the sequences is stored
216  * in the instruction pointer (translated into labels in C++).
217  *
218  * This works well for merging up to 4 sequences.
219  *
220  * Note that making the merging stable does @a not come at a
221  * performance hit.
222  *
223  * Whether the merging is done guarded or unguarded is selected by the
224  * used iterator class.
225  *
226  * @param __seqs_begin Begin iterator of iterator pair input sequence.
227  * @param __seqs_end End iterator of iterator pair input sequence.
228  * @param __target Begin iterator of output sequence.
229  * @param __comp Comparator.
230  * @param __length Maximum length to merge, less equal than the
231  * total number of elements available.
232  *
233  * @return End iterator of output sequence.
234  */
235  template<template<typename _RAI, typename _Cp> class iterator,
236  typename _RAIterIterator,
237  typename _RAIter3,
238  typename _DifferenceTp,
239  typename _Compare>
240  _RAIter3
241  multiway_merge_3_variant(_RAIterIterator __seqs_begin,
242  _RAIterIterator __seqs_end,
243  _RAIter3 __target,
244  _DifferenceTp __length, _Compare __comp)
245  {
246  _GLIBCXX_CALL(__length);
247 
248  typedef _DifferenceTp _DifferenceType;
249 
250  typedef typename std::iterator_traits<_RAIterIterator>
251  ::value_type::first_type
252  _RAIter1;
253  typedef typename std::iterator_traits<_RAIter1>::value_type
254  _ValueType;
255 
256  if (__length == 0)
257  return __target;
258 
259 #if _GLIBCXX_PARALLEL_ASSERTIONS
260  _DifferenceTp __orig_length = __length;
261 #endif
262 
263  iterator<_RAIter1, _Compare>
264  __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
265  __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
266  __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
267 
268  if (__seq0 <= __seq1)
269  {
270  if (__seq1 <= __seq2)
271  goto __s012;
272  else
273  if (__seq2 < __seq0)
274  goto __s201;
275  else
276  goto __s021;
277  }
278  else
279  {
280  if (__seq1 <= __seq2)
281  {
282  if (__seq0 <= __seq2)
283  goto __s102;
284  else
285  goto __s120;
286  }
287  else
288  goto __s210;
289  }
290 #define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
291  __s ## __a ## __b ## __c : \
292  *__target = *__seq ## __a; \
293  ++__target; \
294  --__length; \
295  ++__seq ## __a; \
296  if (__length == 0) goto __finish; \
297  if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
298  if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
299  goto __s ## __b ## __c ## __a;
300 
301  _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
302  _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
303  _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
304  _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
305  _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
306  _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
307 
308 #undef _GLIBCXX_PARALLEL_MERGE_3_CASE
309 
310  __finish:
311  ;
312 
313 #if _GLIBCXX_PARALLEL_ASSERTIONS
314  _GLIBCXX_PARALLEL_ASSERT(
315  ((_RAIter1)__seq0 - __seqs_begin[0].first) +
316  ((_RAIter1)__seq1 - __seqs_begin[1].first) +
317  ((_RAIter1)__seq2 - __seqs_begin[2].first)
318  == __orig_length);
319 #endif
320 
321  __seqs_begin[0].first = __seq0;
322  __seqs_begin[1].first = __seq1;
323  __seqs_begin[2].first = __seq2;
324 
325  return __target;
326  }
327 
328  /**
329  * @brief Highly efficient 4-way merging procedure.
330  *
331  * Merging is done with the algorithm implementation described by Peter
332  * Sanders. Basically, the idea is to minimize the number of necessary
333  * comparison after merging an element. The implementation trick
334  * that makes this fast is that the order of the sequences is stored
335  * in the instruction pointer (translated into goto labels in C++).
336  *
337  * This works well for merging up to 4 sequences.
338  *
339  * Note that making the merging stable does @a not come at a
340  * performance hit.
341  *
342  * Whether the merging is done guarded or unguarded is selected by the
343  * used iterator class.
344  *
345  * @param __seqs_begin Begin iterator of iterator pair input sequence.
346  * @param __seqs_end End iterator of iterator pair input sequence.
347  * @param __target Begin iterator of output sequence.
348  * @param __comp Comparator.
349  * @param __length Maximum length to merge, less equal than the
350  * total number of elements available.
351  *
352  * @return End iterator of output sequence.
353  */
354  template<template<typename _RAI, typename _Cp> class iterator,
355  typename _RAIterIterator,
356  typename _RAIter3,
357  typename _DifferenceTp,
358  typename _Compare>
359  _RAIter3
360  multiway_merge_4_variant(_RAIterIterator __seqs_begin,
361  _RAIterIterator __seqs_end,
362  _RAIter3 __target,
363  _DifferenceTp __length, _Compare __comp)
364  {
365  _GLIBCXX_CALL(__length);
366  typedef _DifferenceTp _DifferenceType;
367 
368  typedef typename std::iterator_traits<_RAIterIterator>
369  ::value_type::first_type
370  _RAIter1;
371  typedef typename std::iterator_traits<_RAIter1>::value_type
372  _ValueType;
373 
374  iterator<_RAIter1, _Compare>
375  __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
376  __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
377  __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
378  __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
379 
380 #define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
381  if (__seq ## __d < __seq ## __a) \
382  goto __s ## __d ## __a ## __b ## __c; \
383  if (__seq ## __d < __seq ## __b) \
384  goto __s ## __a ## __d ## __b ## __c; \
385  if (__seq ## __d < __seq ## __c) \
386  goto __s ## __a ## __b ## __d ## __c; \
387  goto __s ## __a ## __b ## __c ## __d; }
388 
389  if (__seq0 <= __seq1)
390  {
391  if (__seq1 <= __seq2)
392  _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
393  else
394  if (__seq2 < __seq0)
395  _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
396  else
397  _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
398  }
399  else
400  {
401  if (__seq1 <= __seq2)
402  {
403  if (__seq0 <= __seq2)
404  _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
405  else
406  _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
407  }
408  else
409  _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
410  }
411 
412 #define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
413  __c0, __c1, __c2) \
414  __s ## __a ## __b ## __c ## __d: \
415  if (__length == 0) goto __finish; \
416  *__target = *__seq ## __a; \
417  ++__target; \
418  --__length; \
419  ++__seq ## __a; \
420  if (__seq ## __a __c0 __seq ## __b) \
421  goto __s ## __a ## __b ## __c ## __d; \
422  if (__seq ## __a __c1 __seq ## __c) \
423  goto __s ## __b ## __a ## __c ## __d; \
424  if (__seq ## __a __c2 __seq ## __d) \
425  goto __s ## __b ## __c ## __a ## __d; \
426  goto __s ## __b ## __c ## __d ## __a;
427 
428  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
429  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
430  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
431  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
432  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
433  _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
434  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
435  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
436  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
437  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
438  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
439  _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
440  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
441  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
442  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
443  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
444  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
445  _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
446  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
447  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
448  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
449  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
450  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
451  _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
452 
453 #undef _GLIBCXX_PARALLEL_MERGE_4_CASE
454 #undef _GLIBCXX_PARALLEL_DECISION
455 
456  __finish:
457  ;
458 
459  __seqs_begin[0].first = __seq0;
460  __seqs_begin[1].first = __seq1;
461  __seqs_begin[2].first = __seq2;
462  __seqs_begin[3].first = __seq3;
463 
464  return __target;
465  }
466 
467  /** @brief Multi-way merging procedure for a high branching factor,
468  * guarded case.
469  *
470  * This merging variant uses a LoserTree class as selected by <tt>_LT</tt>.
471  *
472  * Stability is selected through the used LoserTree class <tt>_LT</tt>.
473  *
474  * At least one non-empty sequence is required.
475  *
476  * @param __seqs_begin Begin iterator of iterator pair input sequence.
477  * @param __seqs_end End iterator of iterator pair input sequence.
478  * @param __target Begin iterator of output sequence.
479  * @param __comp Comparator.
480  * @param __length Maximum length to merge, less equal than the
481  * total number of elements available.
482  *
483  * @return End iterator of output sequence.
484  */
485  template<typename _LT,
486  typename _RAIterIterator,
487  typename _RAIter3,
488  typename _DifferenceTp,
489  typename _Compare>
490  _RAIter3
491  multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
492  _RAIterIterator __seqs_end,
493  _RAIter3 __target,
494  _DifferenceTp __length, _Compare __comp)
495  {
496  _GLIBCXX_CALL(__length)
497 
498  typedef _DifferenceTp _DifferenceType;
499  typedef typename std::iterator_traits<_RAIterIterator>
500  ::difference_type _SeqNumber;
501  typedef typename std::iterator_traits<_RAIterIterator>
502  ::value_type::first_type
503  _RAIter1;
504  typedef typename std::iterator_traits<_RAIter1>::value_type
505  _ValueType;
506 
507  _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
508 
509  _LT __lt(__k, __comp);
510 
511  // Default value for potentially non-default-constructible types.
512  _ValueType* __arbitrary_element = 0;
513 
514  for (_SeqNumber __t = 0; __t < __k; ++__t)
515  {
516  if(!__arbitrary_element
517  && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
518  __arbitrary_element = &(*__seqs_begin[__t].first);
519  }
520 
521  for (_SeqNumber __t = 0; __t < __k; ++__t)
522  {
523  if (__seqs_begin[__t].first == __seqs_begin[__t].second)
524  __lt.__insert_start(*__arbitrary_element, __t, true);
525  else
526  __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
527  }
528 
529  __lt.__init();
530 
531  _SeqNumber __source;
532 
533  for (_DifferenceType __i = 0; __i < __length; ++__i)
534  {
535  //take out
536  __source = __lt.__get_min_source();
537 
538  *(__target++) = *(__seqs_begin[__source].first++);
539 
540  // Feed.
541  if (__seqs_begin[__source].first == __seqs_begin[__source].second)
542  __lt.__delete_min_insert(*__arbitrary_element, true);
543  else
544  // Replace from same __source.
545  __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
546  }
547 
548  return __target;
549  }
550 
551  /** @brief Multi-way merging procedure for a high branching factor,
552  * unguarded case.
553  *
554  * Merging is done using the LoserTree class <tt>_LT</tt>.
555  *
556  * Stability is selected by the used LoserTrees.
557  *
558  * @pre No input will run out of elements during the merge.
559  *
560  * @param __seqs_begin Begin iterator of iterator pair input sequence.
561  * @param __seqs_end End iterator of iterator pair input sequence.
562  * @param __target Begin iterator of output sequence.
563  * @param __comp Comparator.
564  * @param __length Maximum length to merge, less equal than the
565  * total number of elements available.
566  *
567  * @return End iterator of output sequence.
568  */
569  template<typename _LT,
570  typename _RAIterIterator,
571  typename _RAIter3,
572  typename _DifferenceTp, typename _Compare>
573  _RAIter3
574  multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
575  _RAIterIterator __seqs_end,
576  _RAIter3 __target,
577  const typename std::iterator_traits<typename std::iterator_traits<
578  _RAIterIterator>::value_type::first_type>::value_type&
579  __sentinel,
580  _DifferenceTp __length,
581  _Compare __comp)
582  {
583  _GLIBCXX_CALL(__length)
584  typedef _DifferenceTp _DifferenceType;
585 
586  typedef typename std::iterator_traits<_RAIterIterator>
587  ::difference_type _SeqNumber;
588  typedef typename std::iterator_traits<_RAIterIterator>
589  ::value_type::first_type
590  _RAIter1;
591  typedef typename std::iterator_traits<_RAIter1>::value_type
592  _ValueType;
593 
594  _SeqNumber __k = __seqs_end - __seqs_begin;
595 
596  _LT __lt(__k, __sentinel, __comp);
597 
598  for (_SeqNumber __t = 0; __t < __k; ++__t)
599  {
600 #if _GLIBCXX_PARALLEL_ASSERTIONS
601  _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
602  != __seqs_begin[__t].second);
603 #endif
604  __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
605  }
606 
607  __lt.__init();
608 
609  _SeqNumber __source;
610 
611 #if _GLIBCXX_PARALLEL_ASSERTIONS
612  _DifferenceType __i = 0;
613 #endif
614 
615  _RAIter3 __target_end = __target + __length;
616  while (__target < __target_end)
617  {
618  // Take out.
619  __source = __lt.__get_min_source();
620 
621 #if _GLIBCXX_PARALLEL_ASSERTIONS
622  _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
623  _GLIBCXX_PARALLEL_ASSERT(__i == 0
624  || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
625 #endif
626 
627  // Feed.
628  *(__target++) = *(__seqs_begin[__source].first++);
629 
630 #if _GLIBCXX_PARALLEL_ASSERTIONS
631  ++__i;
632 #endif
633  // Replace from same __source.
634  __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
635  }
636 
637  return __target;
638  }
639 
640 
641  /** @brief Multi-way merging procedure for a high branching factor,
642  * requiring sentinels to exist.
643  *
644  * @tparam _UnguardedLoserTree Loser Tree variant to use for the unguarded
645  * merging.