libstdc++
stl_algo.h
Go to the documentation of this file.
1 // Algorithm implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2019 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
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU 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 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_algo.h
52  * This is an internal header file, included by other library headers.
53  * Do not attempt to use it directly. @headername{algorithm}
54  */
55 
56 #ifndef _STL_ALGO_H
57 #define _STL_ALGO_H 1
58 
59 #include <cstdlib> // for rand
60 #include <bits/algorithmfwd.h>
61 #include <bits/stl_heap.h>
62 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
63 #include <bits/predefined_ops.h>
64 
65 #if __cplusplus >= 201103L
66 #include <bits/uniform_int_dist.h>
67 #endif
68 
69 // See concept_check.h for the __glibcxx_*_requires macros.
70 
71 namespace std _GLIBCXX_VISIBILITY(default)
72 {
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 
75  /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76  template<typename _Iterator, typename _Compare>
77  void
78  __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
79  _Iterator __c, _Compare __comp)
80  {
81  if (__comp(__a, __b))
82  {
83  if (__comp(__b, __c))
84  std::iter_swap(__result, __b);
85  else if (__comp(__a, __c))
86  std::iter_swap(__result, __c);
87  else
88  std::iter_swap(__result, __a);
89  }
90  else if (__comp(__a, __c))
91  std::iter_swap(__result, __a);
92  else if (__comp(__b, __c))
93  std::iter_swap(__result, __c);
94  else
95  std::iter_swap(__result, __b);
96  }
97 
98  /// This is an overload used by find algos for the Input Iterator case.
99  template<typename _InputIterator, typename _Predicate>
100  inline _InputIterator
101  __find_if(_InputIterator __first, _InputIterator __last,
102  _Predicate __pred, input_iterator_tag)
103  {
104  while (__first != __last && !__pred(__first))
105  ++__first;
106  return __first;
107  }
108 
109  /// This is an overload used by find algos for the RAI case.
110  template<typename _RandomAccessIterator, typename _Predicate>
111  _RandomAccessIterator
112  __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
113  _Predicate __pred, random_access_iterator_tag)
114  {
115  typename iterator_traits<_RandomAccessIterator>::difference_type
116  __trip_count = (__last - __first) >> 2;
117 
118  for (; __trip_count > 0; --__trip_count)
119  {
120  if (__pred(__first))
121  return __first;
122  ++__first;
123 
124  if (__pred(__first))
125  return __first;
126  ++__first;
127 
128  if (__pred(__first))
129  return __first;
130  ++__first;
131 
132  if (__pred(__first))
133  return __first;
134  ++__first;
135  }
136 
137  switch (__last - __first)
138  {
139  case 3:
140  if (__pred(__first))
141  return __first;
142  ++__first;
143  case 2:
144  if (__pred(__first))
145  return __first;
146  ++__first;
147  case 1:
148  if (__pred(__first))
149  return __first;
150  ++__first;
151  case 0:
152  default:
153  return __last;
154  }
155  }
156 
157  template<typename _Iterator, typename _Predicate>
158  inline _Iterator
159  __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
160  {
161  return __find_if(__first, __last, __pred,
162  std::__iterator_category(__first));
163  }
164 
165  /// Provided for stable_partition to use.
166  template<typename _InputIterator, typename _Predicate>
167  inline _InputIterator
168  __find_if_not(_InputIterator __first, _InputIterator __last,
169  _Predicate __pred)
170  {
171  return std::__find_if(__first, __last,
172  __gnu_cxx::__ops::__negate(__pred),
173  std::__iterator_category(__first));
174  }
175 
176  /// Like find_if_not(), but uses and updates a count of the
177  /// remaining range length instead of comparing against an end
178  /// iterator.
179  template<typename _InputIterator, typename _Predicate, typename _Distance>
180  _InputIterator
181  __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
182  {
183  for (; __len; --__len, (void) ++__first)
184  if (!__pred(__first))
185  break;
186  return __first;
187  }
188 
189  // set_difference
190  // set_intersection
191  // set_symmetric_difference
192  // set_union
193  // for_each
194  // find
195  // find_if
196  // find_first_of
197  // adjacent_find
198  // count
199  // count_if
200  // search
201 
202  template<typename _ForwardIterator1, typename _ForwardIterator2,
203  typename _BinaryPredicate>
204  _ForwardIterator1
205  __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207  _BinaryPredicate __predicate)
208  {
209  // Test for empty ranges
210  if (__first1 == __last1 || __first2 == __last2)
211  return __first1;
212 
213  // Test for a pattern of length 1.
214  _ForwardIterator2 __p1(__first2);
215  if (++__p1 == __last2)
216  return std::__find_if(__first1, __last1,
217  __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
218 
219  // General case.
220  _ForwardIterator2 __p;
221  _ForwardIterator1 __current = __first1;
222 
223  for (;;)
224  {
225  __first1 =
226  std::__find_if(__first1, __last1,
227  __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
228 
229  if (__first1 == __last1)
230  return __last1;
231 
232  __p = __p1;
233  __current = __first1;
234  if (++__current == __last1)
235  return __last1;
236 
237  while (__predicate(__current, __p))
238  {
239  if (++__p == __last2)
240  return __first1;
241  if (++__current == __last1)
242  return __last1;
243  }
244  ++__first1;
245  }
246  return __first1;
247  }
248 
249  // search_n
250 
251  /**
252  * This is an helper function for search_n overloaded for forward iterators.
253  */
254  template<typename _ForwardIterator, typename _Integer,
255  typename _UnaryPredicate>
256  _ForwardIterator
257  __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
258  _Integer __count, _UnaryPredicate __unary_pred,
260  {
261  __first = std::__find_if(__first, __last, __unary_pred);
262  while (__first != __last)
263  {
264  typename iterator_traits<_ForwardIterator>::difference_type
265  __n = __count;
266  _ForwardIterator __i = __first;
267  ++__i;
268  while (__i != __last && __n != 1 && __unary_pred(__i))
269  {
270  ++__i;
271  --__n;
272  }
273  if (__n == 1)
274  return __first;
275  if (__i == __last)
276  return __last;
277  __first = std::__find_if(++__i, __last, __unary_pred);
278  }
279  return __last;
280  }
281 
282  /**
283  * This is an helper function for search_n overloaded for random access
284  * iterators.
285  */
286  template<typename _RandomAccessIter, typename _Integer,
287  typename _UnaryPredicate>
288  _RandomAccessIter
289  __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
290  _Integer __count, _UnaryPredicate __unary_pred,
292  {
293  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
294  _DistanceType;
295 
296  _DistanceType __tailSize = __last - __first;
297  _DistanceType __remainder = __count;
298 
299  while (__remainder <= __tailSize) // the main loop...
300  {
301  __first += __remainder;
302  __tailSize -= __remainder;
303  // __first here is always pointing to one past the last element of
304  // next possible match.
305  _RandomAccessIter __backTrack = __first;
306  while (__unary_pred(--__backTrack))
307  {
308  if (--__remainder == 0)
309  return (__first - __count); // Success
310  }
311  __remainder = __count + 1 - (__first - __backTrack);
312  }
313  return __last; // Failure
314  }
315 
316  template<typename _ForwardIterator, typename _Integer,
317  typename _UnaryPredicate>
318  _ForwardIterator
319  __search_n(_ForwardIterator __first, _ForwardIterator __last,
320  _Integer __count,
321  _UnaryPredicate __unary_pred)
322  {
323  if (__count <= 0)
324  return __first;
325 
326  if (__count == 1)
327  return std::__find_if(__first, __last, __unary_pred);
328 
329  return std::__search_n_aux(__first, __last, __count, __unary_pred,
330  std::__iterator_category(__first));
331  }
332 
333  // find_end for forward iterators.
334  template<typename _ForwardIterator1, typename _ForwardIterator2,
335  typename _BinaryPredicate>
336  _ForwardIterator1
337  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
338  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
339  forward_iterator_tag, forward_iterator_tag,
340  _BinaryPredicate __comp)
341  {
342  if (__first2 == __last2)
343  return __last1;
344 
345  _ForwardIterator1 __result = __last1;
346  while (1)
347  {
348  _ForwardIterator1 __new_result
349  = std::__search(__first1, __last1, __first2, __last2, __comp);
350  if (__new_result == __last1)
351  return __result;
352  else
353  {
354  __result = __new_result;
355  __first1 = __new_result;
356  ++__first1;
357  }
358  }
359  }
360 
361  // find_end for bidirectional iterators (much faster).
362  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
363  typename _BinaryPredicate>
364  _BidirectionalIterator1
365  __find_end(_BidirectionalIterator1 __first1,
366  _BidirectionalIterator1 __last1,
367  _BidirectionalIterator2 __first2,
368  _BidirectionalIterator2 __last2,
369  bidirectional_iterator_tag, bidirectional_iterator_tag,
370  _BinaryPredicate __comp)
371  {
372  // concept requirements
373  __glibcxx_function_requires(_BidirectionalIteratorConcept<
374  _BidirectionalIterator1>)
375  __glibcxx_function_requires(_BidirectionalIteratorConcept<
376  _BidirectionalIterator2>)
377 
378  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
379  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
380 
381  _RevIterator1 __rlast1(__first1);
382  _RevIterator2 __rlast2(__first2);
383  _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
384  _RevIterator2(__last2), __rlast2,
385  __comp);
386 
387  if (__rresult == __rlast1)
388  return __last1;
389  else
390  {
391  _BidirectionalIterator1 __result = __rresult.base();
392  std::advance(__result, -std::distance(__first2, __last2));
393  return __result;
394  }
395  }
396 
397  /**
398  * @brief Find last matching subsequence in a sequence.
399  * @ingroup non_mutating_algorithms
400  * @param __first1 Start of range to search.
401  * @param __last1 End of range to search.
402  * @param __first2 Start of sequence to match.
403  * @param __last2 End of sequence to match.
404  * @return The last iterator @c i in the range
405  * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
406  * @p *(__first2+N) for each @c N in the range @p
407  * [0,__last2-__first2), or @p __last1 if no such iterator exists.
408  *
409  * Searches the range @p [__first1,__last1) for a sub-sequence that
410  * compares equal value-by-value with the sequence given by @p
411  * [__first2,__last2) and returns an iterator to the __first
412  * element of the sub-sequence, or @p __last1 if the sub-sequence
413  * is not found. The sub-sequence will be the last such
414  * subsequence contained in [__first1,__last1).
415  *
416  * Because the sub-sequence must lie completely within the range @p
417  * [__first1,__last1) it must start at a position less than @p
418  * __last1-(__last2-__first2) where @p __last2-__first2 is the
419  * length of the sub-sequence. This means that the returned
420  * iterator @c i will be in the range @p
421  * [__first1,__last1-(__last2-__first2))
422  */
423  template<typename _ForwardIterator1, typename _ForwardIterator2>
424  inline _ForwardIterator1
425  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
427  {
428  // concept requirements
429  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431  __glibcxx_function_requires(_EqualOpConcept<
432  typename iterator_traits<_ForwardIterator1>::value_type,
433  typename iterator_traits<_ForwardIterator2>::value_type>)
434  __glibcxx_requires_valid_range(__first1, __last1);
435  __glibcxx_requires_valid_range(__first2, __last2);
436 
437  return std::__find_end(__first1, __last1, __first2, __last2,
438  std::__iterator_category(__first1),
439  std::__iterator_category(__first2),
440  __gnu_cxx::__ops::__iter_equal_to_iter());
441  }
442 
443  /**
444  * @brief Find last matching subsequence in a sequence using a predicate.
445  * @ingroup non_mutating_algorithms
446  * @param __first1 Start of range to search.
447  * @param __last1 End of range to search.
448  * @param __first2 Start of sequence to match.
449  * @param __last2 End of sequence to match.
450  * @param __comp The predicate to use.
451  * @return The last iterator @c i in the range @p
452  * [__first1,__last1-(__last2-__first2)) such that @c
453  * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
454  * range @p [0,__last2-__first2), or @p __last1 if no such iterator
455  * exists.
456  *
457  * Searches the range @p [__first1,__last1) for a sub-sequence that
458  * compares equal value-by-value with the sequence given by @p
459  * [__first2,__last2) using comp as a predicate and returns an
460  * iterator to the first element of the sub-sequence, or @p __last1
461  * if the sub-sequence is not found. The sub-sequence will be the
462  * last such subsequence contained in [__first,__last1).
463  *
464  * Because the sub-sequence must lie completely within the range @p
465  * [__first1,__last1) it must start at a position less than @p
466  * __last1-(__last2-__first2) where @p __last2-__first2 is the
467  * length of the sub-sequence. This means that the returned
468  * iterator @c i will be in the range @p
469  * [__first1,__last1-(__last2-__first2))
470  */
471  template<typename _ForwardIterator1, typename _ForwardIterator2,
472  typename _BinaryPredicate>
473  inline _ForwardIterator1
474  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476  _BinaryPredicate __comp)
477  {
478  // concept requirements
479  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482  typename iterator_traits<_ForwardIterator1>::value_type,
483  typename iterator_traits<_ForwardIterator2>::value_type>)
484  __glibcxx_requires_valid_range(__first1, __last1);
485  __glibcxx_requires_valid_range(__first2, __last2);
486 
487  return std::__find_end(__first1, __last1, __first2, __last2,
488  std::__iterator_category(__first1),
489  std::__iterator_category(__first2),
490  __gnu_cxx::__ops::__iter_comp_iter(__comp));
491  }
492 
493 #if __cplusplus >= 201103L
494  /**
495  * @brief Checks that a predicate is true for all the elements
496  * of a sequence.
497  * @ingroup non_mutating_algorithms
498  * @param __first An input iterator.
499  * @param __last An input iterator.
500  * @param __pred A predicate.
501  * @return True if the check is true, false otherwise.
502  *
503  * Returns true if @p __pred is true for each element in the range
504  * @p [__first,__last), and false otherwise.
505  */
506  template<typename _InputIterator, typename _Predicate>
507  inline bool
508  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
509  { return __last == std::find_if_not(__first, __last, __pred); }
510 
511  /**
512  * @brief Checks that a predicate is false for all the elements
513  * of a sequence.
514  * @ingroup non_mutating_algorithms
515  * @param __first An input iterator.
516  * @param __last An input iterator.
517  * @param __pred A predicate.
518  * @return True if the check is true, false otherwise.
519  *
520  * Returns true if @p __pred is false for each element in the range
521  * @p [__first,__last), and false otherwise.
522  */
523  template<typename _InputIterator, typename _Predicate>
524  inline bool
525  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
526  { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
527 
528  /**
529  * @brief Checks that a predicate is false for at least an element
530  * of a sequence.
531  * @ingroup non_mutating_algorithms
532  * @param __first An input iterator.
533  * @param __last An input iterator.
534  * @param __pred A predicate.
535  * @return True if the check is true, false otherwise.
536  *
537  * Returns true if an element exists in the range @p
538  * [__first,__last) such that @p __pred is true, and false
539  * otherwise.
540  */
541  template<typename _InputIterator, typename _Predicate>
542  inline bool
543  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
544  { return !std::none_of(__first, __last, __pred); }
545 
546  /**
547  * @brief Find the first element in a sequence for which a
548  * predicate is false.
549  * @ingroup non_mutating_algorithms
550  * @param __first An input iterator.
551  * @param __last An input iterator.
552  * @param __pred A predicate.
553  * @return The first iterator @c i in the range @p [__first,__last)
554  * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
555  */
556  template<typename _InputIterator, typename _Predicate>
557  inline _InputIterator
558  find_if_not(_InputIterator __first, _InputIterator __last,
559  _Predicate __pred)
560  {
561  // concept requirements
562  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
563  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564  typename iterator_traits<_InputIterator>::value_type>)
565  __glibcxx_requires_valid_range(__first, __last);
566  return std::__find_if_not(__first, __last,
567  __gnu_cxx::__ops::__pred_iter(__pred));
568  }
569 
570  /**
571  * @brief Checks whether the sequence is partitioned.
572  * @ingroup mutating_algorithms
573  * @param __first An input iterator.
574  * @param __last An input iterator.
575  * @param __pred A predicate.
576  * @return True if the range @p [__first,__last) is partioned by @p __pred,
577  * i.e. if all elements that satisfy @p __pred appear before those that
578  * do not.
579  */
580  template<typename _InputIterator, typename _Predicate>
581  inline bool
582  is_partitioned(_InputIterator __first, _InputIterator __last,
583  _Predicate __pred)
584  {
585  __first = std::find_if_not(__first, __last, __pred);
586  if (__first == __last)
587  return true;
588  ++__first;
589  return std::none_of(__first, __last, __pred);
590  }
591 
592  /**
593  * @brief Find the partition point of a partitioned range.
594  * @ingroup mutating_algorithms
595  * @param __first An iterator.
596  * @param __last Another iterator.
597  * @param __pred A predicate.
598  * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
599  * and @p none_of(mid, __last, __pred) are both true.
600  */
601  template<typename _ForwardIterator, typename _Predicate>
602  _ForwardIterator
603  partition_point(_ForwardIterator __first, _ForwardIterator __last,
604  _Predicate __pred)
605  {
606  // concept requirements
607  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
608  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
609  typename iterator_traits<_ForwardIterator>::value_type>)
610 
611  // A specific debug-mode test will be necessary...
612  __glibcxx_requires_valid_range(__first, __last);
613 
614  typedef typename iterator_traits<_ForwardIterator>::difference_type
615  _DistanceType;
616 
617  _DistanceType __len = std::distance(__first, __last);
618  _DistanceType __half;
619  _ForwardIterator __middle;
620 
621  while (__len > 0)
622  {
623  __half = __len >> 1;
624  __middle = __first;
625  std::advance(__middle, __half);
626  if (__pred(*__middle))
627  {
628  __first = __middle;
629  ++__first;
630  __len = __len - __half - 1;
631  }
632  else
633  __len = __half;
634  }
635  return __first;
636  }
637 #endif
638 
639  template<typename _InputIterator, typename _OutputIterator,
640  typename _Predicate>
641  _OutputIterator
642  __remove_copy_if(_InputIterator __first, _InputIterator __last,
643  _OutputIterator __result, _Predicate __pred)
644  {
645  for (; __first != __last; ++__first)
646  if (!__pred(__first))
647  {
648  *__result = *__first;
649  ++__result;
650  }
651  return __result;
652  }
653 
654  /**
655  * @brief Copy a sequence, removing elements of a given value.
656  * @ingroup mutating_algorithms
657  * @param __first An input iterator.
658  * @param __last An input iterator.
659  * @param __result An output iterator.
660  * @param __value The value to be removed.
661  * @return An iterator designating the end of the resulting sequence.
662  *
663  * Copies each element in the range @p [__first,__last) not equal
664  * to @p __value to the range beginning at @p __result.
665  * remove_copy() is stable, so the relative order of elements that
666  * are copied is unchanged.
667  */
668  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
669  inline _OutputIterator
670  remove_copy(_InputIterator __first, _InputIterator __last,
671  _OutputIterator __result, const _Tp& __value)
672  {
673  // concept requirements
674  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
675  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
676  typename iterator_traits<_InputIterator>::value_type>)
677  __glibcxx_function_requires(_EqualOpConcept<
678  typename iterator_traits<_InputIterator>::value_type, _Tp>)
679  __glibcxx_requires_valid_range(__first, __last);
680 
681  return std::__remove_copy_if(__first, __last, __result,
682  __gnu_cxx::__ops::__iter_equals_val(__value));
683  }
684 
685  /**
686  * @brief Copy a sequence, removing elements for which a predicate is true.
687  * @ingroup mutating_algorithms
688  * @param __first An input iterator.
689  * @param __last An input iterator.
690  * @param __result An output iterator.
691  * @param __pred A predicate.
692  * @return An iterator designating the end of the resulting sequence.
693  *
694  * Copies each element in the range @p [__first,__last) for which
695  * @p __pred returns false to the range beginning at @p __result.
696  *
697  * remove_copy_if() is stable, so the relative order of elements that are
698  * copied is unchanged.
699  */
700  template<typename _InputIterator, typename _OutputIterator,
701  typename _Predicate>
702  inline _OutputIterator
703  remove_copy_if(_InputIterator __first, _InputIterator __last,
704  _OutputIterator __result, _Predicate __pred)
705  {
706  // concept requirements
707  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
708  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
709  typename iterator_traits<_InputIterator>::value_type>)
710  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
711  typename iterator_traits<_InputIterator>::value_type>)
712  __glibcxx_requires_valid_range(__first, __last);
713 
714  return std::__remove_copy_if(__first, __last, __result,
715  __gnu_cxx::__ops::__pred_iter(__pred));
716  }
717 
718 #if __cplusplus >= 201103L
719  /**
720  * @brief Copy the elements of a sequence for which a predicate is true.
721  * @ingroup mutating_algorithms
722  * @param __first An input iterator.
723  * @param __last An input iterator.
724  * @param __result An output iterator.
725  * @param __pred A predicate.
726  * @return An iterator designating the end of the resulting sequence.
727  *
728  * Copies each element in the range @p [__first,__last) for which
729  * @p __pred returns true to the range beginning at @p __result.
730  *
731  * copy_if() is stable, so the relative order of elements that are
732  * copied is unchanged.
733  */
734  template<typename _InputIterator, typename _OutputIterator,
735  typename _Predicate>
736  _OutputIterator
737  copy_if(_InputIterator __first, _InputIterator __last,
738  _OutputIterator __result, _Predicate __pred)
739  {
740  // concept requirements
741  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
742  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
743  typename iterator_traits<_InputIterator>::value_type>)
744  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
745  typename iterator_traits<_InputIterator>::value_type>)
746  __glibcxx_requires_valid_range(__first, __last);
747 
748  for (; __first != __last; ++__first)
749  if (__pred(*__first))
750  {
751  *__result = *__first;
752  ++__result;
753  }
754  return __result;
755  }
756 
757  template<typename _InputIterator, typename _Size, typename _OutputIterator>
758  _OutputIterator
759  __copy_n(_InputIterator __first, _Size __n,
760  _OutputIterator __result, input_iterator_tag)
761  {
762  if (__n > 0)
763  {
764  while (true)
765  {
766  *__result = *__first;
767  ++__result;
768  if (--__n > 0)
769  ++__first;
770  else
771  break;
772  }
773  }
774  return __result;
775  }
776 
777  template<typename _RandomAccessIterator, typename _Size,
778  typename _OutputIterator>
779  inline _OutputIterator
780  __copy_n(_RandomAccessIterator __first, _Size __n,
781  _OutputIterator __result, random_access_iterator_tag)
782  { return std::copy(__first, __first + __n, __result); }
783 
784  /**
785  * @brief Copies the range [first,first+n) into [result,result+n).
786  * @ingroup mutating_algorithms
787  * @param __first An input iterator.
788  * @param __n The number of elements to copy.
789  * @param __result An output iterator.
790  * @return result+n.
791  *
792  * This inline function will boil down to a call to @c memmove whenever
793  * possible. Failing that, if random access iterators are passed, then the
794  * loop count will be known (and therefore a candidate for compiler
795  * optimizations such as unrolling).
796  */
797  template<typename _InputIterator, typename _Size, typename _OutputIterator>
798  inline _OutputIterator
799  copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
800  {
801  // concept requirements
802  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
803  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
804  typename iterator_traits<_InputIterator>::value_type>)
805 
806  return std::__copy_n(__first, __n, __result,
807  std::__iterator_category(__first));
808  }
809 
810  /**
811  * @brief Copy the elements of a sequence to separate output sequences
812  * depending on the truth value of a predicate.
813  * @ingroup mutating_algorithms
814  * @param __first An input iterator.
815  * @param __last An input iterator.
816  * @param __out_true An output iterator.
817  * @param __out_false An output iterator.
818  * @param __pred A predicate.
819  * @return A pair designating the ends of the resulting sequences.
820  *
821  * Copies each element in the range @p [__first,__last) for which
822  * @p __pred returns true to the range beginning at @p out_true
823  * and each element for which @p __pred returns false to @p __out_false.
824  */
825  template<typename _InputIterator, typename _OutputIterator1,
826  typename _OutputIterator2, typename _Predicate>
827  pair<_OutputIterator1, _OutputIterator2>
828  partition_copy(_InputIterator __first, _InputIterator __last,
829  _OutputIterator1 __out_true, _OutputIterator2 __out_false,
830  _Predicate __pred)
831  {
832  // concept requirements
833  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
834  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
835  typename iterator_traits<_InputIterator>::value_type>)
836  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
837  typename iterator_traits<_InputIterator>::value_type>)
838  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
839  typename iterator_traits<_InputIterator>::value_type>)
840  __glibcxx_requires_valid_range(__first, __last);
841 
842  for (; __first != __last; ++__first)
843  if (__pred(*__first))
844  {
845  *__out_true = *__first;
846  ++__out_true;
847  }
848  else
849  {
850  *__out_false = *__first;
851  ++__out_false;
852  }
853 
854  return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
855  }
856 #endif
857 
858  template<typename _ForwardIterator, typename _Predicate>
859  _ForwardIterator
860  __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861  _Predicate __pred)
862  {
863  __first = std::__find_if(__first, __last, __pred);
864  if (__first == __last)
865  return __first;
866  _ForwardIterator __result = __first;
867  ++__first;
868  for (; __first != __last; ++__first)
869  if (!__pred(__first))
870  {
871  *__result = _GLIBCXX_MOVE(*__first);
872  ++__result;
873  }
874  return __result;
875  }
876 
877  /**
878  * @brief Remove elements from a sequence.
879  * @ingroup mutating_algorithms
880  * @param __first An input iterator.
881  * @param __last An input iterator.
882  * @param __value The value to be removed.
883  * @return An iterator designating the end of the resulting sequence.
884  *
885  * All elements equal to @p __value are removed from the range
886  * @p [__first,__last).
887  *
888  * remove() is stable, so the relative order of elements that are
889  * not removed is unchanged.
890  *
891  * Elements between the end of the resulting sequence and @p __last
892  * are still present, but their value is unspecified.
893  */
894  template<typename _ForwardIterator, typename _Tp>
895  inline _ForwardIterator
896  remove(_ForwardIterator __first, _ForwardIterator __last,
897  const _Tp& __value)
898  {
899  // concept requirements
900  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
901  _ForwardIterator>)
902  __glibcxx_function_requires(_EqualOpConcept<
903  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
904  __glibcxx_requires_valid_range(__first, __last);
905 
906  return std::__remove_if(__first, __last,
907  __gnu_cxx::__ops::__iter_equals_val(__value));
908  }
909 
910  /**
911  * @brief Remove elements from a sequence using a predicate.
912  * @ingroup mutating_algorithms
913  * @param __first A forward iterator.
914  * @param __last A forward iterator.
915  * @param __pred A predicate.
916  * @return An iterator designating the end of the resulting sequence.
917  *
918  * All elements for which @p __pred returns true are removed from the range
919  * @p [__first,__last).
920  *
921  * remove_if() is stable, so the relative order of elements that are
922  * not removed is unchanged.
923  *
924  * Elements between the end of the resulting sequence and @p __last
925  * are still present, but their value is unspecified.
926  */
927  template<typename _ForwardIterator, typename _Predicate>
928  inline _ForwardIterator
929  remove_if(_ForwardIterator __first, _ForwardIterator __last,
930  _Predicate __pred)
931  {
932  // concept requirements
933  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
934  _ForwardIterator>)
935  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
936  typename iterator_traits<_ForwardIterator>::value_type>)
937  __glibcxx_requires_valid_range(__first, __last);
938 
939  return std::__remove_if(__first, __last,
940  __gnu_cxx::__ops::__pred_iter(__pred));
941  }
942 
943  template<typename _ForwardIterator, typename _BinaryPredicate>
944  _ForwardIterator
945  __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
946  _BinaryPredicate __binary_pred)
947  {
948  if (__first == __last)
949  return __last;
950  _ForwardIterator __next = __first;
951  while (++__next != __last)
952  {
953  if (__binary_pred(__first, __next))
954  return __first;
955  __first = __next;
956  }
957  return __last;
958  }
959 
960  template<typename _ForwardIterator, typename _BinaryPredicate>
961  _ForwardIterator
962  __unique(_ForwardIterator __first, _ForwardIterator __last,
963  _BinaryPredicate __binary_pred)
964  {
965  // Skip the beginning, if already unique.
966  __first = std::__adjacent_find(__first, __last, __binary_pred);
967  if (__first == __last)
968  return __last;
969 
970  // Do the real copy work.
971  _ForwardIterator __dest = __first;
972  ++__first;
973  while (++__first != __last)
974  if (!__binary_pred(__dest, __first))
975  *++__dest = _GLIBCXX_MOVE(*__first);
976  return ++__dest;
977  }
978 
979  /**
980  * @brief Remove consecutive duplicate values from a sequence.
981  * @ingroup mutating_algorithms
982  * @param __first A forward iterator.
983  * @param __last A forward iterator.
984  * @return An iterator designating the end of the resulting sequence.
985  *
986  * Removes all but the first element from each group of consecutive
987  * values that compare equal.
988  * unique() is stable, so the relative order of elements that are
989  * not removed is unchanged.
990  * Elements between the end of the resulting sequence and @p __last
991  * are still present, but their value is unspecified.
992  */
993  template<typename _ForwardIterator>
994  inline _ForwardIterator
995  unique(_ForwardIterator __first, _ForwardIterator __last)
996  {
997  // concept requirements
998  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
999  _ForwardIterator>)
1000  __glibcxx_function_requires(_EqualityComparableConcept<
1001  typename iterator_traits<_ForwardIterator>::value_type>)
1002  __glibcxx_requires_valid_range(__first, __last);
1003 
1004  return std::__unique(__first, __last,
1005  __gnu_cxx::__ops::__iter_equal_to_iter());
1006  }
1007 
1008  /**
1009  * @brief Remove consecutive values from a sequence using a predicate.
1010  * @ingroup mutating_algorithms
1011  * @param __first A forward iterator.
1012  * @param __last A forward iterator.
1013  * @param __binary_pred A binary predicate.
1014  * @return An iterator designating the end of the resulting sequence.
1015  *
1016  * Removes all but the first element from each group of consecutive
1017  * values for which @p __binary_pred returns true.
1018  * unique() is stable, so the relative order of elements that are
1019  * not removed is unchanged.
1020  * Elements between the end of the resulting sequence and @p __last
1021  * are still present, but their value is unspecified.
1022  */
1023  template<typename _ForwardIterator, typename _BinaryPredicate>
1024  inline _ForwardIterator
1025  unique(_ForwardIterator __first, _ForwardIterator __last,
1026  _BinaryPredicate __binary_pred)
1027  {
1028  // concept requirements
1029  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1030  _ForwardIterator>)
1031  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032  typename iterator_traits<_ForwardIterator>::value_type,
1033  typename iterator_traits<_ForwardIterator>::value_type>)
1034  __glibcxx_requires_valid_range(__first, __last);
1035 
1036  return std::__unique(__first, __last,
1037  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1038  }
1039 
1040  /**
1041  * This is an uglified
1042  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1043  * _BinaryPredicate)
1044  * overloaded for forward iterators and output iterator as result.
1045  */
1046  template<typename _ForwardIterator, typename _OutputIterator,
1047  typename _BinaryPredicate>
1048  _OutputIterator
1049  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1050  _OutputIterator __result, _BinaryPredicate __binary_pred,
1052  {
1053  // concept requirements -- iterators already checked
1054  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1055  typename iterator_traits<_ForwardIterator>::value_type,
1056  typename iterator_traits<_ForwardIterator>::value_type>)
1057 
1058  _ForwardIterator __next = __first;
1059  *__result = *__first;
1060  while (++__next != __last)
1061  if (!__binary_pred(__first, __next))
1062  {
1063  __first = __next;
1064  *++__result = *__first;
1065  }
1066  return ++__result;
1067  }
1068 
1069  /**
1070  * This is an uglified
1071  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1072  * _BinaryPredicate)
1073  * overloaded for input iterators and output iterator as result.
1074  */
1075  template<typename _InputIterator, typename _OutputIterator,
1076  typename _BinaryPredicate>
1077  _OutputIterator
1078  __unique_copy(_InputIterator __first, _InputIterator __last,
1079  _OutputIterator __result, _BinaryPredicate __binary_pred,
1081  {
1082  // concept requirements -- iterators already checked
1083  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1084  typename iterator_traits<_InputIterator>::value_type,
1085  typename iterator_traits<_InputIterator>::value_type>)
1086 
1087  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1088  __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1089  __rebound_pred
1090  = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1091  *__result = __value;
1092  while (++__first != __last)
1093  if (!__rebound_pred(__first, __value))
1094  {
1095  __value = *__first;
1096  *++__result = __value;
1097  }
1098  return ++__result;
1099  }
1100 
1101  /**
1102  * This is an uglified
1103  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1104  * _BinaryPredicate)
1105  * overloaded for input iterators and forward iterator as result.
1106  */
1107  template<typename _InputIterator, typename _ForwardIterator,
1108  typename _BinaryPredicate>
1109  _ForwardIterator
1110  __unique_copy(_InputIterator __first, _InputIterator __last,
1111  _ForwardIterator __result, _BinaryPredicate __binary_pred,
1113  {
1114  // concept requirements -- iterators already checked
1115  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1116  typename iterator_traits<_ForwardIterator>::value_type,
1117  typename iterator_traits<_InputIterator>::value_type>)
1118  *__result = *__first;
1119  while (++__first != __last)
1120  if (!__binary_pred(__result, __first))
1121  *++__result = *__first;
1122  return ++__result;
1123  }
1124 
1125  /**
1126  * This is an uglified reverse(_BidirectionalIterator,
1127  * _BidirectionalIterator)
1128  * overloaded for bidirectional iterators.
1129  */
1130  template<typename _BidirectionalIterator>
1131  void
1132  __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1134  {
1135  while (true)
1136  if (__first == __last || __first == --__last)
1137  return;
1138  else
1139  {
1140  std::iter_swap(__first, __last);
1141  ++__first;
1142  }
1143  }
1144 
1145  /**
1146  * This is an uglified reverse(_BidirectionalIterator,
1147  * _BidirectionalIterator)
1148  * overloaded for random access iterators.
1149  */
1150  template<typename _RandomAccessIterator>
1151  void
1152  __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1154  {
1155  if (__first == __last)
1156  return;
1157  --__last;
1158  while (__first < __last)
1159  {
1160  std::iter_swap(__first, __last);
1161  ++__first;
1162  --__last;
1163  }
1164  }
1165 
1166  /**
1167  * @brief Reverse a sequence.
1168  * @ingroup mutating_algorithms
1169  * @param __first A bidirectional iterator.
1170  * @param __last A bidirectional iterator.
1171  * @return reverse() returns no value.
1172  *
1173  * Reverses the order of the elements in the range @p [__first,__last),
1174  * so that the first element becomes the last etc.
1175  * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1176  * swaps @p *(__first+i) and @p *(__last-(i+1))
1177  */
1178  template<typename _BidirectionalIterator>
1179  inline void
1180  reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1181  {
1182  // concept requirements
1183  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1184  _BidirectionalIterator>)
1185  __glibcxx_requires_valid_range(__first, __last);
1186  std::__reverse(__first, __last, std::__iterator_category(__first));
1187  }
1188 
1189  /**
1190  * @brief Copy a sequence, reversing its elements.
1191  * @ingroup mutating_algorithms
1192  * @param __first A bidirectional iterator.
1193  * @param __last A bidirectional iterator.
1194  * @param __result An output iterator.
1195  * @return An iterator designating the end of the resulting sequence.
1196  *
1197  * Copies the elements in the range @p [__first,__last) to the
1198  * range @p [__result,__result+(__last-__first)) such that the
1199  * order of the elements is reversed. For every @c i such that @p
1200  * 0<=i<=(__last-__first), @p reverse_copy() performs the
1201  * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1202  * The ranges @p [__first,__last) and @p
1203  * [__result,__result+(__last-__first)) must not overlap.
1204  */
1205  template<typename _BidirectionalIterator, typename _OutputIterator>
1206  _OutputIterator
1207  reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1208  _OutputIterator __result)
1209  {
1210  // concept requirements
1211  __glibcxx_function_requires(_BidirectionalIteratorConcept<
1212  _BidirectionalIterator>)
1213  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1214  typename iterator_traits<_BidirectionalIterator>::value_type>)
1215  __glibcxx_requires_valid_range(__first, __last);
1216 
1217  while (__first != __last)
1218  {
1219  --__last;
1220  *__result = *__last;
1221  ++__result;
1222  }
1223  return __result;
1224  }
1225 
1226  /**
1227  * This is a helper function for the rotate algorithm specialized on RAIs.
1228  * It returns the greatest common divisor of two integer values.
1229  */
1230  template<typename _EuclideanRingElement>
1231  _EuclideanRingElement
1232  __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1233  {
1234  while (__n != 0)
1235  {
1236  _EuclideanRingElement __t = __m % __n;
1237  __m = __n;
1238  __n = __t;
1239  }
1240  return __m;
1241  }
1242 
1243  inline namespace _V2
1244  {
1245 
1246  /// This is a helper function for the rotate algorithm.
1247  template<typename _ForwardIterator>
1248  _ForwardIterator
1249  __rotate(_ForwardIterator __first,
1250  _ForwardIterator __middle,
1251  _ForwardIterator __last,
1253  {
1254  _ForwardIterator __first2 = __middle;
1255  do
1256  {
1257  std::iter_swap(__first, __first2);
1258  ++__first;
1259  ++__first2;
1260  if (__first == __middle)
1261  __middle = __first2;
1262  }
1263  while (__first2 != __last);
1264 
1265  _ForwardIterator __ret = __first;
1266 
1267  __first2 = __middle;
1268 
1269  while (__first2 != __last)
1270  {
1271  std::iter_swap(__first, __first2);
1272  ++__first;
1273  ++__first2;
1274  if (__first == __middle)
1275  __middle = __first2;
1276  else if (__first2 == __last)
1277  __first2 = __middle;
1278  }
1279  return __ret;
1280  }
1281 
1282  /// This is a helper function for the rotate algorithm.
1283  template<typename _BidirectionalIterator>
1284  _BidirectionalIterator
1285  __rotate(_BidirectionalIterator __first,
1286  _BidirectionalIterator __middle,
1287  _BidirectionalIterator __last,
1289  {
1290  // concept requirements
1291  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1292  _BidirectionalIterator>)
1293 
1294  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1295  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1296 
1297  while (__first != __middle && __middle != __last)
1298  {
1299  std::iter_swap(__first, --__last);
1300  ++__first;
1301  }
1302 
1303  if (__first == __middle)
1304  {
1305  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1306  return __last;
1307  }
1308  else
1309  {
1310  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1311  return __first;
1312  }
1313  }
1314 
1315  /// This is a helper function for the rotate algorithm.
1316  template<typename _RandomAccessIterator>
1317  _RandomAccessIterator
1318  __rotate(_RandomAccessIterator __first,
1319  _RandomAccessIterator __middle,
1320  _RandomAccessIterator __last,
1322  {
1323  // concept requirements
1324  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1325  _RandomAccessIterator>)
1326 
1327  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1328  _Distance;
1329  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1330  _ValueType;
1331 
1332  _Distance __n = __last - __first;
1333  _Distance __k = __middle - __first;
1334 
1335  if (__k == __n - __k)
1336  {
1337  std::swap_ranges(__first, __middle, __middle);
1338  return __middle;
1339  }
1340 
1341  _RandomAccessIterator __p = __first;
1342  _RandomAccessIterator __ret = __first + (__last - __middle);
1343 
1344  for (;;)
1345  {
1346  if (__k < __n - __k)
1347  {
1348  if (__is_pod(_ValueType) && __k == 1)
1349  {
1350  _ValueType __t = _GLIBCXX_MOVE(*__p);
1351  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1352  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1353  return __ret;
1354  }
1355  _RandomAccessIterator __q = __p + __k;
1356  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1357  {
1358  std::iter_swap(__p, __q);
1359  ++__p;
1360  ++__q;
1361  }
1362  __n %= __k;
1363  if (__n == 0)
1364  return __ret;
1365  std::swap(__n, __k);
1366  __k = __n - __k;
1367  }
1368  else
1369  {
1370  __k = __n - __k;
1371  if (__is_pod(_ValueType) && __k == 1)
1372  {
1373  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1374  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1375  *__p = _GLIBCXX_MOVE(__t);
1376  return __ret;
1377  }
1378  _RandomAccessIterator __q = __p + __n;
1379  __p = __q - __k;
1380  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1381  {
1382  --__p;
1383  --__q;
1384  std::iter_swap(__p, __q);
1385  }
1386  __n %= __k;
1387  if (__n == 0)
1388  return __ret;
1389  std::swap(__n, __k);
1390  }
1391  }
1392  }
1393 
1394  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1395  // DR 488. rotate throws away useful information
1396  /**
1397  * @brief Rotate the elements of a sequence.
1398  * @ingroup mutating_algorithms
1399  * @param __first A forward iterator.
1400  * @param __middle A forward iterator.
1401  * @param __last A forward iterator.
1402  * @return first + (last - middle).
1403  *
1404  * Rotates the elements of the range @p [__first,__last) by
1405  * @p (__middle - __first) positions so that the element at @p __middle
1406  * is moved to @p __first, the element at @p __middle+1 is moved to
1407  * @p __first+1 and so on for each element in the range
1408  * @p [__first,__last).
1409  *
1410  * This effectively swaps the ranges @p [__first,__middle) and
1411  * @p [__middle,__last).
1412  *
1413  * Performs
1414  * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1415  * for each @p n in the range @p [0,__last-__first).
1416  */
1417  template<typename _ForwardIterator>
1418  inline _ForwardIterator
1419  rotate(_ForwardIterator __first, _ForwardIterator __middle,
1420  _ForwardIterator __last)
1421  {
1422  // concept requirements
1423  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1424  _ForwardIterator>)
1425  __glibcxx_requires_valid_range(__first, __middle);
1426  __glibcxx_requires_valid_range(__middle, __last);
1427 
1428  if (__first == __middle)
1429  return __last;
1430  else if (__last == __middle)
1431  return __first;
1432 
1433  return std::__rotate(__first, __middle, __last,
1434  std::__iterator_category(__first));
1435  }
1436 
1437  } // namespace _V2
1438 
1439  /**
1440  * @brief Copy a sequence, rotating its elements.
1441  * @ingroup mutating_algorithms
1442  * @param __first A forward iterator.
1443  * @param __middle A forward iterator.
1444  * @param __last A forward iterator.
1445  * @param __result An output iterator.
1446  * @return An iterator designating the end of the resulting sequence.
1447  *
1448  * Copies the elements of the range @p [__first,__last) to the
1449  * range beginning at @result, rotating the copied elements by
1450  * @p (__middle-__first) positions so that the element at @p __middle
1451  * is moved to @p __result, the element at @p __middle+1 is moved
1452  * to @p __result+1 and so on for each element in the range @p
1453  * [__first,__last).
1454  *
1455  * Performs
1456  * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1457  * for each @p n in the range @p [0,__last-__first).
1458  */
1459  template<typename _ForwardIterator, typename _OutputIterator>
1460  inline _OutputIterator
1461  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1462  _ForwardIterator __last, _OutputIterator __result)
1463  {
1464  // concept requirements
1465  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1466  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1467  typename iterator_traits<_ForwardIterator>::value_type>)
1468  __glibcxx_requires_valid_range(__first, __middle);
1469  __glibcxx_requires_valid_range(__middle, __last);
1470 
1471  return std::copy(__first, __middle,
1472  std::copy(__middle, __last, __result));
1473  }
1474 
1475  /// This is a helper function...
1476  template<typename _ForwardIterator, typename _Predicate>
1477  _ForwardIterator
1478  __partition(_ForwardIterator __first, _ForwardIterator __last,
1479  _Predicate __pred, forward_iterator_tag)
1480  {
1481  if (__first == __last)
1482  return __first;
1483 
1484  while (__pred(*__first))
1485  if (++__first == __last)
1486  return __first;
1487 
1488  _ForwardIterator __next = __first;
1489 
1490  while (++__next != __last)
1491  if (__pred(*__next))
1492  {
1493  std::iter_swap(__first, __next);
1494  ++__first;
1495  }
1496 
1497  return __first;
1498  }
1499 
1500  /// This is a helper function...
1501  template<typename _BidirectionalIterator, typename _Predicate>
1502  _BidirectionalIterator
1503  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1504  _Predicate __pred, bidirectional_iterator_tag)
1505  {
1506  while (true)
1507  {
1508  while (true)
1509  if (__first == __last)
1510  return __first;
1511  else if (__pred(*__first))
1512  ++__first;
1513  else
1514  break;
1515  --__last;
1516  while (true)
1517  if (__first == __last)
1518  return __first;
1519  else if (!bool(__pred(*__last)))
1520  --__last;
1521  else
1522  break;
1523  std::iter_swap(__first, __last);
1524  ++__first;
1525  }
1526  }
1527 
1528  // partition
1529 
1530  /// This is a helper function...
1531  /// Requires __first != __last and !__pred(__first)
1532  /// and __len == distance(__first, __last).
1533  ///
1534  /// !__pred(__first) allows us to guarantee that we don't
1535  /// move-assign an element onto itself.
1536  template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1537  typename _Distance>
1538  _ForwardIterator
1539  __stable_partition_adaptive(_ForwardIterator __first,
1540  _ForwardIterator __last,
1541  _Predicate __pred, _Distance __len,
1542  _Pointer __buffer,
1543  _Distance __buffer_size)
1544  {
1545  if (__len == 1)
1546  return __first;
1547 
1548  if (__len <= __buffer_size)
1549  {
1550  _ForwardIterator __result1 = __first;
1551  _Pointer __result2 = __buffer;
1552 
1553  // The precondition guarantees that !__pred(__first), so
1554  // move that element to the buffer before starting the loop.
1555  // This ensures that we only call __pred once per element.
1556  *__result2 = _GLIBCXX_MOVE(*__first);
1557  ++__result2;
1558  ++__first;
1559  for (; __first != __last; ++__first)
1560  if (__pred(__first))
1561  {
1562  *__result1 = _GLIBCXX_MOVE(*__first);
1563  ++__result1;
1564  }
1565  else
1566  {
1567  *__result2 = _GLIBCXX_MOVE(*__first);
1568  ++__result2;
1569  }
1570 
1571  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1572  return __result1;
1573  }
1574 
1575  _ForwardIterator __middle = __first;
1576  std::advance(__middle, __len / 2);
1577  _ForwardIterator __left_split =
1578  std::__stable_partition_adaptive(__first, __middle, __pred,
1579  __len / 2, __buffer,
1580  __buffer_size);
1581 
1582  // Advance past true-predicate values to satisfy this
1583  // function's preconditions.
1584  _Distance __right_len = __len - __len / 2;
1585  _ForwardIterator __right_split =
1586  std::__find_if_not_n(__middle, __right_len, __pred);
1587 
1588  if (__right_len)
1589  __right_split =
1590  std::__stable_partition_adaptive(__right_split, __last, __pred,
1591  __right_len,
1592  __buffer, __buffer_size);
1593 
1594  return std::rotate(__left_split, __middle, __right_split);
1595  }
1596 
1597  template<typename _ForwardIterator, typename _Predicate>
1598  _ForwardIterator
1599  __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1600  _Predicate __pred)
1601  {
1602  __first = std::__find_if_not(__first, __last, __pred);
1603 
1604  if (__first == __last)
1605  return __first;
1606 
1607  typedef typename iterator_traits<_ForwardIterator>::value_type
1608  _ValueType;
1609  typedef typename iterator_traits<_ForwardIterator>::difference_type
1610  _DistanceType;
1611 
1612  _Temporary_buffer<_ForwardIterator, _ValueType>
1613  __buf(__first, std::distance(__first, __last));
1614  return
1615  std::__stable_partition_adaptive(__first, __last, __pred,
1616  _DistanceType(__buf.requested_size()),
1617  __buf.begin(),
1618  _DistanceType(__buf.size()));
1619  }
1620 
1621  /**
1622  * @brief Move elements for which a predicate is true to the beginning
1623  * of a sequence, preserving relative ordering.
1624  * @ingroup mutating_algorithms
1625  * @param __first A forward iterator.
1626  * @param __last A forward iterator.
1627  * @param __pred A predicate functor.
1628  * @return An iterator @p middle such that @p __pred(i) is true for each
1629  * iterator @p i in the range @p [first,middle) and false for each @p i
1630  * in the range @p [middle,last).
1631  *
1632  * Performs the same function as @p partition() with the additional
1633  * guarantee that the relative ordering of elements in each group is
1634  * preserved, so any two elements @p x and @p y in the range
1635  * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1636  * relative ordering after calling @p stable_partition().
1637  */
1638  template<typename _ForwardIterator, typename _Predicate>
1639  inline _ForwardIterator
1640  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1641  _Predicate __pred)
1642  {
1643  // concept requirements
1644  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1645  _ForwardIterator>)
1646  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1647  typename iterator_traits<_ForwardIterator>::value_type>)
1648  __glibcxx_requires_valid_range(__first, __last);
1649 
1650  return std::__stable_partition(__first, __last,
1651  __gnu_cxx::__ops::__pred_iter(__pred));
1652  }
1653 
1654  /// This is a helper function for the sort routines.
1655  template<typename _RandomAccessIterator, typename _Compare>
1656  void
1657  __heap_select(_RandomAccessIterator __first,
1658  _RandomAccessIterator __middle,
1659  _RandomAccessIterator __last, _Compare __comp)
1660  {
1661  std::__make_heap(__first, __middle, __comp);
1662  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1663  if (__comp(__i, __first))
1664  std::__pop_heap(__first, __middle, __i, __comp);
1665  }
1666 
1667  // partial_sort
1668 
1669  template<typename _InputIterator, typename _RandomAccessIterator,
1670  typename _Compare>
1671  _RandomAccessIterator
1672  __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1673  _RandomAccessIterator __result_first,
1674  _RandomAccessIterator __result_last,
1675  _Compare __comp)
1676  {
1677  typedef typename iterator_traits<_InputIterator>::value_type
1678  _InputValueType;
1679  typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1680  typedef typename _RItTraits::difference_type _DistanceType;
1681 
1682  if (__result_first == __result_last)
1683  return __result_last;
1684  _RandomAccessIterator __result_real_last = __result_first;
1685  while (__first != __last && __result_real_last != __result_last)
1686  {
1687  *__result_real_last = *__first;
1688  ++__result_real_last;
1689  ++__first;
1690  }
1691 
1692  std::__make_heap(__result_first, __result_real_last, __comp);
1693  while (__first != __last)
1694  {
1695  if (__comp(__first, __result_first))
1696  std::__adjust_heap(__result_first, _DistanceType(0),
1697  _DistanceType(__result_real_last
1698  - __result_first),
1699  _InputValueType(*__first), __comp);
1700  ++__first;
1701  }
1702  std::__sort_heap(__result_first, __result_real_last, __comp);
1703  return __result_real_last;
1704  }
1705 
1706  /**
1707  * @brief Copy the smallest elements of a sequence.
1708  * @ingroup sorting_algorithms
1709  * @param __first An iterator.
1710  * @param __last Another iterator.
1711  * @param __result_first A random-access iterator.
1712  * @param __result_last Another random-access iterator.
1713  * @return An iterator indicating the end of the resulting sequence.
1714  *
1715  * Copies and sorts the smallest N values from the range @p [__first,__last)
1716  * to the range beginning at @p __result_first, where the number of
1717  * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1718  * @p (__result_last-__result_first).
1719  * After the sort if @e i and @e j are iterators in the range
1720  * @p [__result_first,__result_first+N) such that i precedes j then
1721  * *j<*i is false.
1722  * The value returned is @p __result_first+N.
1723  */
1724  template<typename _InputIterator, typename _RandomAccessIterator>
1725  inline _RandomAccessIterator
1726  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1727  _RandomAccessIterator __result_first,
1728  _RandomAccessIterator __result_last)
1729  {
1730 #ifdef _GLIBCXX_CONCEPT_CHECKS
1731  typedef typename iterator_traits<_InputIterator>::value_type
1732  _InputValueType;
1733  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1734  _OutputValueType;
1735 #endif
1736 
1737  // concept requirements
1738  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1739  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1740  _OutputValueType>)
1741  __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1742  _OutputValueType>)
1743  __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1744  __glibcxx_requires_valid_range(__first, __last);
1745  __glibcxx_requires_irreflexive(__first, __last);
1746  __glibcxx_requires_valid_range(__result_first, __result_last);
1747 
1748  return std::__partial_sort_copy(__first, __last,
1749  __result_first, __result_last,
1750  __gnu_cxx::__ops::__iter_less_iter());
1751  }
1752 
1753  /**
1754  * @brief Copy the smallest elements of a sequence using a predicate for
1755  * comparison.
1756  * @ingroup sorting_algorithms
1757  * @param __first An input iterator.
1758  * @param __last Another input iterator.
1759  * @param __result_first A random-access iterator.
1760  * @param __result_last Another random-access iterator.
1761  * @param __comp A comparison functor.
1762  * @return An iterator indicating the end of the resulting sequence.
1763  *
1764  * Copies and sorts the smallest N values from the range @p [__first,__last)
1765  * to the range beginning at @p result_first, where the number of
1766  * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1767  * @p (__result_last-__result_first).
1768  * After the sort if @e i and @e j are iterators in the range
1769  * @p [__result_first,__result_first+N) such that i precedes j then
1770  * @p __comp(*j,*i) is false.
1771  * The value returned is @p __result_first+N.
1772  */
1773  template<typename _InputIterator, typename _RandomAccessIterator,
1774  typename _Compare>
1775  inline _RandomAccessIterator
1776  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1777  _RandomAccessIterator __result_first,
1778  _RandomAccessIterator __result_last,
1779  _Compare __comp)
1780  {
1781 #ifdef _GLIBCXX_CONCEPT_CHECKS
1782  typedef typename iterator_traits<_InputIterator>::value_type
1783  _InputValueType;
1784  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1785  _OutputValueType;
1786 #endif
1787 
1788  // concept requirements
1789  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1790  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1791  _RandomAccessIterator>)
1792  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1793  _OutputValueType>)
1794  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1795  _InputValueType, _OutputValueType>)
1796  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1797  _OutputValueType, _OutputValueType>)
1798  __glibcxx_requires_valid_range(__first, __last);
1799  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1800  __glibcxx_requires_valid_range(__result_first, __result_last);
1801 
1802  return std::__partial_sort_copy(__first, __last,
1803  __result_first, __result_last,
1804  __gnu_cxx::__ops::__iter_comp_iter(__comp));
1805  }
1806 
1807  /// This is a helper function for the sort routine.
1808  template<typename _RandomAccessIterator, typename _Compare>
1809  void
1810  __unguarded_linear_insert(_RandomAccessIterator __last,
1811  _Compare __comp)
1812  {
1813  typename iterator_traits<_RandomAccessIterator>::value_type
1814  __val = _GLIBCXX_MOVE(*__last);
1815  _RandomAccessIterator __next = __last;
1816  --__next;
1817  while (__comp(__val, __next))
1818  {
1819  *__last = _GLIBCXX_MOVE(*__next);
1820  __last = __next;
1821  --__next;
1822  }
1823  *__last = _GLIBCXX_MOVE(__val);
1824  }
1825 
1826  /// This is a helper function for the sort routine.
1827  template<typename _RandomAccessIterator, typename _Compare>
1828  void
1829  __insertion_sort(_RandomAccessIterator __first,
1830  _RandomAccessIterator __last, _Compare __comp)
1831  {
1832  if (__first == __last) return;
1833 
1834  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1835  {
1836  if (__comp(__i, __first))
1837  {
1838  typename iterator_traits<_RandomAccessIterator>::value_type
1839  __val = _GLIBCXX_MOVE(*__i);
1840  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1841  *__first = _GLIBCXX_MOVE(__val);
1842  }
1843  else
1845  __gnu_cxx::__ops::__val_comp_iter(__comp));
1846  }
1847  }
1848 
1849  /// This is a helper function for the sort routine.
1850  template<typename _RandomAccessIterator, typename _Compare>
1851  inline void
1852  __unguarded_insertion_sort(_RandomAccessIterator __first,
1853  _RandomAccessIterator __last, _Compare __comp)
1854  {
1855  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1857  __gnu_cxx::__ops::__val_comp_iter(__comp));
1858  }
1859 
1860  /**
1861  * @doctodo
1862  * This controls some aspect of the sort routines.
1863  */
1864  enum { _S_threshold = 16 };
1865 
1866  /// This is a helper function for the sort routine.
1867  template<typename _RandomAccessIterator, typename _Compare>
1868  void
1869  __final_insertion_sort(_RandomAccessIterator __first,
1870  _RandomAccessIterator __last, _Compare __comp)
1871  {
1872  if (__last - __first > int(_S_threshold))
1873  {
1874  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1875  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1876  __comp);
1877  }
1878  else
1879  std::__insertion_sort(__first, __last, __comp);
1880  }
1881 
1882  /// This is a helper function...
1883  template<typename _RandomAccessIterator, typename _Compare>
1884  _RandomAccessIterator
1885  __unguarded_partition(_RandomAccessIterator __first,
1886  _RandomAccessIterator __last,
1887  _RandomAccessIterator __pivot, _Compare __comp)
1888  {
1889  while (true)
1890  {
1891  while (__comp(__first, __pivot))
1892  ++__first;
1893  --__last;
1894  while (__comp(__pivot, __last))
1895  --__last;
1896  if (!(__first < __last))
1897  return __first;
1898  std::iter_swap(__first, __last);
1899  ++__first;
1900  }
1901  }
1902 
1903  /// This is a helper function...
1904  template<typename _RandomAccessIterator, typename _Compare>
1905  inline _RandomAccessIterator
1906  __unguarded_partition_pivot(_RandomAccessIterator __first,
1907  _RandomAccessIterator __last, _Compare __comp)
1908  {
1909  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1910  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1911  __comp);
1912  return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1913  }
1914 
1915  template<typename _RandomAccessIterator, typename _Compare>
1916  inline void
1917  __partial_sort(_RandomAccessIterator __first,
1918  _RandomAccessIterator __middle,
1919  _RandomAccessIterator __last,
1920  _Compare __comp)
1921  {
1922  std::__heap_select(__first, __middle, __last, __comp);
1923  std::__sort_heap(__first, __middle, __comp);
1924  }
1925 
1926  /// This is a helper function for the sort routine.
1927  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1928  void
1929  __introsort_loop(_RandomAccessIterator __first,
1930  _RandomAccessIterator __last,
1931  _Size __depth_limit, _Compare __comp)
1932  {
1933  while (__last - __first > int(_S_threshold))
1934  {
1935  if (__depth_limit == 0)
1936  {
1937  std::__partial_sort(__first, __last, __last, __comp);
1938  return;
1939  }
1940  --__depth_limit;
1941  _RandomAccessIterator __cut =
1942  std::__unguarded_partition_pivot(__first, __last, __comp);
1943  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1944  __last = __cut;
1945  }
1946  }
1947 
1948  // sort
1949 
1950  template<typename _RandomAccessIterator, typename _Compare>
1951  inline void
1952  __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1953  _Compare __comp)
1954  {
1955  if (__first != __last)
1956  {
1957  std::__introsort_loop(__first, __last,
1958  std::__lg(__last - __first) * 2,
1959  __comp);
1960  std::__final_insertion_sort(__first, __last, __comp);
1961  }
1962  }
1963 
1964  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1965  void
1966  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1967  _RandomAccessIterator __last, _Size __depth_limit,
1968  _Compare __comp)
1969  {
1970  while (__last - __first > 3)
1971  {
1972  if (__depth_limit == 0)
1973  {
1974  std::__heap_select(__first, __nth + 1, __last, __comp);
1975  // Place the nth largest element in its final position.
1976  std::iter_swap(__first, __nth);
1977  return;
1978  }
1979  --__depth_limit;
1980  _RandomAccessIterator __cut =
1981  std::__unguarded_partition_pivot(__first, __last, __comp);
1982  if (__cut <= __nth)
1983  __first = __cut;
1984  else
1985  __last = __cut;
1986  }
1987  std::__insertion_sort(__first, __last, __comp);
1988  }
1989 
1990  // nth_element
1991 
1992  // lower_bound moved to stl_algobase.h
1993 
1994  /**
1995  * @brief Finds the first position in which @p __val could be inserted
1996  * without changing the ordering.
1997  * @ingroup binary_search_algorithms
1998  * @param __first An iterator.
1999  * @param __last Another iterator.
2000  * @param __val The search term.
2001  * @param __comp A functor to use for comparisons.
2002  * @return An iterator pointing to the first element <em>not less
2003  * than</em> @p __val, or end() if every element is less
2004  * than @p __val.
2005  * @ingroup binary_search_algorithms
2006  *
2007  * The comparison function should have the same effects on ordering as
2008  * the function used for the initial sort.
2009  */
2010  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2011  inline _ForwardIterator
2012  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2013  const _Tp& __val, _Compare __comp)
2014  {
2015  // concept requirements
2016  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2017  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2018  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2019  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2020  __val, __comp);
2021 
2022  return std::__lower_bound(__first, __last, __val,
2023  __gnu_cxx::__ops::__iter_comp_val(__comp));
2024  }
2025 
2026  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2027  _ForwardIterator
2028  __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2029  const _Tp& __val, _Compare __comp)
2030  {
2031  typedef typename iterator_traits<_ForwardIterator>::difference_type
2032  _DistanceType;
2033 
2034  _DistanceType __len = std::distance(__first, __last);
2035 
2036  while (__len > 0)
2037  {
2038  _DistanceType __half = __len >> 1;
2039  _ForwardIterator __middle = __first;
2040  std::advance(__middle, __half);
2041  if (__comp(__val, __middle))
2042  __len = __half;
2043  else
2044  {
2045  __first = __middle;
2046  ++__first;
2047  __len = __len - __half - 1;
2048  }
2049  }
2050  return __first;
2051  }
2052 
2053  /**
2054  * @brief Finds the last position in which @p __val could be inserted
2055  * without changing the ordering.
2056  * @ingroup binary_search_algorithms
2057  * @param __first An iterator.
2058  * @param __last Another iterator.
2059  * @param __val The search term.
2060  * @return An iterator pointing to the first element greater than @p __val,
2061  * or end() if no elements are greater than @p __val.
2062  * @ingroup binary_search_algorithms
2063  */
2064  template<typename _ForwardIterator, typename _Tp>
2065  inline _ForwardIterator
2066  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2067  const _Tp& __val)
2068  {
2069  // concept requirements
2070  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2071  __glibcxx_function_requires(_LessThanOpConcept<
2072  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2073  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2074 
2075  return std::__upper_bound(__first, __last, __val,
2076  __gnu_cxx::__ops::__val_less_iter());
2077  }
2078 
2079  /**
2080  * @brief Finds the last position in which @p __val could be inserted
2081  * without changing the ordering.
2082  * @ingroup binary_search_algorithms
2083  * @param __first An iterator.
2084  * @param __last Another iterator.
2085  * @param __val The search term.
2086  * @param __comp A functor to use for comparisons.
2087  * @return An iterator pointing to the first element greater than @p __val,
2088  * or end() if no elements are greater than @p __val.
2089  * @ingroup binary_search_algorithms
2090  *
2091  * The comparison function should have the same effects on ordering as
2092  * the function used for the initial sort.
2093  */
2094  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2095  inline _ForwardIterator
2096  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2097  const _Tp& __val, _Compare __comp)
2098  {
2099  // concept requirements
2100  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2101  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2102  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2103  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2104  __val, __comp);
2105 
2106  return std::__upper_bound(__first, __last, __val,
2107  __gnu_cxx::__ops::__val_comp_iter(__comp));
2108  }
2109 
2110  template<typename _ForwardIterator, typename _Tp,
2111  typename _CompareItTp, typename _CompareTpIt>
2112  pair<_ForwardIterator, _ForwardIterator>
2113  __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2114  const _Tp& __val,
2115  _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2116  {
2117  typedef typename iterator_traits<_ForwardIterator>::difference_type
2118  _DistanceType;
2119 
2120  _DistanceType __len = std::distance(__first, __last);
2121 
2122  while (__len > 0)
2123  {
2124  _DistanceType __half = __len >> 1;
2125  _ForwardIterator __middle = __first;
2126  std::advance(__middle, __half);
2127  if (__comp_it_val(__middle, __val))
2128  {
2129  __first = __middle;
2130  ++__first;
2131  __len = __len - __half - 1;
2132  }
2133  else if (__comp_val_it(__val, __middle))
2134  __len = __half;
2135  else
2136  {
2137  _ForwardIterator __left
2138  = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2139  std::advance(__first, __len);
2140  _ForwardIterator __right
2141  = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2142  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2143  }
2144  }
2145  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2146  }
2147 
2148  /**
2149  * @brief Finds the largest subrange in which @p __val could be inserted
2150  * at any place in it without changing the ordering.
2151  * @ingroup binary_search_algorithms
2152  * @param __first An iterator.
2153  * @param __last Another iterator.
2154  * @param __val The search term.
2155  * @return An pair of iterators defining the subrange.
2156  * @ingroup binary_search_algorithms
2157  *
2158  * This is equivalent to
2159  * @code
2160  * std::make_pair(lower_bound(__first, __last, __val),
2161  * upper_bound(__first, __last, __val))
2162  * @endcode
2163  * but does not actually call those functions.
2164  */
2165  template<typename _ForwardIterator, typename _Tp>
2166  inline pair<_ForwardIterator, _ForwardIterator>
2167  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2168  const _Tp& __val)
2169  {
2170  // concept requirements
2171  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2172  __glibcxx_function_requires(_LessThanOpConcept<
2173  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2174  __glibcxx_function_requires(_LessThanOpConcept<
2175  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2176  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2177  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2178 
2179  return std::__equal_range(__first, __last, __val,
2180  __gnu_cxx::__ops::__iter_less_val(),
2181  __gnu_cxx::__ops::__val_less_iter());
2182  }
2183 
2184  /**
2185  * @brief Finds the largest subrange in which @p __val could be inserted
2186  * at any place in it without changing the ordering.
2187  * @param __first An iterator.
2188  * @param __last Another iterator.
2189  * @param __val The search term.
2190  * @param __comp A functor to use for comparisons.
2191  * @return An pair of iterators defining the subrange.
2192  * @ingroup binary_search_algorithms
2193  *
2194  * This is equivalent to
2195  * @code
2196  * std::make_pair(lower_bound(__first, __last, __val, __comp),
2197  * upper_bound(__first, __last, __val, __comp))
2198  * @endcode
2199  * but does not actually call those functions.
2200  */
2201  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2202  inline pair<_ForwardIterator, _ForwardIterator>
2203  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2204  const _Tp& __val, _Compare __comp)
2205  {
2206  // concept requirements
2207  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2208  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2209  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2210  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2211  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2212  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2213  __val, __comp);
2214  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2215  __val, __comp);
2216 
2217  return std::__equal_range(__first, __last, __val,
2218  __gnu_cxx::__ops::__iter_comp_val(__comp),
2219  __gnu_cxx::__ops::__val_comp_iter(__comp));
2220  }
2221 
2222  /**
2223  * @brief Determines whether an element exists in a range.
2224  * @ingroup binary_search_algorithms
2225  * @param __first An iterator.
2226  * @param __last Another iterator.
2227  * @param __val The search term.
2228  * @return True if @p __val (or its equivalent) is in [@p
2229  * __first,@p __last ].
2230  *
2231  * Note that this does not actually return an iterator to @p __val. For
2232  * that, use std::find or a container's specialized find member functions.
2233  */
2234  template<typename _ForwardIterator, typename _Tp>
2235  bool
2236  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2237  const _Tp& __val)
2238  {
2239  // concept requirements
2240  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2241  __glibcxx_function_requires(_LessThanOpConcept<
2242  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2243  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2244  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2245 
2246  _ForwardIterator __i
2247  = std::__lower_bound(__first, __last, __val,
2248  __gnu_cxx::__ops::__iter_less_val());
2249  return __i != __last && !(__val < *__i);
2250  }
2251 
2252  /**
2253  * @brief Determines whether an element exists in a range.
2254  * @ingroup binary_search_algorithms
2255  * @param __first An iterator.
2256  * @param __last Another iterator.
2257  * @param __val The search term.
2258  * @param __comp A functor to use for comparisons.
2259  * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2260  *
2261  * Note that this does not actually return an iterator to @p __val. For
2262  * that, use std::find or a container's specialized find member functions.
2263  *
2264  * The comparison function should have the same effects on ordering as
2265  * the function used for the initial sort.
2266  */
2267  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2268  bool
2269  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2270  const _Tp& __val, _Compare __comp)
2271  {
2272  // concept requirements
2273  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2274  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2275  _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2276  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2277  __val, __comp);
2278  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2279  __val, __comp);
2280 
2281  _ForwardIterator __i
2282  = std::__lower_bound(__first, __last, __val,
2283  __gnu_cxx::__ops::__iter_comp_val(__comp));
2284  return __i != __last && !bool(__comp(__val, *__i));
2285  }
2286 
2287  // merge
2288 
2289  /// This is a helper function for the __merge_adaptive routines.
2290  template<typename _InputIterator1, typename _InputIterator2,
2291  typename _OutputIterator, typename _Compare>
2292  void
2293  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2294  _InputIterator2 __first2, _InputIterator2 __last2,
2295  _OutputIterator __result, _Compare __comp)
2296  {
2297  while (__first1 != __last1 && __first2 != __last2)
2298  {
2299  if (__comp(__first2, __first1))
2300  {
2301  *__result = _GLIBCXX_MOVE(*__first2);
2302  ++__first2;
2303  }
2304  else
2305  {
2306  *__result = _GLIBCXX_MOVE(*__first1);
2307  ++__first1;
2308  }
2309  ++__result;
2310  }
2311  if (__first1 != __last1)
2312  _GLIBCXX_MOVE3(__first1, __last1, __result);
2313  }
2314 
2315  /// This is a helper function for the __merge_adaptive routines.
2316  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2317  typename _BidirectionalIterator3, typename _Compare>
2318  void
2319  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2320  _BidirectionalIterator1 __last1,
2321  _BidirectionalIterator2 __first2,
2322  _BidirectionalIterator2 __last2,
2323  _BidirectionalIterator3 __result,
2324  _Compare __comp)
2325  {
2326  if (__first1 == __last1)
2327  {
2328  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2329  return;
2330  }
2331  else if (__first2 == __last2)
2332  return;
2333 
2334  --__last1;
2335  --__last2;
2336  while (true)
2337  {
2338  if (__comp(__last2, __last1))
2339  {
2340  *--__result = _GLIBCXX_MOVE(*__last1);
2341  if (__first1 == __last1)
2342  {
2343  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2344  return;
2345  }
2346  --__last1;
2347  }
2348  else
2349  {
2350  *--__result = _GLIBCXX_MOVE(*__last2);
2351  if (__first2 == __last2)
2352  return;
2353  --__last2;
2354  }
2355  }
2356  }
2357 
2358  /// This is a helper function for the merge routines.
2359  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2360  typename _Distance>
2361  _BidirectionalIterator1
2362  __rotate_adaptive(_BidirectionalIterator1 __first,
2363  _BidirectionalIterator1 __middle,
2364  _BidirectionalIterator1 __last,
2365  _Distance __len1, _Distance __len2,
2366  _BidirectionalIterator2 __buffer,
2367  _Distance __buffer_size)
2368  {
2369  _BidirectionalIterator2 __buffer_end;
2370  if (__len1 > __len2 && __len2 <= __buffer_size)
2371  {
2372  if (__len2)
2373  {
2374  __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2375  _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2376  return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2377  }
2378  else
2379  return __first;
2380  }
2381  else if (__len1 <= __buffer_size)
2382  {
2383  if (__len1)
2384  {
2385  __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2386  _GLIBCXX_MOVE3(__middle, __last, __first);
2387  return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2388  }
2389  else
2390  return __last;
2391  }
2392  else
2393  return std::rotate(__first, __middle, __last);
2394  }
2395 
2396  /// This is a helper function for the merge routines.
2397  template<typename _BidirectionalIterator, typename _Distance,
2398  typename _Pointer, typename _Compare>
2399  void
2400  __merge_adaptive(_BidirectionalIterator __first,
2401  _BidirectionalIterator __middle,
2402  _BidirectionalIterator __last,
2403  _Distance __len1, _Distance __len2,
2404  _Pointer __buffer, _Distance __buffer_size,
2405  _Compare __comp)
2406  {
2407  if (__len1 <= __len2 && __len1 <= __buffer_size)
2408  {
2409  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2410  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2411  __first, __comp);
2412  }
2413  else if (__len2 <= __buffer_size)
2414  {
2415  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2416  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2417  __buffer_end, __last, __comp);
2418  }
2419  else
2420  {
2421  _BidirectionalIterator __first_cut = __first;
2422  _BidirectionalIterator __second_cut = __middle;
2423  _Distance __len11 = 0;
2424  _Distance __len22 = 0;
2425  if (__len1 > __len2)
2426  {
2427  __len11 = __len1 / 2;
2428  std::advance(__first_cut, __len11);
2429  __second_cut
2430  = std::__lower_bound(__middle, __last, *__first_cut,
2431  __gnu_cxx::__ops::__iter_comp_val(__comp));
2432  __len22 = std::distance(__middle, __second_cut);
2433  }
2434  else
2435  {
2436  __len22 = __len2 / 2;
2437  std::advance(__second_cut, __len22);
2438  __first_cut
2439  = std::__upper_bound(__first, __middle, *__second_cut,
2440  __gnu_cxx::__ops::__val_comp_iter(__comp));
2441  __len11 = std::distance(__first, __first_cut);
2442  }
2443 
2444  _BidirectionalIterator __new_middle
2445  = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2446  __len1 - __len11, __len22, __buffer,
2447  __buffer_size);
2448  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2449  __len22, __buffer, __buffer_size, __comp);
2450  std::__merge_adaptive(__new_middle, __second_cut, __last,
2451  __len1 - __len11,
2452  __len2 - __len22, __buffer,
2453  __buffer_size, __comp);
2454  }
2455  }
2456 
2457  /// This is a helper function for the merge routines.
2458  template<typename _BidirectionalIterator, typename _Distance,
2459  typename _Compare>
2460  void
2461  __merge_without_buffer(_BidirectionalIterator __first,
2462  _BidirectionalIterator __middle,
2463  _BidirectionalIterator __last,
2464  _Distance __len1, _Distance __len2,
2465  _Compare __comp)
2466  {
2467  if (__len1 == 0 || __len2 == 0)
2468  return;
2469 
2470  if (__len1 + __len2 == 2)
2471  {
2472  if (__comp(__middle, __first))
2473  std::iter_swap(__first, __middle);
2474  return;
2475  }
2476 
2477  _BidirectionalIterator __first_cut = __first;
2478  _BidirectionalIterator __second_cut = __middle;
2479  _Distance __len11 = 0;
2480  _Distance __len22 = 0;
2481  if (__len1 > __len2)
2482  {
2483  __len11 = __len1 / 2;
2484  std::advance(__first_cut, __len11);
2485  __second_cut
2486  = std::__lower_bound(__middle, __last, *__first_cut,
2487  __gnu_cxx::__ops::__iter_comp_val(__comp));
2488  __len22 = std::distance(__middle, __second_cut);
2489  }
2490  else
2491  {
2492  __len22 = __len2 / 2;
2493  std::advance(__second_cut, __len22);
2494  __first_cut
2495  = std::__upper_bound(__first, __middle, *__second_cut,
2496  __gnu_cxx::__ops::__val_comp_iter(__comp));
2497  __len11 = std::distance(__first, __first_cut);
2498  }
2499 
2500  _BidirectionalIterator __new_middle
2501  = std::rotate(__first_cut, __middle, __second_cut);
2502  std::__merge_without_buffer(__first, __first_cut, __new_middle,
2503  __len11, __len22, __comp);
2504  std::__merge_without_buffer(__new_middle, __second_cut, __last,
2505  __len1 - __len11, __len2 - __len22, __comp);
2506  }
2507 
2508  template<typename _BidirectionalIterator, typename _Compare>
2509  void
2510  __inplace_merge(_BidirectionalIterator __first,
2511  _BidirectionalIterator __middle,
2512  _BidirectionalIterator __last,
2513  _Compare __comp)
2514  {
2515  typedef typename iterator_traits<_BidirectionalIterator>::value_type
2516  _ValueType;
2517  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2518  _DistanceType;
2519 
2520  if (__first == __middle || __middle == __last)
2521  return;
2522 
2523  const _DistanceType __len1 = std::distance(__first, __middle);
2524  const _DistanceType __len2 = std::distance(__middle, __last);
2525 
2526  typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2527  _TmpBuf __buf(__first, __len1 + __len2);
2528 
2529  if (__buf.begin() == 0)
2531  (__first, __middle, __last, __len1, __len2, __comp);
2532  else
2534  (__first, __middle, __last, __len1, __len2, __buf.begin(),
2535  _DistanceType(__buf.size()), __comp);
2536  }
2537 
2538  /**
2539  * @brief Merges two sorted ranges in place.
2540  * @ingroup sorting_algorithms
2541  * @param __first An iterator.
2542  * @param __middle Another iterator.
2543  * @param __last Another iterator.
2544  * @return Nothing.
2545  *
2546  * Merges two sorted and consecutive ranges, [__first,__middle) and
2547  * [__middle,__last), and puts the result in [__first,__last). The
2548  * output will be sorted. The sort is @e stable, that is, for
2549  * equivalent elements in the two ranges, elements from the first
2550  * range will always come before elements from the second.
2551  *
2552  * If enough additional memory is available, this takes (__last-__first)-1
2553  * comparisons. Otherwise an NlogN algorithm is used, where N is
2554  * distance(__first,__last).
2555  */
2556  template<typename _BidirectionalIterator>
2557  inline void
2558  inplace_merge(_BidirectionalIterator __first,
2559  _BidirectionalIterator __middle,
2560  _BidirectionalIterator __last)
2561  {
2562  // concept requirements
2563  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2564  _BidirectionalIterator>)
2565  __glibcxx_function_requires(_LessThanComparableConcept<
2566  typename iterator_traits<_BidirectionalIterator>::value_type>)
2567  __glibcxx_requires_sorted(__first, __middle);
2568  __glibcxx_requires_sorted(__middle, __last);
2569  __glibcxx_requires_irreflexive(__first, __last);
2570 
2571  std::__inplace_merge(__first, __middle, __last,
2572  __gnu_cxx::__ops::__iter_less_iter());
2573  }
2574 
2575  /**
2576  * @brief Merges two sorted ranges in place.
2577  * @ingroup sorting_algorithms
2578  * @param __first An iterator.
2579  * @param __middle Another iterator.
2580  * @param __last Another iterator.
2581  * @param __comp A functor to use for comparisons.
2582  * @return Nothing.
2583  *
2584  * Merges two sorted and consecutive ranges, [__first,__middle) and
2585  * [middle,last), and puts the result in [__first,__last). The output will
2586  * be sorted. The sort is @e stable, that is, for equivalent
2587  * elements in the two ranges, elements from the first range will always
2588  * come before elements from the second.
2589  *
2590  * If enough additional memory is available, this takes (__last-__first)-1
2591  * comparisons. Otherwise an NlogN algorithm is used, where N is
2592  * distance(__first,__last).
2593  *
2594  * The comparison function should have the same effects on ordering as
2595  * the function used for the initial sort.
2596  */
2597  template<typename _BidirectionalIterator, typename _Compare>
2598  inline void
2599  inplace_merge(_BidirectionalIterator __first,
2600  _BidirectionalIterator __middle,
2601  _BidirectionalIterator __last,
2602  _Compare __comp)
2603  {
2604  // concept requirements
2605  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2606  _BidirectionalIterator>)
2607  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2608  typename iterator_traits<_BidirectionalIterator>::value_type,
2609  typename iterator_traits<_BidirectionalIterator>::value_type>)
2610  __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2611  __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2612  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2613 
2614  std::__inplace_merge(__first, __middle, __last,
2615  __gnu_cxx::__ops::__iter_comp_iter(__comp));
2616  }
2617 
2618 
2619  /// This is a helper function for the __merge_sort_loop routines.
2620  template<typename _InputIterator, typename _OutputIterator,
2621  typename _Compare>
2622  _OutputIterator
2623  __move_merge(_InputIterator __first1, _InputIterator __last1,
2624  _InputIterator __first2, _InputIterator __last2,
2625  _OutputIterator __result, _Compare __comp)
2626  {
2627  while (__first1 != __last1 && __first2 != __last2)
2628  {
2629  if (__comp(__first2, __first1))
2630  {
2631  *__result = _GLIBCXX_MOVE(*__first2);
2632  ++__first2;
2633  }
2634  else
2635  {
2636  *__result = _GLIBCXX_MOVE(*__first1);
2637  ++__first1;
2638  }
2639  ++__result;
2640  }
2641  return _GLIBCXX_MOVE3(__first2, __last2,
2642  _GLIBCXX_MOVE3(__first1, __last1,
2643  __result));
2644  }
2645 
2646  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2647  typename _Distance, typename _Compare>
2648  void
2649  __merge_sort_loop(_RandomAccessIterator1 __first,
2650  _RandomAccessIterator1 __last,
2651  _RandomAccessIterator2 __result, _Distance __step_size,
2652  _Compare __comp)
2653  {
2654  const _Distance __two_step = 2 * __step_size;
2655 
2656  while (__last - __first >= __two_step)
2657  {
2658  __result = std::__move_merge(__first, __first + __step_size,
2659  __first + __step_size,
2660  __first + __two_step,
2661  __result, __comp);
2662  __first += __two_step;
2663  }
2664  __step_size = std::min(_Distance(__last - __first), __step_size);
2665 
2666  std::__move_merge(__first, __first + __step_size,
2667  __first + __step_size, __last, __result, __comp);
2668  }
2669 
2670  template<typename _RandomAccessIterator, typename _Distance,
2671  typename _Compare>
2672  void
2673  __chunk_insertion_sort(_RandomAccessIterator __first,
2674  _RandomAccessIterator __last,
2675  _Distance __chunk_size, _Compare __comp)
2676  {
2677  while (__last - __first >= __chunk_size)
2678  {
2679  std::__insertion_sort(__first, __first + __chunk_size, __comp);
2680  __first += __chunk_size;
2681  }
2682  std::__insertion_sort(__first, __last, __comp);
2683  }
2684 
2685  enum { _S_chunk_size = 7 };
2686 
2687  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2688  void
2689  __merge_sort_with_buffer(_RandomAccessIterator __first,
2690  _RandomAccessIterator __last,
2691  _Pointer __buffer, _Compare __comp)
2692  {
2693  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2694  _Distance;
2695 
2696  const _Distance __len = __last - __first;
2697  const _Pointer __buffer_last = __buffer + __len;
2698 
2699  _Distance __step_size = _S_chunk_size;
2700  std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2701 
2702  while (__step_size < __len)
2703  {
2704  std::__merge_sort_loop(__first, __last, __buffer,
2705  __step_size, __comp);
2706  __step_size *= 2;
2707  std::__merge_sort_loop(__buffer, __buffer_last, __first,
2708  __step_size, __comp);
2709  __step_size *= 2;
2710  }
2711  }
2712 
2713  template<typename _RandomAccessIterator, typename _Pointer,
2714  typename _Distance, typename _Compare>
2715  void
2716  __stable_sort_adaptive(_RandomAccessIterator __first,
2717  _RandomAccessIterator __last,
2718  _Pointer __buffer, _Distance __buffer_size,
2719  _Compare __comp)
2720  {
2721  const _Distance __len = (__last - __first + 1) / 2;
2722  const _RandomAccessIterator __middle = __first + __len;
2723  if (__len > __buffer_size)
2724  {
2725  std::__stable_sort_adaptive(__first, __middle, __buffer,
2726  __buffer_size, __comp);
2727  std::__stable_sort_adaptive(__middle, __last, __buffer,
2728  __buffer_size, __comp);
2729  }
2730  else
2731  {
2732  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2733  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2734  }
2735  std::__merge_adaptive(__first, __middle, __last,
2736  _Distance(__middle - __first),
2737  _Distance(__last - __middle),
2738  __buffer, __buffer_size,
2739  __comp);
2740  }
2741 
2742  /// This is a helper function for the stable sorting routines.
2743  template<typename _RandomAccessIterator, typename _Compare>
2744  void
2745  __inplace_stable_sort(_RandomAccessIterator __first,
2746  _RandomAccessIterator __last, _Compare __comp)
2747  {
2748  if (__last - __first < 15)
2749  {
2750  std::__insertion_sort(__first, __last, __comp);
2751  return;
2752  }
2753  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2754  std::__inplace_stable_sort(__first, __middle, __comp);
2755  std::__inplace_stable_sort(__middle, __last, __comp);
2756  std::__merge_without_buffer(__first, __middle, __last,
2757  __middle - __first,
2758  __last - __middle,
2759  __comp);
2760  }
2761 
2762  // stable_sort
2763 
2764  // Set algorithms: includes, set_union, set_intersection, set_difference,
2765  // set_symmetric_difference. All of these algorithms have the precondition
2766  // that their input ranges are sorted and the postcondition that their output
2767  // ranges are sorted.
2768 
2769  template<typename _InputIterator1, typename _InputIterator2,
2770  typename _Compare>
2771  bool
2772  __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2773  _InputIterator2 __first2, _InputIterator2 __last2,
2774  _Compare __comp)
2775  {
2776  while (__first1 != __last1 && __first2 != __last2)
2777  if (__comp(__first2, __first1))
2778  return false;
2779  else if (__comp(__first1, __first2))
2780  ++__first1;
2781  else
2782  {
2783  ++__first1;
2784  ++__first2;
2785  }
2786 
2787  return __first2 == __last2;
2788  }
2789 
2790  /**
2791  * @brief Determines whether all elements of a sequence exists in a range.
2792  * @param __first1 Start of search range.
2793  * @param __last1 End of search range.
2794  * @param __first2 Start of sequence
2795  * @param __last2 End of sequence.
2796  * @return True if each element in [__first2,__last2) is contained in order
2797  * within [__first1,__last1). False otherwise.
2798  * @ingroup set_algorithms
2799  *
2800  * This operation expects both [__first1,__last1) and
2801  * [__first2,__last2) to be sorted. Searches for the presence of
2802  * each element in [__first2,__last2) within [__first1,__last1).
2803  * The iterators over each range only move forward, so this is a
2804  * linear algorithm. If an element in [__first2,__last2) is not
2805  * found before the search iterator reaches @p __last2, false is
2806  * returned.
2807  */
2808  template<typename _InputIterator1, typename _InputIterator2>
2809  inline bool
2810  includes(_InputIterator1 __first1, _InputIterator1 __last1,
2811  _InputIterator2 __first2, _InputIterator2 __last2)
2812  {
2813  // concept requirements
2814  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2815  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2816  __glibcxx_function_requires(_LessThanOpConcept<
2817  typename iterator_traits<_InputIterator1>::value_type,
2818  typename iterator_traits<_InputIterator2>::value_type>)
2819  __glibcxx_function_requires(_LessThanOpConcept<
2820  typename iterator_traits<_InputIterator2>::value_type,
2821  typename iterator_traits<_InputIterator1>::value_type>)
2822  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2823  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2824  __glibcxx_requires_irreflexive2(__first1, __last1);
2825  __glibcxx_requires_irreflexive2(__first2, __last2);
2826 
2827  return std::__includes(__first1, __last1, __first2, __last2,
2828  __gnu_cxx::__ops::__iter_less_iter());
2829  }
2830 
2831  /**
2832  * @brief Determines whether all elements of a sequence exists in a range
2833  * using comparison.
2834  * @ingroup set_algorithms
2835  * @param __first1 Start of search range.
2836  * @param __last1 End of search range.
2837  * @param __first2 Start of sequence
2838  * @param __last2 End of sequence.
2839  * @param __comp Comparison function to use.
2840  * @return True if each element in [__first2,__last2) is contained
2841  * in order within [__first1,__last1) according to comp. False
2842  * otherwise. @ingroup set_algorithms
2843  *
2844  * This operation expects both [__first1,__last1) and
2845  * [__first2,__last2) to be sorted. Searches for the presence of
2846  * each element in [__first2,__last2) within [__first1,__last1),
2847  * using comp to decide. The iterators over each range only move
2848  * forward, so this is a linear algorithm. If an element in
2849  * [__first2,__last2) is not found before the search iterator
2850  * reaches @p __last2, false is returned.
2851  */
2852  template<typename _InputIterator1, typename _InputIterator2,
2853  typename _Compare>
2854  inline bool
2855  includes(_InputIterator1 __first1, _InputIterator1 __last1,
2856  _InputIterator2 __first2, _InputIterator2 __last2,
2857  _Compare __comp)
2858  {
2859  // concept requirements
2860  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2861  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2862  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2863  typename iterator_traits<_InputIterator1>::value_type,
2864  typename iterator_traits<_InputIterator2>::value_type>)
2865  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2866  typename iterator_traits<_InputIterator2>::value_type,
2867  typename iterator_traits<_InputIterator1>::value_type>)
2868  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2869  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2870  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2871  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2872 
2873  return std::__includes(__first1, __last1, __first2, __last2,
2874  __gnu_cxx::__ops::__iter_comp_iter(__comp));
2875  }
2876 
2877  // nth_element
2878  // merge
2879  // set_difference
2880  // set_intersection
2881  // set_union
2882  // stable_sort
2883  // set_symmetric_difference
2884  // min_element
2885  // max_element
2886 
2887  template<typename _BidirectionalIterator, typename _Compare>
2888  bool
2889  __next_permutation(_BidirectionalIterator __first,
2890  _BidirectionalIterator __last, _Compare __comp)
2891  {
2892  if (__first == __last)
2893  return false;
2894  _BidirectionalIterator __i = __first;
2895  ++__i;
2896  if (__i == __last)
2897  return false;
2898  __i = __last;
2899  --__i;
2900 
2901  for(;;)
2902  {
2903  _BidirectionalIterator __ii = __i;
2904  --__i;
2905  if (__comp(__i, __ii))
2906  {
2907  _BidirectionalIterator __j = __last;
2908  while (!__comp(__i, --__j))
2909  {}
2910  std::iter_swap(__i, __j);
2911  std::__reverse(__ii, __last,
2912  std::__iterator_category(__first));
2913  return true;
2914  }
2915  if (__i == __first)
2916  {
2917  std::__reverse(__first, __last,
2918  std::__iterator_category(__first));
2919  return false;
2920  }
2921  }
2922  }
2923 
2924  /**
2925  * @brief Permute range into the next @e dictionary ordering.
2926  * @ingroup sorting_algorithms
2927  * @param __first Start of range.
2928  * @param __last End of range.
2929  * @return False if wrapped to first permutation, true otherwise.
2930  *
2931  * Treats all permutations of the range as a set of @e dictionary sorted
2932  * sequences. Permutes the current sequence into the next one of this set.
2933  * Returns true if there are more sequences to generate. If the sequence
2934  * is the largest of the set, the smallest is generated and false returned.
2935  */
2936  template<typename _BidirectionalIterator>
2937  inline bool
2938  next_permutation(_BidirectionalIterator __first,
2939  _BidirectionalIterator __last)
2940  {
2941  // concept requirements
2942  __glibcxx_function_requires(_BidirectionalIteratorConcept<
2943  _BidirectionalIterator>)
2944  __glibcxx_function_requires(_LessThanComparableConcept<
2945  typename iterator_traits<_BidirectionalIterator>::value_type>)
2946  __glibcxx_requires_valid_range(__first, __last);
2947  __glibcxx_requires_irreflexive(__first, __last);
2948 
2949  return std::__next_permutation
2950  (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2951  }
2952 
2953  /**
2954  * @brief Permute range into the next @e dictionary ordering using
2955  * comparison functor.
2956  * @ingroup sorting_algorithms
2957  * @param __first Start of range.
2958  * @param __last End of range.
2959  * @param __comp A comparison functor.
2960  * @return False if wrapped to first permutation, true otherwise.
2961  *
2962  * Treats all permutations of the range [__first,__last) as a set of
2963  * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2964  * sequence into the next one of this set. Returns true if there are more
2965  * sequences to generate. If the sequence is the largest of the set, the
2966  * smallest is generated and false returned.
2967  */
2968  template<typename _BidirectionalIterator, typename _Compare>
2969  inline bool
2970  next_permutation(_BidirectionalIterator __first,
2971  _BidirectionalIterator __last, _Compare __comp)
2972  {
2973  // concept requirements
2974  __glibcxx_function_requires(_BidirectionalIteratorConcept<
2975  _BidirectionalIterator>)
2976  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2977  typename iterator_traits<_BidirectionalIterator>::value_type,
2978  typename iterator_traits<_BidirectionalIterator>::value_type>)
2979  __glibcxx_requires_valid_range(__first, __last);
2980  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2981 
2982  return std::__next_permutation
2983  (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2984  }
2985 
2986  template<typename _BidirectionalIterator, typename _Compare>
2987  bool
2988  __prev_permutation(_BidirectionalIterator __first,
2989  _BidirectionalIterator __last, _Compare __comp)
2990  {
2991  if (__first == __last)
2992  return false;
2993  _BidirectionalIterator __i = __first;
2994  ++__i;
2995  if (__i == __last)
2996  return false;
2997  __i = __last;
2998  --__i;
2999 
3000  for(;;)
3001  {
3002  _BidirectionalIterator __ii = __i;
3003  --__i;
3004  if (__comp(__ii, __i))
3005  {
3006  _BidirectionalIterator __j = __last;
3007  while (!__comp(--__j, __i))
3008  {}
3009  std::iter_swap(__i, __j);
3010  std::__reverse(__ii, __last,
3011  std::__iterator_category(__first));
3012  return true;
3013  }
3014  if (__i == __first)
3015  {
3016  std::__reverse(__first, __last,
3017  std::__iterator_category(__first));
3018  return false;
3019  }
3020  }
3021  }
3022 
3023  /**
3024  * @brief Permute range into the previous @e dictionary ordering.
3025  * @ingroup sorting_algorithms
3026  * @param __first Start of range.
3027  * @param __last End of range.
3028  * @return False if wrapped to last permutation, true otherwise.
3029  *
3030  * Treats all permutations of the range as a set of @e dictionary sorted
3031  * sequences. Permutes the current sequence into the previous one of this
3032  * set. Returns true if there are more sequences to generate. If the
3033  * sequence is the smallest of the set, the largest is generated and false
3034  * returned.
3035  */
3036  template<typename _BidirectionalIterator>
3037  inline bool
3038  prev_permutation(_BidirectionalIterator __first,
3039  _BidirectionalIterator __last)
3040  {
3041  // concept requirements
3042  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3043  _BidirectionalIterator>)
3044  __glibcxx_function_requires(_LessThanComparableConcept<
3045  typename iterator_traits<_BidirectionalIterator>::value_type>)
3046  __glibcxx_requires_valid_range(__first, __last);
3047  __glibcxx_requires_irreflexive(__first, __last);
3048 
3049  return std::__prev_permutation(__first, __last,
3050  __gnu_cxx::__ops::__iter_less_iter());
3051  }
3052 
3053  /**
3054  * @brief Permute range into the previous @e dictionary ordering using
3055  * comparison functor.
3056  * @ingroup sorting_algorithms
3057  * @param __first Start of range.
3058  * @param __last End of range.
3059  * @param __comp A comparison functor.
3060  * @return False if wrapped to last permutation, true otherwise.
3061  *
3062  * Treats all permutations of the range [__first,__last) as a set of
3063  * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3064  * sequence into the previous one of this set. Returns true if there are
3065  * more sequences to generate. If the sequence is the smallest of the set,
3066  * the largest is generated and false returned.
3067  */
3068  template<typename _BidirectionalIterator, typename _Compare>
3069  inline bool
3070  prev_permutation(_BidirectionalIterator __first,
3071  _BidirectionalIterator __last, _Compare __comp)
3072  {
3073  // concept requirements
3074  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3075  _BidirectionalIterator>)
3076  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3077  typename iterator_traits<_BidirectionalIterator>::value_type,
3078  typename iterator_traits<_BidirectionalIterator>::value_type>)
3079  __glibcxx_requires_valid_range(__first, __last);
3080  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3081 
3082  return std::__prev_permutation(__first, __last,
3083  __gnu_cxx::__ops::__iter_comp_iter(__comp));
3084  }
3085 
3086  // replace
3087  // replace_if
3088 
3089  template<typename _InputIterator, typename _OutputIterator,
3090  typename _Predicate, typename _Tp>
3091  _OutputIterator
3092  __replace_copy_if(_InputIterator __first, _InputIterator __last,
3093  _OutputIterator __result,
3094  _Predicate __pred, const _Tp& __new_value)
3095  {
3096  for (; __first != __last; ++__first, (void)++__result)
3097  if (__pred(__first))
3098  *__result = __new_value;
3099  else
3100  *__result = *__first;
3101  return __result;
3102  }
3103 
3104  /**
3105  * @brief Copy a sequence, replacing each element of one value with another
3106  * value.
3107  * @param __first An input iterator.
3108  * @param __last An input iterator.
3109  * @param __result An output iterator.
3110  * @param __old_value The value to be replaced.
3111  * @param __new_value The replacement value.
3112  * @return The end of the output sequence, @p result+(last-first).
3113  *
3114  * Copies each element in the input range @p [__first,__last) to the
3115  * output range @p [__result,__result+(__last-__first)) replacing elements
3116  * equal to @p __old_value with @p __new_value.
3117  */
3118  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3119  inline _OutputIterator
3120  replace_copy(_InputIterator __first, _InputIterator __last,
3121  _OutputIterator __result,
3122  const _Tp& __old_value, const _Tp& __new_value)
3123  {
3124  // concept requirements
3125  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3126  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3127  typename iterator_traits<_InputIterator>::value_type>)
3128  __glibcxx_function_requires(_EqualOpConcept<
3129  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3130  __glibcxx_requires_valid_range(__first, __last);
3131 
3132  return std::__replace_copy_if(__first, __last, __result,
3133  __gnu_cxx::__ops::__iter_equals_val(__old_value),
3134  __new_value);
3135  }
3136 
3137  /**
3138  * @brief Copy a sequence, replacing each value for which a predicate
3139  * returns true with another value.
3140  * @ingroup mutating_algorithms
3141  * @param __first An input iterator.
3142  * @param __last An input iterator.
3143  * @param __result An output iterator.
3144  * @param __pred A predicate.
3145  * @param __new_value The replacement value.
3146  * @return The end of the output sequence, @p __result+(__last-__first).
3147  *
3148  * Copies each element in the range @p [__first,__last) to the range
3149  * @p [__result,__result+(__last-__first)) replacing elements for which
3150  * @p __pred returns true with @p __new_value.
3151  */
3152  template<typename _InputIterator, typename _OutputIterator,
3153  typename _Predicate, typename _Tp>
3154  inline _OutputIterator
3155  replace_copy_if(_InputIterator __first, _InputIterator __last,
3156  _OutputIterator __result,
3157  _Predicate __pred, const _Tp& __new_value)
3158  {
3159  // concept requirements
3160  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3161  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3162  typename iterator_traits<_InputIterator>::value_type>)
3163  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3164  typename iterator_traits<_InputIterator>::value_type>)
3165  __glibcxx_requires_valid_range(__first, __last);
3166 
3167  return std::__replace_copy_if(__first, __last, __result,
3168  __gnu_cxx::__ops::__pred_iter(__pred),
3169  __new_value);
3170  }
3171 
3172  template<typename _InputIterator, typename _Predicate>
3173  typename iterator_traits<_InputIterator>::difference_type
3174  __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3175  {
3176  typename iterator_traits<_InputIterator>::difference_type __n = 0;
3177  for (; __first != __last; ++__first)
3178  if (__pred(__first))
3179  ++__n;
3180  return __n;
3181  }
3182 
3183 #if __cplusplus >= 201103L
3184  /**
3185  * @brief Determines whether the elements of a sequence are sorted.
3186  * @ingroup sorting_algorithms
3187  * @param __first An iterator.
3188  * @param __last Another iterator.
3189  * @return True if the elements are sorted, false otherwise.
3190  */
3191  template<typename _ForwardIterator>
3192  inline bool
3193  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3194  { return std::is_sorted_until(__first, __last) == __last; }
3195 
3196  /**
3197  * @brief Determines whether the elements of a sequence are sorted
3198  * according to a comparison functor.
3199  * @ingroup sorting_algorithms
3200  * @param __first An iterator.
3201  * @param __last Another iterator.
3202  * @param __comp A comparison functor.
3203  * @return True if the elements are sorted, false otherwise.
3204  */
3205  template<typename _ForwardIterator, typename _Compare>
3206  inline bool
3207  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3208  _Compare __comp)
3209  { return std::is_sorted_until(__first, __last, __comp) == __last; }
3210 
3211  template<typename _ForwardIterator, typename _Compare>
3212  _ForwardIterator
3213  __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3214  _Compare __comp)
3215  {
3216  if (__first == __last)
3217  return __last;
3218 
3219  _ForwardIterator __next = __first;
3220  for (++__next; __next != __last; __first = __next, (void)++__next)
3221  if (__comp(__next, __first))
3222  return __next;
3223  return __next;
3224  }
3225 
3226  /**
3227  * @brief Determines the end of a sorted sequence.
3228  * @ingroup sorting_algorithms
3229  * @param __first An iterator.
3230  * @param __last Another iterator.
3231  * @return An iterator pointing to the last iterator i in [__first, __last)
3232  * for which the range [__first, i) is sorted.
3233  */
3234  template<typename _ForwardIterator>
3235  inline _ForwardIterator
3236  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3237  {
3238  // concept requirements
3239  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3240  __glibcxx_function_requires(_LessThanComparableConcept<
3241  typename iterator_traits<_ForwardIterator>::value_type>)
3242  __glibcxx_requires_valid_range(__first, __last);
3243  __glibcxx_requires_irreflexive(__first, __last);
3244 
3245  return std::__is_sorted_until(__first, __last,
3246  __gnu_cxx::__ops::__iter_less_iter());
3247  }
3248 
3249  /**
3250  * @brief Determines the end of a sorted sequence using comparison functor.
3251  * @ingroup sorting_algorithms
3252  * @param __first An iterator.
3253  * @param __last Another iterator.
3254  * @param __comp A comparison functor.
3255  * @return An iterator pointing to the last iterator i in [__first, __last)
3256  * for which the range [__first, i) is sorted.
3257  */
3258  template<typename _ForwardIterator, typename _Compare>
3259  inline _ForwardIterator
3260  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3261  _Compare __comp)
3262  {
3263  // concept requirements
3264  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3265  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3266  typename iterator_traits<_ForwardIterator>::value_type,
3267  typename iterator_traits<_ForwardIterator>::value_type>)
3268  __glibcxx_requires_valid_range(__first, __last);
3269  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3270 
3271  return std::__is_sorted_until(__first, __last,
3272  __gnu_cxx::__ops::__iter_comp_iter(__comp));
3273  }
3274 
3275  /**
3276  * @brief Determines min and max at once as an ordered pair.
3277  * @ingroup sorting_algorithms
3278  * @param __a A thing of arbitrary type.
3279  * @param __b Another thing of arbitrary type.
3280  * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3281  * __b) otherwise.
3282  */
3283  template<typename _Tp>
3284  _GLIBCXX14_CONSTEXPR
3285  inline pair<const _Tp&, const _Tp&>
3286  minmax(const _Tp& __a, const _Tp& __b)
3287  {
3288  // concept requirements
3289  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3290 
3291  return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3292  : pair<const _Tp&, const _Tp&>(__a, __b);
3293  }
3294 
3295  /**
3296  * @brief Determines min and max at once as an ordered pair.
3297  * @ingroup sorting_algorithms
3298  * @param __a A thing of arbitrary type.
3299  * @param __b Another thing of arbitrary type.
3300  * @param __comp A @link comparison_functors comparison functor @endlink.
3301  * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3302  * __b) otherwise.
3303  */
3304  template<typename _Tp, typename _Compare>
3305  _GLIBCXX14_CONSTEXPR
3306  inline pair<const _Tp&, const _Tp&>
3307  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3308  {
3309  return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3310  : pair<const _Tp&, const _Tp&>(__a, __b);
3311  }
3312 
3313  template<typename _ForwardIterator, typename _Compare>
3314  _GLIBCXX14_CONSTEXPR
3315  pair<_ForwardIterator, _ForwardIterator>
3316  __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3317  _Compare __comp)
3318  {
3319  _ForwardIterator __next = __first;
3320  if (__first == __last
3321  || ++__next == __last)
3322  return std::make_pair(__first, __first);
3323 
3324  _ForwardIterator __min{}, __max{};
3325  if (__comp(__next, __first))
3326  {
3327  __min = __next;
3328  __max = __first;
3329  }
3330  else
3331  {
3332  __min = __first;
3333  __max = __next;
3334  }
3335 
3336  __first = __next;
3337  ++__first;
3338 
3339  while (__first != __last)
3340  {
3341  __next = __first;
3342  if (++__next == __last)
3343  {
3344  if (__comp(__first, __min))
3345  __min = __first;
3346  else if (!__comp(__first, __max))
3347  __max = __first;
3348  break;
3349  }
3350 
3351  if (__comp(__next, __first))
3352  {
3353  if (__comp(__next, __min))
3354  __min = __next;
3355  if (!__comp(__first, __max))
3356  __max = __first;
3357  }
3358  else
3359  {
3360  if (__comp(__first, __min))
3361  __min = __first;
3362  if (!__comp(__next, __max))
3363  __max = __next;
3364  }
3365 
3366  __first = __next;
3367  ++__first;
3368  }
3369 
3370  return std::make_pair(__min, __max);
3371  }
3372 
3373  /**
3374  * @brief Return a pair of iterators pointing to the minimum and maximum
3375  * elements in a range.
3376  * @ingroup sorting_algorithms
3377  * @param __first Start of range.
3378  * @param __last End of range.
3379  * @return make_pair(m, M), where m is the first iterator i in
3380  * [__first, __last) such that no other element in the range is
3381  * smaller, and where M is the last iterator i in [__first, __last)
3382  * such that no other element in the range is larger.
3383  */
3384  template<typename _ForwardIterator>
3385  _GLIBCXX14_CONSTEXPR
3386  inline pair<_ForwardIterator, _ForwardIterator>
3387  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3388  {
3389  // concept requirements
3390  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3391  __glibcxx_function_requires(_LessThanComparableConcept<
3392  typename iterator_traits<_ForwardIterator>::value_type>)
3393  __glibcxx_requires_valid_range(__first, __last);
3394  __glibcxx_requires_irreflexive(__first, __last);
3395 
3396  return std::__minmax_element(__first, __last,
3397  __gnu_cxx::__ops::__iter_less_iter());
3398  }
3399 
3400  /**
3401  * @brief Return a pair of iterators pointing to the minimum and maximum
3402  * elements in a range.
3403  * @ingroup sorting_algorithms
3404  * @param __first Start of range.
3405  * @param __last End of range.
3406  * @param __comp Comparison functor.
3407  * @return make_pair(m, M), where m is the first iterator i in
3408  * [__first, __last) such that no other element in the range is
3409  * smaller, and where M is the last iterator i in [__first, __last)
3410  * such that no other element in the range is larger.
3411  */
3412  template<typename _ForwardIterator, typename _Compare>
3413  _GLIBCXX14_CONSTEXPR
3414  inline pair<_ForwardIterator, _ForwardIterator>
3415  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3416  _Compare __comp)
3417  {
3418  // concept requirements
3419  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3420  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3421  typename iterator_traits<_ForwardIterator>::value_type,
3422  typename iterator_traits<_ForwardIterator>::value_type>)
3423  __glibcxx_requires_valid_range(__first, __last);
3424  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3425 
3426  return std::__minmax_element(__first, __last,
3427  __gnu_cxx::__ops::__iter_comp_iter(__comp));
3428  }
3429 
3430  // N2722 + DR 915.
3431  template<typename _Tp>
3432  _GLIBCXX14_CONSTEXPR
3433  inline _Tp
3434  min(initializer_list<_Tp> __l)
3435  { return *std::min_element(__l.begin(), __l.end()); }
3436 
3437  template<typename _Tp, typename _Compare>
3438  _GLIBCXX14_CONSTEXPR
3439  inline _Tp
3440  min(initializer_list<_Tp> __l, _Compare __comp)
3441  { return *std::min_element(__l.begin(), __l.end(), __comp); }
3442 
3443  template<typename _Tp>
3444  _GLIBCXX14_CONSTEXPR
3445  inline _Tp
3446  max(initializer_list<_Tp> __l)
3447  { return *std::max_element(__l.begin(), __l.end()); }
3448 
3449  template<typename _Tp, typename _Compare>
3450  _GLIBCXX14_CONSTEXPR
3451  inline _Tp
3452  max(initializer_list<_Tp> __l, _Compare __comp)
3453  { return *std::max_element(__l.begin(), __l.end(), __comp); }
3454 
3455  template<typename _Tp>
3456  _GLIBCXX14_CONSTEXPR
3457  inline pair<_Tp, _Tp>
3458  minmax(initializer_list<_Tp> __l)
3459  {
3460  pair<const _Tp*, const _Tp*> __p =
3461  std::minmax_element(__l.begin(), __l.end());
3462  return std::make_pair(*__p.first, *__p.second);
3463  }
3464 
3465  template<typename _Tp, typename _Compare>
3466  _GLIBCXX14_CONSTEXPR
3467  inline pair<_Tp, _Tp>
3468  minmax(initializer_list<_Tp> __l, _Compare __comp)
3469  {
3470  pair<const _Tp*, const _Tp*> __p =
3471  std::minmax_element(__l.begin(), __l.end(), __comp);
3472  return std::make_pair(*__p.first, *__p.second);
3473  }
3474 
3475  template<typename _ForwardIterator1, typename _ForwardIterator2,
3476  typename _BinaryPredicate>
3477  bool
3478  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3479  _ForwardIterator2 __first2, _BinaryPredicate __pred)
3480  {
3481  // Efficiently compare identical prefixes: O(N) if sequences
3482  // have the same elements in the same order.
3483  for (; __first1 != __last1; ++__first1, (void)++__first2)
3484  if (!__pred(__first1, __first2))
3485  break;
3486 
3487  if (__first1 == __last1)
3488  return true;
3489 
3490  // Establish __last2 assuming equal ranges by iterating over the
3491  // rest of the list.
3492  _ForwardIterator2 __last2 = __first2;
3493  std::advance(__last2, std::distance(__first1, __last1));
3494  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3495  {
3496  if (__scan != std::__find_if(__first1, __scan,
3497  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3498  continue; // We've seen this one before.
3499 
3500  auto __matches
3501  = std::__count_if(__first2, __last2,
3502  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3503  if (0 == __matches ||
3504  std::__count_if(__scan, __last1,
3505  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3506  != __matches)
3507  return false;
3508  }
3509  return true;
3510  }
3511 
3512  /**
3513  * @brief Checks whether a permutation of the second sequence is equal
3514  * to the first sequence.
3515  * @ingroup non_mutating_algorithms
3516  * @param __first1 Start of first range.
3517  * @param __last1 End of first range.
3518  * @param __first2 Start of second range.
3519  * @return true if there exists a permutation of the elements in the range
3520  * [__first2, __first2 + (__last1 - __first1)), beginning with
3521  * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
3522  * returns true; otherwise, returns false.
3523  */
3524  template<typename _ForwardIterator1, typename _ForwardIterator2>
3525  inline bool
3526  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3527  _ForwardIterator2 __first2)
3528  {
3529  // concept requirements
3530  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3531  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3532  __glibcxx_function_requires(_EqualOpConcept<
3533  typename iterator_traits<_ForwardIterator1>::value_type,
3534  typename iterator_traits<_ForwardIterator2>::value_type>)
3535  __glibcxx_requires_valid_range(__first1, __last1);
3536 
3537  return std::__is_permutation(__first1, __last1, __first2,
3538  __gnu_cxx::__ops::__iter_equal_to_iter());
3539  }
3540 
3541  /**
3542  * @brief Checks whether a permutation of the second sequence is equal
3543  * to the first sequence.
3544  * @ingroup non_mutating_algorithms
3545  * @param __first1 Start of first range.
3546  * @param __last1 End of first range.
3547  * @param __first2 Start of second range.
3548  * @param __pred A binary predicate.
3549  * @return true if there exists a permutation of the elements in
3550  * the range [__first2, __first2 + (__last1 - __first1)),
3551  * beginning with ForwardIterator2 begin, such that
3552  * equal(__first1, __last1, __begin, __pred) returns true;
3553  * otherwise, returns false.
3554  */
3555  template<typename _ForwardIterator1, typename _ForwardIterator2,
3556  typename _BinaryPredicate>
3557  inline bool
3558  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3559  _ForwardIterator2 __first2, _BinaryPredicate __pred)
3560  {
3561  // concept requirements
3562  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3563  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3564  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3565  typename iterator_traits<_ForwardIterator1>::value_type,
3566  typename iterator_traits<_ForwardIterator2>::value_type>)
3567  __glibcxx_requires_valid_range(__first1, __last1);
3568 
3569  return std::__is_permutation(__first1, __last1, __first2,
3570  __gnu_cxx::__ops::__iter_comp_iter(__pred));
3571  }
3572 
3573 #if __cplusplus > 201103L
3574  template<typename _ForwardIterator1, typename _ForwardIterator2,
3575  typename _BinaryPredicate>
3576  bool
3577  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3578  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3579  _BinaryPredicate __pred)
3580  {
3581  using _Cat1
3582  = typename iterator_traits<_ForwardIterator1>::iterator_category;
3583  using _Cat2
3584  = typename iterator_traits<_ForwardIterator2>::iterator_category;
3585  using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3586  using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3587  constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3588  if (__ra_iters)
3589  {
3590  auto __d1 = std::distance(__first1, __last1);
3591  auto __d2 = std::distance(__first2, __last2);
3592  if (__d1 != __d2)
3593  return false;
3594  }
3595 
3596  // Efficiently compare identical prefixes: O(N) if sequences
3597  // have the same elements in the same order.
3598  for (; __first1 != __last1 && __first2 != __last2;
3599  ++__first1, (void)++__first2)
3600  if (!__pred(__first1, __first2))
3601  break;
3602 
3603  if (__ra_iters)
3604  {
3605  if (__first1 == __last1)
3606  return true;
3607  }
3608  else
3609  {
3610  auto __d1 = std::distance(__first1, __last1);
3611  auto __d2 = std::distance(__first2, __last2);
3612  if (__d1 == 0 && __d2 == 0)
3613  return true;
3614  if (__d1 != __d2)
3615  return false;
3616  }
3617 
3618  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3619  {
3620  if (__scan != std::__find_if(__first1, __scan,
3621  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3622  continue; // We've seen this one before.
3623 
3624  auto __matches = std::__count_if(__first2, __last2,
3625  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3626  if (0 == __matches
3627  || std::__count_if(__scan, __last1,
3628  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3629  != __matches)
3630  return false;
3631  }
3632  return true;
3633  }
3634 
3635  /**
3636  * @brief Checks whether a permutaion of the second sequence is equal
3637  * to the first sequence.
3638  * @ingroup non_mutating_algorithms
3639  * @param __first1 Start of first range.
3640  * @param __last1 End of first range.
3641  * @param __first2 Start of second range.
3642  * @param __last2 End of first range.
3643  * @return true if there exists a permutation of the elements in the range
3644  * [__first2, __last2), beginning with ForwardIterator2 begin,
3645  * such that equal(__first1, __last1, begin) returns true;
3646  * otherwise, returns false.
3647  */
3648  template<typename _ForwardIterator1, typename _ForwardIterator2>
3649  inline bool
3650  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3651  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3652  {
3653  __glibcxx_requires_valid_range(__first1, __last1);
3654  __glibcxx_requires_valid_range(__first2, __last2);
3655 
3656  return
3657  std::__is_permutation(__first1, __last1, __first2, __last2,
3658  __gnu_cxx::__ops::__iter_equal_to_iter());
3659  }
3660 
3661  /**
3662  * @brief Checks whether a permutation of the second sequence is equal
3663  * to the first sequence.
3664  * @ingroup non_mutating_algorithms
3665  * @param __first1 Start of first range.
3666  * @param __last1 End of first range.
3667  * @param __first2 Start of second range.
3668  * @param __last2 End of first range.
3669  * @param __pred A binary predicate.
3670  * @return true if there exists a permutation of the elements in the range
3671  * [__first2, __last2), beginning with ForwardIterator2 begin,
3672  * such that equal(__first1, __last1, __begin, __pred) returns true;
3673  * otherwise, returns false.
3674  */
3675  template<typename _ForwardIterator1, typename _ForwardIterator2,
3676  typename _BinaryPredicate>
3677  inline bool
3678  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3679  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3680  _BinaryPredicate __pred)
3681  {
3682  __glibcxx_requires_valid_range(__first1, __last1);
3683  __glibcxx_requires_valid_range(__first2, __last2);
3684 
3685  return std::__is_permutation(__first1, __last1, __first2, __last2,
3686  __gnu_cxx::__ops::__iter_comp_iter(__pred));
3687  }
3688 
3689 #if __cplusplus > 201402L
3690 
3691 #define __cpp_lib_clamp 201603
3692 
3693  /**
3694  * @brief Returns the value clamped between lo and hi.
3695  * @ingroup sorting_algorithms
3696  * @param __val A value of arbitrary type.
3697  * @param __lo A lower limit of arbitrary type.
3698  * @param __hi An upper limit of arbitrary type.
3699  * @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.
3700  */
3701  template<typename _Tp>
3702  constexpr const _Tp&
3703  clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3704  {
3705  __glibcxx_assert(!(__hi < __lo));
3706  return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3707  }
3708 
3709  /**
3710  * @brief Returns the value clamped between lo and hi.
3711  * @ingroup sorting_algorithms
3712  * @param __val A value of arbitrary type.
3713  * @param __lo A lower limit of arbitrary type.
3714  * @param __hi An upper limit of arbitrary type.
3715  * @param __comp A comparison functor.
3716  * @return max(__val, __lo, __comp) if __comp(__val, __hi)
3717  * or min(__val, __hi, __comp) otherwise.
3718  */
3719  template<typename _Tp, typename _Compare>
3720  constexpr const _Tp&
3721  clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3722  {
3723  __glibcxx_assert(!__comp(__hi, __lo));
3724  return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3725  }
3726 #endif // C++17
3727 #endif // C++14
3728 
3729 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3730  /**
3731  * @brief Generate two uniformly distributed integers using a
3732  * single distribution invocation.
3733  * @param __b0 The upper bound for the first integer.
3734  * @param __b1 The upper bound for the second integer.
3735  * @param __g A UniformRandomBitGenerator.
3736  * @return A pair (i, j) with i and j uniformly distributed
3737  * over [0, __b0) and [0, __b1), respectively.
3738  *
3739  * Requires: __b0 * __b1 <= __g.max() - __g.min().
3740  *
3741  * Using uniform_int_distribution with a range that is very
3742  * small relative to the range of the generator ends up wasting
3743  * potentially expensively generated randomness, since
3744  * uniform_int_distribution does not store leftover randomness
3745  * between invocations.
3746  *
3747  * If we know we want two integers in ranges that are sufficiently
3748  * small, we can compose the ranges, use a single distribution
3749  * invocation, and significantly reduce the waste.
3750  */
3751  template<typename _IntType, typename _UniformRandomBitGenerator>
3752  pair<_IntType, _IntType>
3753  __gen_two_uniform_ints(_IntType __b0, _IntType __b1,
3754  _UniformRandomBitGenerator&& __g)
3755  {
3756  _IntType __x
3757  = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g);
3758  return std::make_pair(__x / __b1, __x % __b1);
3759  }
3760 
3761  /**
3762  * @brief Shuffle the elements of a sequence using a uniform random
3763  * number generator.
3764  * @ingroup mutating_algorithms
3765  * @param __first A forward iterator.
3766  * @param __last A forward iterator.
3767  * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3768  * @return Nothing.
3769  *
3770  * Reorders the elements in the range @p [__first,__last) using @p __g to
3771  * provide random numbers.
3772  */
3773  template<typename _RandomAccessIterator,
3774  typename _UniformRandomNumberGenerator>
3775  void
3776  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3777  _UniformRandomNumberGenerator&& __g)
3778  {
3779  // concept requirements
3780  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3781  _RandomAccessIterator>)
3782  __glibcxx_requires_valid_range(__first, __last);
3783 
3784  if (__first == __last)
3785  return;
3786 
3787  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3788  _DistanceType;
3789 
3790  typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3791  typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3792  typedef typename __distr_type::param_type __p_type;
3793 
3794  typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3795  _Gen;
3797  __uc_type;
3798 
3799  const __uc_type __urngrange = __g.max() - __g.min();
3800  const __uc_type __urange = __uc_type(__last - __first);
3801 
3802  if (__urngrange / __urange >= __urange)
3803  // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
3804  {
3805  _RandomAccessIterator __i = __first + 1;
3806 
3807  // Since we know the range isn't empty, an even number of elements
3808  // means an uneven number of elements /to swap/, in which case we
3809  // do the first one up front:
3810 
3811  if ((__urange % 2) == 0)
3812  {
3813  __distr_type __d{0, 1};
3814  std::iter_swap(__i++, __first + __d(__g));
3815  }
3816 
3817  // Now we know that __last - __i is even, so we do the rest in pairs,
3818  // using a single distribution invocation to produce swap positions
3819  // for two successive elements at a time:
3820 
3821  while (__i != __last)
3822  {
3823  const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3824 
3825  const pair<__uc_type, __uc_type> __pospos =
3826  __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
3827 
3828  std::iter_swap(__i++, __first + __pospos.first);
3829  std::iter_swap(__i++, __first + __pospos.second);
3830  }
3831 
3832  return;
3833  }
3834 
3835  __distr_type __d;
3836 
3837  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3838  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3839  }
3840 #endif
3841 
3842 #endif // C++11
3843 
3844 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3845 
3846  /**
3847  * @brief Apply a function to every element of a sequence.
3848  * @ingroup non_mutating_algorithms
3849  * @param __first An input iterator.
3850  * @param __last An input iterator.
3851  * @param __f A unary function object.
3852  * @return @p __f
3853  *
3854  * Applies the function object @p __f to each element in the range
3855  * @p [first,last). @p __f must not modify the order of the sequence.
3856  * If @p __f has a return value it is ignored.
3857  */
3858  template<typename _InputIterator, typename _Function>
3859  _Function
3860  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3861  {
3862  // concept requirements
3863  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3864  __glibcxx_requires_valid_range(__first, __last);
3865  for (; __first != __last; ++__first)
3866  __f(*__first);
3867  return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3868  }
3869 
3870  /**
3871  * @brief Find the first occurrence of a value in a sequence.
3872  * @ingroup non_mutating_algorithms
3873  * @param __first An input iterator.
3874  * @param __last An input iterator.
3875  * @param __val The value to find.
3876  * @return The first iterator @c i in the range @p [__first,__last)
3877  * such that @c *i == @p __val, or @p __last if no such iterator exists.
3878  */
3879  template<typename _InputIterator, typename _Tp>
3880  inline _InputIterator
3881  find(_InputIterator __first, _InputIterator __last,
3882  const _Tp& __val)
3883  {
3884  // concept requirements
3885  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3886  __glibcxx_function_requires(_EqualOpConcept<
3887  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3888  __glibcxx_requires_valid_range(__first, __last);
3889  return std::__find_if(__first, __last,
3890  __gnu_cxx::__ops::__iter_equals_val(__val));
3891  }
3892 
3893  /**
3894  * @brief Find the first element in a sequence for which a
3895  * predicate is true.
3896  * @ingroup non_mutating_algorithms
3897  * @param __first An input iterator.
3898  * @param __last An input iterator.
3899  * @param __pred A predicate.
3900  * @return The first iterator @c i in the range @p [__first,__last)
3901  * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3902  */
3903  template<typename _InputIterator, typename _Predicate>
3904  inline _InputIterator
3905  find_if(_InputIterator __first, _InputIterator __last,
3906  _Predicate __pred)
3907  {
3908  // concept requirements
3909  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3910  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3911  typename iterator_traits<_InputIterator>::value_type>)
3912  __glibcxx_requires_valid_range(__first, __last);
3913 
3914  return std::__find_if(__first, __last,
3915  __gnu_cxx::__ops::__pred_iter(__pred));
3916  }
3917 
3918  /**
3919  * @brief Find element from a set in a sequence.
3920  * @ingroup non_mutating_algorithms
3921  * @param __first1 Start of range to search.
3922  * @param __last1 End of range to search.
3923  * @param __first2 Start of match candidates.
3924  * @param __last2 End of match candidates.
3925  * @return The first iterator @c i in the range
3926  * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3927  * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3928  *
3929  * Searches the range @p [__first1,__last1) for an element that is
3930  * equal to some element in the range [__first2,__last2). If
3931  * found, returns an iterator in the range [__first1,__last1),
3932  * otherwise returns @p __last1.
3933  */
3934  template<typename _InputIterator, typename _ForwardIterator>
3935  _InputIterator
3936  find_first_of(_InputIterator __first1, _InputIterator __last1,
3937  _ForwardIterator __first2, _ForwardIterator __last2)
3938  {
3939  // concept requirements
3940  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3941  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3942  __glibcxx_function_requires(_EqualOpConcept<
3943  typename iterator_traits<_InputIterator>::value_type,
3944  typename iterator_traits<_ForwardIterator>::value_type>)
3945  __glibcxx_requires_valid_range(__first1, __last1);
3946  __glibcxx_requires_valid_range(__first2, __last2);
3947 
3948  for (; __first1 != __last1; ++__first1)
3949  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3950  if (*__first1 == *__iter)
3951  return __first1;
3952  return __last1;
3953  }
3954 
3955  /**
3956  * @brief Find element from a set in a sequence using a predicate.
3957  * @ingroup non_mutating_algorithms
3958  * @param __first1 Start of range to search.
3959  * @param __last1 End of range to search.
3960  * @param __first2 Start of match candidates.
3961  * @param __last2 End of match candidates.
3962  * @param __comp Predicate to use.
3963  * @return The first iterator @c i in the range
3964  * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3965  * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3966  * such iterator exists.
3967  *
3968 
3969  * Searches the range @p [__first1,__last1) for an element that is
3970  * equal to some element in the range [__first2,__last2). If
3971  * found, returns an iterator in the range [__first1,__last1),
3972  * otherwise returns @p __last1.
3973  */
3974  template<typename _InputIterator, typename _ForwardIterator,
3975  typename _BinaryPredicate>
3976  _InputIterator
3977  find_first_of(_InputIterator __first1, _InputIterator __last1,
3978  _ForwardIterator __first2, _ForwardIterator __last2,
3979  _BinaryPredicate __comp)
3980  {
3981  // concept requirements
3982  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3983  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3984  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3985  typename iterator_traits<_InputIterator>::value_type,
3986  typename iterator_traits<_ForwardIterator>::value_type>)
3987  __glibcxx_requires_valid_range(__first1, __last1);
3988  __glibcxx_requires_valid_range(__first2, __last2);
3989 
3990  for (; __first1 != __last1; ++__first1)
3991  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3992  if (__comp(*__first1, *__iter))
3993  return __first1;
3994  return __last1;
3995  }
3996 
3997  /**
3998  * @brief Find two adjacent values in a sequence that are equal.
3999  * @ingroup non_mutating_algorithms
4000  * @param __first A forward iterator.
4001  * @param __last A forward iterator.
4002  * @return The first iterator @c i such that @c i and @c i+1 are both
4003  * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4004  * or @p __last if no such iterator exists.
4005  */
4006  template<typename _ForwardIterator>
4007  inline _ForwardIterator
4008  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4009  {
4010  // concept requirements
4011  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4012  __glibcxx_function_requires(_EqualityComparableConcept<
4013  typename iterator_traits<_ForwardIterator>::value_type>)
4014  __glibcxx_requires_valid_range(__first, __last);
4015 
4016  return std::__adjacent_find(__first, __last,
4017  __gnu_cxx::__ops::__iter_equal_to_iter());
4018  }
4019 
4020  /**
4021  * @brief Find two adjacent values in a sequence using a predicate.
4022  * @ingroup non_mutating_algorithms
4023  * @param __first A forward iterator.
4024  * @param __last A forward iterator.
4025  * @param __binary_pred A binary predicate.
4026  * @return The first iterator @c i such that @c i and @c i+1 are both
4027  * valid iterators in @p [__first,__last) and such that
4028  * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4029  * exists.
4030  */
4031  template<typename _ForwardIterator, typename _BinaryPredicate>
4032  inline _ForwardIterator
4033  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4034  _BinaryPredicate __binary_pred)
4035  {
4036  // concept requirements
4037  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4038  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4039  typename iterator_traits<_ForwardIterator>::value_type,
4040  typename iterator_traits<_ForwardIterator>::value_type>)
4041  __glibcxx_requires_valid_range(__first, __last);
4042 
4043  return std::__adjacent_find(__first, __last,
4044  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4045  }
4046 
4047  /**
4048  * @brief Count the number of copies of a value in a sequence.
4049  * @ingroup non_mutating_algorithms
4050  * @param __first An input iterator.
4051  * @param __last An input iterator.
4052  * @param __value The value to be counted.
4053  * @return The number of iterators @c i in the range @p [__first,__last)
4054  * for which @c *i == @p __value
4055  */
4056  template<typename _InputIterator, typename _Tp>
4057  inline typename iterator_traits<_InputIterator>::difference_type
4058  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4059  {
4060  // concept requirements
4061  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4062  __glibcxx_function_requires(_EqualOpConcept<
4063  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4064  __glibcxx_requires_valid_range(__first, __last);
4065 
4066  return std::__count_if(__first, __last,
4067  __gnu_cxx::__ops::__iter_equals_val(__value));
4068  }
4069 
4070  /**
4071  * @brief Count the elements of a sequence for which a predicate is true.
4072  * @ingroup non_mutating_algorithms
4073  * @param __first An input iterator.
4074  * @param __last An input iterator.
4075  * @param __pred A predicate.
4076  * @return The number of iterators @c i in the range @p [__first,__last)
4077  * for which @p __pred(*i) is true.
4078  */
4079  template<typename _InputIterator, typename _Predicate>
4080  inline typename iterator_traits<_InputIterator>::difference_type
4081  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4082  {
4083  // concept requirements
4084  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4085  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4086  typename iterator_traits<_InputIterator>::value_type>)
4087  __glibcxx_requires_valid_range(__first, __last);
4088 
4089  return std::__count_if(__first, __last,
4090  __gnu_cxx::__ops::__pred_iter(__pred));
4091  }
4092 
4093  /**
4094  * @brief Search a sequence for a matching sub-sequence.
4095  * @ingroup non_mutating_algorithms
4096  * @param __first1 A forward iterator.
4097  * @param __last1 A forward iterator.
4098  * @param __first2 A forward iterator.
4099  * @param __last2 A forward iterator.
4100  * @return The first iterator @c i in the range @p
4101  * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4102  * *(__first2+N) for each @c N in the range @p
4103  * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4104  *
4105  * Searches the range @p [__first1,__last1) for a sub-sequence that
4106  * compares equal value-by-value with the sequence given by @p
4107  * [__first2,__last2) and returns an iterator to the first element
4108  * of the sub-sequence, or @p __last1 if the sub-sequence is not
4109  * found.
4110  *
4111  * Because the sub-sequence must lie completely within the range @p
4112  * [__first1,__last1) it must start at a position less than @p
4113  * __last1-(__last2-__first2) where @p __last2-__first2 is the
4114  * length of the sub-sequence.
4115  *
4116  * This means that the returned iterator @c i will be in the range
4117  * @p [__first1,__last1-(__last2-__first2))
4118  */
4119  template<typename _ForwardIterator1, typename _ForwardIterator2>
4120  inline _ForwardIterator1
4121  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4122  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4123  {
4124  // concept requirements
4125  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4126  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4127  __glibcxx_function_requires(_EqualOpConcept<
4128  typename iterator_traits<_ForwardIterator1>::value_type,
4129  typename iterator_traits<_ForwardIterator2>::value_type>)
4130  __glibcxx_requires_valid_range(__first1, __last1);
4131  __glibcxx_requires_valid_range(__first2, __last2);
4132 
4133  return std::__search(__first1, __last1, __first2, __last2,
4134  __gnu_cxx::__ops::__iter_equal_to_iter());
4135  }
4136 
4137  /**
4138  * @brief Search a sequence for a matching sub-sequence using a predicate.
4139  * @ingroup non_mutating_algorithms
4140  * @param __first1 A forward iterator.
4141  * @param __last1 A forward iterator.
4142  * @param __first2 A forward iterator.
4143  * @param __last2 A forward iterator.
4144  * @param __predicate A binary predicate.
4145  * @return The first iterator @c i in the range
4146  * @p [__first1,__last1-(__last2-__first2)) such that
4147  * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4148  * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4149  *
4150  * Searches the range @p [__first1,__last1) for a sub-sequence that
4151  * compares equal value-by-value with the sequence given by @p
4152  * [__first2,__last2), using @p __predicate to determine equality,
4153  * and returns an iterator to the first element of the
4154  * sub-sequence, or @p __last1 if no such iterator exists.
4155  *
4156  * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4157  */
4158  template<typename _ForwardIterator1, typename _ForwardIterator2,
4159  typename _BinaryPredicate>
4160  inline _ForwardIterator1
4161  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4162  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4163  _BinaryPredicate __predicate)
4164  {
4165  // concept requirements
4166  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4167  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4168  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4169  typename iterator_traits<_ForwardIterator1>::value_type,
4170  typename iterator_traits<_ForwardIterator2>::value_type>)
4171  __glibcxx_requires_valid_range(__first1, __last1);
4172  __glibcxx_requires_valid_range(__first2, __last2);
4173 
4174  return std::__search(__first1, __last1, __first2, __last2,
4175  __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4176  }
4177 
4178  /**
4179  * @brief Search a sequence for a number of consecutive values.
4180  * @ingroup non_mutating_algorithms
4181  * @param __first A forward iterator.
4182  * @param __last A forward iterator.
4183  * @param __count The number of consecutive values.
4184  * @param __val The value to find.
4185  * @return The first iterator @c i in the range @p
4186  * [__first,__last-__count) such that @c *(i+N) == @p __val for
4187  * each @c N in the range @p [0,__count), or @p __last if no such
4188  * iterator exists.
4189  *
4190  * Searches the range @p [__first,__last) for @p count consecutive elements
4191  * equal to @p __val.
4192  */
4193  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4194  inline _ForwardIterator
4195  search_n(_ForwardIterator __first, _ForwardIterator __last,
4196  _Integer __count, const _Tp& __val)
4197  {
4198  // concept requirements
4199  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4200  __glibcxx_function_requires(_EqualOpConcept<
4201  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4202  __glibcxx_requires_valid_range(__first, __last);
4203 
4204  return std::__search_n(__first, __last, __count,
4205  __gnu_cxx::__ops::__iter_equals_val(__val));
4206  }
4207 
4208 
4209  /**
4210  * @brief Search a sequence for a number of consecutive values using a
4211  * predicate.
4212  * @ingroup non_mutating_algorithms
4213  * @param __first A forward iterator.
4214  * @param __last A forward iterator.
4215  * @param __count The number of consecutive values.
4216  * @param __val The value to find.
4217  * @param __binary_pred A binary predicate.
4218  * @return The first iterator @c i in the range @p
4219  * [__first,__last-__count) such that @p
4220  * __binary_pred(*(i+N),__val) is true for each @c N in the range
4221  * @p [0,__count), or @p __last if no such iterator exists.
4222  *
4223  * Searches the range @p [__first,__last) for @p __count
4224  * consecutive elements for which the predicate returns true.
4225  */
4226  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4227  typename _BinaryPredicate>
4228  inline _ForwardIterator
4229  search_n(_ForwardIterator __first, _ForwardIterator __last,
4230  _Integer __count, const _Tp& __val,
4231  _BinaryPredicate __binary_pred)
4232  {
4233  // concept requirements
4234  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4235  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4236  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4237  __glibcxx_requires_valid_range(__first, __last);
4238 
4239  return std::__search_n(__first, __last, __count,
4240  __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4241  }
4242 
4243 #if __cplusplus > 201402L
4244  /** @brief Search a sequence using a Searcher object.
4245  *
4246  * @param __first A forward iterator.
4247  * @param __last A forward iterator.
4248  * @param __searcher A callable object.
4249  * @return @p __searcher(__first,__last).first
4250  */
4251  template<typename _ForwardIterator, typename _Searcher>
4252  inline _ForwardIterator
4253  search(_ForwardIterator __first, _ForwardIterator __last,
4254  const _Searcher& __searcher)
4255  { return __searcher(__first, __last).first; }
4256 #endif
4257 
4258  /**
4259  * @brief Perform an operation on a sequence.
4260  * @ingroup mutating_algorithms
4261  * @param __first An input iterator.
4262  * @param __last An input iterator.
4263  * @param __result An output iterator.
4264  * @param __unary_op A unary operator.
4265  * @return An output iterator equal to @p __result+(__last-__first).
4266  *
4267  * Applies the operator to each element in the input range and assigns
4268  * the results to successive elements of the output sequence.
4269  * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4270  * range @p [0,__last-__first).
4271  *
4272  * @p unary_op must not alter its argument.
4273  */
4274  template<typename _InputIterator, typename _OutputIterator,
4275  typename _UnaryOperation>
4276  _OutputIterator
4277  transform(_InputIterator __first, _InputIterator __last,
4278  _OutputIterator __result, _UnaryOperation __unary_op)
4279  {
4280  // concept requirements
4281  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4282  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4283  // "the type returned by a _UnaryOperation"
4284  __typeof__(__unary_op(*__first))>)
4285  __glibcxx_requires_valid_range(__first, __last);
4286 
4287  for (; __first != __last; ++__first, (void)++__result)
4288  *__result = __unary_op(*__first);
4289  return __result;
4290  }
4291 
4292  /**
4293  * @brief Perform an operation on corresponding elements of two sequences.
4294  * @ingroup mutating_algorithms
4295  * @param __first1 An input iterator.
4296  * @param __last1 An input iterator.
4297  * @param __first2 An input iterator.
4298  * @param __result An output iterator.
4299  * @param __binary_op A binary operator.
4300  * @return An output iterator equal to @p result+(last-first).
4301  *
4302  * Applies the operator to the corresponding elements in the two
4303  * input ranges and assigns the results to successive elements of the
4304  * output sequence.
4305  * Evaluates @p
4306  * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4307  * @c N in the range @p [0,__last1-__first1).
4308  *
4309  * @p binary_op must not alter either of its arguments.
4310  */
4311  template<typename _InputIterator1, typename _InputIterator2,
4312  typename _OutputIterator, typename _BinaryOperation>
4313  _OutputIterator
4314  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4315  _InputIterator2 __first2, _OutputIterator __result,
4316  _BinaryOperation __binary_op)
4317  {
4318  // concept requirements
4319  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4320  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4321  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4322  // "the type returned by a _BinaryOperation"
4323  __typeof__(__binary_op(*__first1,*__first2))>)
4324  __glibcxx_requires_valid_range(__first1, __last1);
4325 
4326  for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4327  *__result = __binary_op(*__first1, *__first2);
4328  return __result;
4329  }
4330 
4331  /**
4332  * @brief Replace each occurrence of one value in a sequence with another
4333  * value.
4334  * @ingroup mutating_algorithms
4335  * @param __first A forward iterator.
4336  * @param __last A forward iterator.
4337  * @param __old_value The value to be replaced.
4338  * @param __new_value The replacement value.
4339  * @return replace() returns no value.
4340  *
4341  * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4342  * @p __old_value then the assignment @c *i = @p __new_value is performed.
4343  */
4344  template<typename _ForwardIterator, typename _Tp>
4345  void
4346  replace(_ForwardIterator __first, _ForwardIterator __last,
4347  const _Tp& __old_value, const _Tp& __new_value)
4348  {
4349  // concept requirements
4350  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4351  _ForwardIterator>)
4352  __glibcxx_function_requires(_EqualOpConcept<
4353  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4354  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4355  typename iterator_traits<_ForwardIterator>::value_type>)
4356  __glibcxx_requires_valid_range(__first, __last);
4357 
4358  for (; __first != __last; ++__first)
4359  if (*__first == __old_value)
4360  *__first = __new_value;
4361  }
4362 
4363  /**
4364  * @brief Replace each value in a sequence for which a predicate returns
4365  * true with another value.
4366  * @ingroup mutating_algorithms
4367  * @param __first A forward iterator.
4368  * @param __last A forward iterator.
4369  * @param __pred A predicate.
4370  * @param __new_value The replacement value.
4371  * @return replace_if() returns no value.
4372  *
4373  * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4374  * is true then the assignment @c *i = @p __new_value is performed.
4375  */
4376  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4377  void
4378  replace_if(_ForwardIterator __first, _ForwardIterator __last,
4379  _Predicate __pred, const _Tp& __new_value)
4380  {
4381  // concept requirements
4382  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4383  _ForwardIterator>)
4384  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4385  typename iterator_traits<_ForwardIterator>::value_type>)
4386  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4387  typename iterator_traits<_ForwardIterator>::value_type>)
4388  __glibcxx_requires_valid_range(__first, __last);
4389 
4390  for (; __first != __last; ++__first)
4391  if (__pred(*__first))
4392  *__first = __new_value;
4393  }
4394 
4395  /**
4396  * @brief Assign the result of a function object to each value in a
4397  * sequence.
4398  * @ingroup mutating_algorithms
4399  * @param __first A forward iterator.
4400  * @param __last A forward iterator.
4401  * @param __gen A function object taking no arguments and returning
4402  * std::iterator_traits<_ForwardIterator>::value_type
4403  * @return generate() returns no value.
4404  *
4405  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4406  * @p [__first,__last).
4407  */
4408  template<typename _ForwardIterator, typename _Generator>
4409  void
4410  generate(_ForwardIterator __first, _ForwardIterator __last,
4411  _Generator __gen)
4412  {
4413  // concept requirements
4414  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4415  __glibcxx_function_requires(_GeneratorConcept<_Generator,
4416  typename iterator_traits<_ForwardIterator>::value_type>)
4417  __glibcxx_requires_valid_range(__first, __last);
4418 
4419  for (; __first != __last; ++__first)
4420  *__first = __gen();
4421  }
4422 
4423  /**
4424  * @brief Assign the result of a function object to each value in a
4425  * sequence.
4426  * @ingroup mutating_algorithms
4427  * @param __first A forward iterator.
4428  * @param __n The length of the sequence.
4429  * @param __gen A function object taking no arguments and returning
4430  * std::iterator_traits<_ForwardIterator>::value_type
4431  * @return The end of the sequence, @p __first+__n
4432  *
4433  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4434  * @p [__first,__first+__n).
4435  *
4436  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4437  * DR 865. More algorithms that throw away information
4438  */
4439  template<typename _OutputIterator, typename _Size, typename _Generator>
4440  _OutputIterator
4441  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4442  {
4443  // concept requirements
4444  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4445  // "the type returned by a _Generator"
4446  __typeof__(__gen())>)
4447 
4448  for (__decltype(__n + 0) __niter = __n;
4449  __niter > 0; --__niter, (void) ++__first)
4450  *__first = __gen();
4451  return __first;
4452  }
4453 
4454  /**
4455  * @brief Copy a sequence, removing consecutive duplicate values.
4456  * @ingroup mutating_algorithms
4457  * @param __first An input iterator.
4458  * @param __last An input iterator.
4459  * @param __result An output iterator.
4460  * @return An iterator designating the end of the resulting sequence.
4461  *
4462  * Copies each element in the range @p [__first,__last) to the range
4463  * beginning at @p __result, except that only the first element is copied
4464  * from groups of consecutive elements that compare equal.
4465  * unique_copy() is stable, so the relative order of elements that are
4466  * copied is unchanged.
4467  *
4468  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4469  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4470  *
4471  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4472  * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4473  * Assignable?
4474  */
4475  template<typename _InputIterator, typename _OutputIterator>
4476  inline _OutputIterator
4477  unique_copy(_InputIterator __first, _InputIterator __last,
4478  _OutputIterator __result)
4479  {
4480  // concept requirements
4481  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4482  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4483  typename iterator_traits<_InputIterator>::value_type>)
4484  __glibcxx_function_requires(_EqualityComparableConcept<
4485  typename iterator_traits<_InputIterator>::value_type>)
4486  __glibcxx_requires_valid_range(__first, __last);
4487 
4488  if (__first == __last)
4489  return __result;
4490  return std::__unique_copy(__first, __last, __result,
4491  __gnu_cxx::__ops::__iter_equal_to_iter(),
4492  std::__iterator_category(__first),
4493  std::__iterator_category(__result));
4494  }
4495 
4496  /**
4497  * @brief Copy a sequence, removing consecutive values using a predicate.
4498  * @ingroup mutating_algorithms
4499  * @param __first An input iterator.
4500  * @param __last An input iterator.
4501  * @param __result An output iterator.
4502  * @param __binary_pred A binary predicate.
4503  * @return An iterator designating the end of the resulting sequence.
4504  *
4505  * Copies each element in the range @p [__first,__last) to the range
4506  * beginning at @p __result, except that only the first element is copied
4507  * from groups of consecutive elements for which @p __binary_pred returns
4508  * true.
4509  * unique_copy() is stable, so the relative order of elements that are
4510  * copied is unchanged.
4511  *
4512  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4513  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4514  */
4515  template<typename _InputIterator, typename _OutputIterator,
4516  typename _BinaryPredicate>
4517  inline _OutputIterator
4518  unique_copy(_InputIterator __first, _InputIterator __last,
4519  _OutputIterator __result,
4520  _BinaryPredicate __binary_pred)
4521  {
4522  // concept requirements -- predicates checked later
4523  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4524  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4525  typename iterator_traits<_InputIterator>::value_type>)
4526  __glibcxx_requires_valid_range(__first, __last);
4527 
4528  if (__first == __last)
4529  return __result;
4530  return std::__unique_copy(__first, __last, __result,
4531  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4532  std::__iterator_category(__first),
4533  std::__iterator_category(__result));
4534  }
4535 
4536 #if _GLIBCXX_HOSTED
4537  /**
4538  * @brief Randomly shuffle the elements of a sequence.
4539  * @ingroup mutating_algorithms
4540  * @param __first A forward iterator.
4541  * @param __last A forward iterator.
4542  * @return Nothing.
4543  *
4544  * Reorder the elements in the range @p [__first,__last) using a random
4545  * distribution, so that every possible ordering of the sequence is
4546  * equally likely.
4547  */
4548  template<typename _RandomAccessIterator>
4549  inline void
4550  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4551  {
4552  // concept requirements
4553  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4554  _RandomAccessIterator>)
4555  __glibcxx_requires_valid_range(__first, __last);
4556 
4557  if (__first != __last)
4558  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4559  {
4560  // XXX rand() % N is not uniformly distributed
4561  _RandomAccessIterator __j = __first
4562  + std::rand() % ((__i - __first) + 1);
4563  if (__i != __j)
4564  std::iter_swap(__i, __j);
4565  }
4566  }
4567 #endif
4568 
4569  /**
4570  * @brief Shuffle the elements of a sequence using a random number
4571  * generator.
4572  * @ingroup mutating_algorithms
4573  * @param __first A forward iterator.
4574  * @param __last A forward iterator.
4575  * @param __rand The RNG functor or function.
4576  * @return Nothing.
4577  *
4578  * Reorders the elements in the range @p [__first,__last) using @p __rand to
4579  * provide a random distribution. Calling @p __rand(N) for a positive
4580  * integer @p N should return a randomly chosen integer from the
4581  * range [0,N).
4582  */
4583  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4584  void
4585  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4586 #if __cplusplus >= 201103L
4587  _RandomNumberGenerator&& __rand)
4588 #else
4589  _RandomNumberGenerator& __rand)
4590 #endif
4591  {
4592  // concept requirements
4593  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4594  _RandomAccessIterator>)
4595  __glibcxx_requires_valid_range(__first, __last);
4596 
4597  if (__first == __last)
4598  return;
4599  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4600  {
4601  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4602  if (__i != __j)
4603  std::iter_swap(__i, __j);
4604  }
4605  }
4606 
4607 
4608  /**
4609  * @brief Move elements for which a predicate is true to the beginning
4610  * of a sequence.
4611  * @ingroup mutating_algorithms
4612  * @param __first A forward iterator.
4613  * @param __last A forward iterator.
4614  * @param __pred A predicate functor.
4615  * @return An iterator @p middle such that @p __pred(i) is true for each
4616  * iterator @p i in the range @p [__first,middle) and false for each @p i
4617  * in the range @p [middle,__last).
4618  *
4619  * @p __pred must not modify its operand. @p partition() does not preserve
4620  * the relative ordering of elements in each group, use
4621  * @p stable_partition() if this is needed.
4622  */
4623  template<typename _ForwardIterator, typename _Predicate>
4624  inline _ForwardIterator
4625  partition(_ForwardIterator __first, _ForwardIterator __last,
4626  _Predicate __pred)
4627  {
4628  // concept requirements
4629  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4630  _ForwardIterator>)
4631  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4632  typename iterator_traits<_ForwardIterator>::value_type>)
4633  __glibcxx_requires_valid_range(__first, __last);
4634 
4635  return std::__partition(__first, __last, __pred,
4636  std::__iterator_category(__first));
4637  }
4638 
4639 
4640  /**
4641  * @brief Sort the smallest elements of a sequence.
4642  * @ingroup sorting_algorithms
4643  * @param __first An iterator.
4644  * @param __middle Another iterator.
4645  * @param __last Another iterator.
4646  * @return Nothing.
4647  *
4648  * Sorts the smallest @p (__middle-__first) elements in the range
4649  * @p [first,last) and moves them to the range @p [__first,__middle). The
4650  * order of the remaining elements in the range @p [__middle,__last) is
4651  * undefined.
4652  * After the sort if @e i and @e j are iterators in the range
4653  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4654  * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4655  */
4656  template<typename _RandomAccessIterator>
4657  inline void
4658  partial_sort(_RandomAccessIterator __first,
4659  _RandomAccessIterator __middle,
4660  _RandomAccessIterator __last)
4661  {
4662  // concept requirements
4663  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4664  _RandomAccessIterator>)
4665  __glibcxx_function_requires(_LessThanComparableConcept<
4666  typename iterator_traits<_RandomAccessIterator>::value_type>)
4667  __glibcxx_requires_valid_range(__first, __middle);
4668  __glibcxx_requires_valid_range(__middle, __last);
4669  __glibcxx_requires_irreflexive(__first, __last);
4670 
4671  std::__partial_sort(__first, __middle, __last,
4672  __gnu_cxx::__ops::__iter_less_iter());
4673  }
4674 
4675  /**
4676  * @brief Sort the smallest elements of a sequence using a predicate
4677  * for comparison.
4678  * @ingroup sorting_algorithms
4679  * @param __first An iterator.
4680  * @param __middle Another iterator.
4681  * @param __last Another iterator.
4682  * @param __comp A comparison functor.
4683  * @return Nothing.
4684  *
4685  * Sorts the smallest @p (__middle-__first) elements in the range
4686  * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4687  * order of the remaining elements in the range @p [__middle,__last) is
4688  * undefined.
4689  * After the sort if @e i and @e j are iterators in the range
4690  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4691  * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4692  * are both false.
4693  */
4694  template<typename _RandomAccessIterator, typename _Compare>
4695  inline void
4696  partial_sort(_RandomAccessIterator __first,
4697  _RandomAccessIterator __middle,
4698  _RandomAccessIterator __last,
4699  _Compare __comp)
4700  {
4701  // concept requirements
4702  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4703  _RandomAccessIterator>)
4704  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4705  typename iterator_traits<_RandomAccessIterator>::value_type,
4706  typename iterator_traits<_RandomAccessIterator>::value_type>)
4707  __glibcxx_requires_valid_range(__first, __middle);
4708  __glibcxx_requires_valid_range(__middle, __last);
4709  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4710 
4711  std::__partial_sort(__first, __middle, __last,
4712  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4713  }
4714 
4715  /**
4716  * @brief Sort a sequence just enough to find a particular position.
4717  * @ingroup sorting_algorithms
4718  * @param __first An iterator.
4719  * @param __nth Another iterator.
4720  * @param __last Another iterator.
4721  * @return Nothing.
4722  *
4723  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4724  * is the same element that would have been in that position had the
4725  * whole sequence been sorted. The elements either side of @p *__nth are
4726  * not completely sorted, but for any iterator @e i in the range
4727  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4728  * holds that *j < *i is false.
4729  */
4730  template<typename _RandomAccessIterator>
4731  inline void
4732  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4733  _RandomAccessIterator __last)
4734  {
4735  // concept requirements
4736  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4737  _RandomAccessIterator>)
4738  __glibcxx_function_requires(_LessThanComparableConcept<
4739  typename iterator_traits<_RandomAccessIterator>::value_type>)
4740  __glibcxx_requires_valid_range(__first, __nth);
4741  __glibcxx_requires_valid_range(__nth, __last);
4742  __glibcxx_requires_irreflexive(__first, __last);
4743 
4744  if (__first == __last || __nth == __last)
4745  return;
4746 
4747  std::__introselect(__first, __nth, __last,
4748  std::__lg(__last - __first) * 2,
4749  __gnu_cxx::__ops::__iter_less_iter());
4750  }
4751 
4752  /**
4753  * @brief Sort a sequence just enough to find a particular position
4754  * using a predicate for comparison.
4755  * @ingroup sorting_algorithms
4756  * @param __first An iterator.
4757  * @param __nth Another iterator.
4758  * @param __last Another iterator.
4759  * @param __comp A comparison functor.
4760  * @return Nothing.
4761  *
4762  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4763  * is the same element that would have been in that position had the
4764  * whole sequence been sorted. The elements either side of @p *__nth are
4765  * not completely sorted, but for any iterator @e i in the range
4766  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4767  * holds that @p __comp(*j,*i) is false.
4768  */
4769  template<typename _RandomAccessIterator, typename _Compare>
4770  inline void
4771  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4772  _RandomAccessIterator __last, _Compare __comp)
4773  {
4774  // concept requirements
4775  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4776  _RandomAccessIterator>)
4777  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4778  typename iterator_traits<_RandomAccessIterator>::value_type,
4779  typename iterator_traits<_RandomAccessIterator>::value_type>)
4780  __glibcxx_requires_valid_range(__first, __nth);
4781  __glibcxx_requires_valid_range(__nth, __last);
4782  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4783 
4784  if (__first == __last || __nth == __last)
4785  return;
4786 
4787  std::__introselect(__first, __nth, __last,
4788  std::__lg(__last - __first) * 2,
4789  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4790  }
4791 
4792  /**
4793  * @brief Sort the elements of a sequence.
4794  * @ingroup sorting_algorithms
4795  * @param __first An iterator.
4796  * @param __last Another iterator.
4797  * @return Nothing.
4798  *
4799  * Sorts the elements in the range @p [__first,__last) in ascending order,
4800  * such that for each iterator @e i in the range @p [__first,__last-1),
4801  * *(i+1)<*i is false.
4802  *
4803  * The relative ordering of equivalent elements is not preserved, use
4804  * @p stable_sort() if this is needed.
4805  */
4806  template<typename _RandomAccessIterator>
4807  inline void
4808  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4809  {
4810  // concept requirements
4811  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4812  _RandomAccessIterator>)
4813  __glibcxx_function_requires(_LessThanComparableConcept<
4814  typename iterator_traits<_RandomAccessIterator>::value_type>)
4815  __glibcxx_requires_valid_range(__first, __last);
4816  __glibcxx_requires_irreflexive(__first, __last);
4817 
4818  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4819  }
4820 
4821  /**
4822  * @brief Sort the elements of a sequence using a predicate for comparison.
4823  * @ingroup sorting_algorithms
4824  * @param __first An iterator.
4825  * @param __last Another iterator.
4826  * @param __comp A comparison functor.
4827  * @return Nothing.
4828  *
4829  * Sorts the elements in the range @p [__first,__last) in ascending order,
4830  * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4831  * range @p [__first,__last-1).
4832  *
4833  * The relative ordering of equivalent elements is not preserved, use
4834  * @p stable_sort() if this is needed.
4835  */
4836  template<typename _RandomAccessIterator, typename _Compare>
4837  inline void
4838  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4839  _Compare __comp)
4840  {
4841  // concept requirements
4842  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4843  _RandomAccessIterator>)
4844  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4845  typename iterator_traits<_RandomAccessIterator>::value_type,
4846  typename iterator_traits<_RandomAccessIterator>::value_type>)
4847  __glibcxx_requires_valid_range(__first, __last);
4848  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4849 
4850  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4851  }
4852 
4853  template<typename _InputIterator1, typename _InputIterator2,
4854  typename _OutputIterator, typename _Compare>
4855  _OutputIterator
4856  __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4857  _InputIterator2 __first2, _InputIterator2 __last2,
4858  _OutputIterator __result, _Compare __comp)
4859  {
4860  while (__first1 != __last1 && __first2 != __last2)
4861  {
4862  if (__comp(__first2, __first1))
4863  {
4864  *__result = *__first2;
4865  ++__first2;
4866  }
4867  else
4868  {
4869  *__result = *__first1;
4870  ++__first1;
4871  }
4872  ++__result;
4873  }
4874  return std::copy(__first2, __last2,
4875  std::copy(__first1, __last1, __result));
4876  }
4877 
4878  /**
4879  * @brief Merges two sorted ranges.
4880  * @ingroup sorting_algorithms
4881  * @param __first1 An iterator.
4882  * @param __first2 Another iterator.
4883  * @param __last1 Another iterator.
4884  * @param __last2 Another iterator.
4885  * @param __result An iterator pointing to the end of the merged range.
4886  * @return An iterator pointing to the first element <em>not less
4887  * than</em> @e val.
4888  *
4889  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4890  * the sorted range @p [__result, __result + (__last1-__first1) +
4891  * (__last2-__first2)). Both input ranges must be sorted, and the
4892  * output range must not overlap with either of the input ranges.
4893  * The sort is @e stable, that is, for equivalent elements in the
4894  * two ranges, elements from the first range will always come
4895  * before elements from the second.
4896  */
4897  template<typename _InputIterator1, typename _InputIterator2,
4898  typename _OutputIterator>
4899  inline _OutputIterator
4900  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4901  _InputIterator2 __first2, _InputIterator2 __last2,
4902  _OutputIterator __result)
4903  {
4904  // concept requirements
4905  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4906  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4907  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4908  typename iterator_traits<_InputIterator1>::value_type>)
4909  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4910  typename iterator_traits<_InputIterator2>::value_type>)
4911  __glibcxx_function_requires(_LessThanOpConcept<
4912  typename iterator_traits<_InputIterator2>::value_type,
4913  typename iterator_traits<_InputIterator1>::value_type>)
4914  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4915  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4916  __glibcxx_requires_irreflexive2(__first1, __last1);
4917  __glibcxx_requires_irreflexive2(__first2, __last2);
4918 
4919  return _GLIBCXX_STD_A::__merge(__first1, __last1,
4920  __first2, __last2, __result,
4921  __gnu_cxx::__ops::__iter_less_iter());
4922  }
4923 
4924  /**
4925  * @brief Merges two sorted ranges.
4926  * @ingroup sorting_algorithms
4927  * @param __first1 An iterator.
4928  * @param __first2 Another iterator.
4929  * @param __last1 Another iterator.
4930  * @param __last2 Another iterator.
4931  * @param __result An iterator pointing to the end of the merged range.
4932  * @param __comp A functor to use for comparisons.
4933  * @return An iterator pointing to the first element "not less
4934  * than" @e val.
4935  *
4936  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4937  * the sorted range @p [__result, __result + (__last1-__first1) +
4938  * (__last2-__first2)). Both input ranges must be sorted, and the
4939  * output range must not overlap with either of the input ranges.
4940  * The sort is @e stable, that is, for equivalent elements in the
4941  * two ranges, elements from the first range will always come
4942  * before elements from the second.
4943  *
4944  * The comparison function should have the same effects on ordering as
4945  * the function used for the initial sort.
4946  */
4947  template<typename _InputIterator1, typename _InputIterator2,
4948  typename _OutputIterator, typename _Compare>
4949  inline _OutputIterator
4950  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4951  _InputIterator2 __first2, _InputIterator2 __last2,
4952  _OutputIterator __result, _Compare __comp)
4953  {
4954  // concept requirements
4955  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4956  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4957  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4958  typename iterator_traits<_InputIterator1>::value_type>)
4959  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960  typename iterator_traits<_InputIterator2>::value_type>)
4961  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4962  typename iterator_traits<_InputIterator2>::value_type,
4963  typename iterator_traits<_InputIterator1>::value_type>)
4964  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4965  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4966  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4967  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4968 
4969  return _GLIBCXX_STD_A::__merge(__first1, __last1,
4970  __first2, __last2, __result,
4971  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4972  }
4973 
4974  template<typename _RandomAccessIterator, typename _Compare>
4975  inline void
4976  __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4977  _Compare __comp)
4978  {
4979  typedef typename iterator_traits<_RandomAccessIterator>::value_type
4980  _ValueType;
4981  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4982  _DistanceType;
4983 
4984  typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4985  _TmpBuf __buf(__first, std::distance(__first, __last));
4986 
4987  if (__buf.begin() == 0)
4988  std::__inplace_stable_sort(__first, __last, __comp);
4989  else
4990  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4991  _DistanceType(__buf.size()), __comp);
4992  }
4993 
4994  /**
4995  * @brief Sort the elements of a sequence, preserving the relative order
4996  * of equivalent elements.
4997  * @ingroup sorting_algorithms
4998  * @param __first An iterator.
4999  * @param __last Another iterator.
5000  * @return Nothing.
5001  *
5002  * Sorts the elements in the range @p [__first,__last) in ascending order,
5003  * such that for each iterator @p i in the range @p [__first,__last-1),
5004  * @p *(i+1)<*i is false.
5005  *
5006  * The relative ordering of equivalent elements is preserved, so any two
5007  * elements @p x and @p y in the range @p [__first,__last) such that
5008  * @p x<y is false and @p y<x is false will have the same relative
5009  * ordering after calling @p stable_sort().
5010  */
5011  template<typename _RandomAccessIterator>
5012  inline void
5013  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5014  {
5015  // concept requirements
5016  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5017  _RandomAccessIterator>)
5018  __glibcxx_function_requires(_LessThanComparableConcept<
5019  typename iterator_traits<_RandomAccessIterator>::value_type>)
5020  __glibcxx_requires_valid_range(__first, __last);
5021  __glibcxx_requires_irreflexive(__first, __last);
5022 
5023  _GLIBCXX_STD_A::__stable_sort(__first, __last,
5024  __gnu_cxx::__ops::__iter_less_iter());
5025  }
5026 
5027  /**
5028  * @brief Sort the elements of a sequence using a predicate for comparison,
5029  * preserving the relative order of equivalent elements.
5030  * @ingroup sorting_algorithms
5031  * @param __first An iterator.
5032  * @param __last Another iterator.
5033  * @param __comp A comparison functor.
5034  * @return Nothing.
5035  *
5036  * Sorts the elements in the range @p [__first,__last) in ascending order,
5037  * such that for each iterator @p i in the range @p [__first,__last-1),
5038  * @p __comp(*(i+1),*i) is false.
5039  *
5040  * The relative ordering of equivalent elements is preserved, so any two
5041  * elements @p x and @p y in the range @p [__first,__last) such that
5042  * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5043  * relative ordering after calling @p stable_sort().
5044  */
5045  template<typename _RandomAccessIterator, typename _Compare>
5046  inline void
5047  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5048  _Compare __comp)
5049  {
5050  // concept requirements
5051  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5052  _RandomAccessIterator>)
5053  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5054  typename iterator_traits<_RandomAccessIterator>::value_type,
5055  typename iterator_traits<_RandomAccessIterator>::value_type>)
5056  __glibcxx_requires_valid_range(__first, __last);
5057  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5058 
5059  _GLIBCXX_STD_A::__stable_sort(__first, __last,
5060  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5061  }
5062 
5063  template<typename _InputIterator1, typename _InputIterator2,
5064  typename _OutputIterator,
5065  typename _Compare>
5066  _OutputIterator
5067  __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5068  _InputIterator2 __first2, _InputIterator2 __last2,
5069  _OutputIterator __result, _Compare __comp)
5070  {
5071  while (__first1 != __last1 && __first2 != __last2)
5072  {
5073  if (__comp(__first1, __first2))
5074  {
5075  *__result = *__first1;
5076  ++__first1;
5077  }
5078  else if (__comp(__first2, __first1))
5079  {
5080  *__result = *__first2;
5081  ++__first2;
5082  }
5083  else
5084  {
5085  *__result = *__first1;
5086  ++__first1;
5087  ++__first2;
5088  }
5089  ++__result;
5090  }
5091  return std::copy(__first2, __last2,
5092  std::copy(__first1, __last1, __result));
5093  }
5094 
5095  /**
5096  * @brief Return the union of two sorted ranges.
5097  * @ingroup set_algorithms
5098  * @param __first1 Start of first range.
5099  * @param __last1 End of first range.
5100  * @param __first2 Start of second range.
5101  * @param __last2 End of second range.
5102  * @param __result Start of output range.
5103  * @return End of the output range.
5104  * @ingroup set_algorithms
5105  *
5106  * This operation iterates over both ranges, copying elements present in
5107  * each range in order to the output range. Iterators increment for each
5108  * range. When the current element of one range is less than the other,
5109  * that element is copied and the iterator advanced. If an element is
5110  * contained in both ranges, the element from the first range is copied and
5111  * both ranges advance. The output range may not overlap either input
5112  * range.
5113  */
5114  template<typename _InputIterator1, typename _InputIterator2,
5115  typename _OutputIterator>
5116  inline _OutputIterator
5117  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5118  _InputIterator2 __first2, _InputIterator2 __last2,
5119  _OutputIterator __result)
5120  {
5121  // concept requirements
5122  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5123  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5124  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5125  typename iterator_traits<_InputIterator1>::value_type>)
5126  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5127  typename iterator_traits<_InputIterator2>::value_type>)
5128  __glibcxx_function_requires(_LessThanOpConcept<
5129  typename iterator_traits<_InputIterator1>::value_type,
5130  typename iterator_traits<_InputIterator2>::value_type>)
5131  __glibcxx_function_requires(_LessThanOpConcept<
5132  typename iterator_traits<_InputIterator2>::value_type,
5133  typename iterator_traits<_InputIterator1>::value_type>)
5134  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5135  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5136  __glibcxx_requires_irreflexive2(__first1, __last1);
5137  __glibcxx_requires_irreflexive2(__first2, __last2);
5138 
5139  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5140  __first2, __last2, __result,
5141  __gnu_cxx::__ops::__iter_less_iter());
5142  }
5143 
5144  /**
5145  * @brief Return the union of two sorted ranges using a comparison functor.
5146  * @ingroup set_algorithms
5147  * @param __first1 Start of first range.
5148  * @param __last1 End of first range.
5149  * @param __first2 Start of second range.
5150  * @param __last2 End of second range.
5151  * @param __result Start of output range.
5152  * @param __comp The comparison functor.
5153  * @return End of the output range.
5154  * @ingroup set_algorithms
5155  *
5156  * This operation iterates over both ranges, copying elements present in
5157  * each range in order to the output range. Iterators increment for each
5158  * range. When the current element of one range is less than the other
5159  * according to @p __comp, that element is copied and the iterator advanced.
5160  * If an equivalent element according to @p __comp is contained in both
5161  * ranges, the element from the first range is copied and both ranges
5162  * advance. The output range may not overlap either input range.
5163  */
5164  template<typename _InputIterator1, typename _InputIterator2,
5165  typename _OutputIterator, typename _Compare>
5166  inline _OutputIterator
5167  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5168  _InputIterator2 __first2, _InputIterator2 __last2,
5169  _OutputIterator __result, _Compare __comp)
5170  {
5171  // concept requirements
5172  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5173  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5174  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5175  typename iterator_traits<_InputIterator1>::value_type>)
5176  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177  typename iterator_traits<_InputIterator2>::value_type>)
5178  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5179  typename iterator_traits<_InputIterator1>::value_type,
5180  typename iterator_traits<_InputIterator2>::value_type>)
5181  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5182  typename iterator_traits<_InputIterator2>::value_type,
5183  typename iterator_traits<_InputIterator1>::value_type>)
5184  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5185  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5186  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5187  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5188 
5189  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5190  __first2, __last2, __result,
5191  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5192  }
5193 
5194  template<typename _InputIterator1, typename _InputIterator2,
5195  typename _OutputIterator,
5196  typename _Compare>
5197  _OutputIterator
5198  __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5199  _InputIterator2 __first2, _InputIterator2 __last2,
5200  _OutputIterator __result, _Compare __comp)
5201  {
5202  while (__first1 != __last1 && __first2 != __last2)
5203  if (__comp(__first1, __first2))
5204  ++__first1;
5205  else if (__comp(__first2, __first1))
5206  ++__first2;
5207  else
5208  {
5209  *__result = *__first1;
5210  ++__first1;
5211  ++__first2;
5212  ++__result;
5213  }
5214  return __result;
5215  }
5216 
5217  /**
5218  * @brief Return the intersection of two sorted ranges.
5219  * @ingroup set_algorithms
5220  * @param __first1 Start of first range.
5221  * @param __last1 End of first range.
5222  * @param __first2 Start of second range.
5223  * @param __last2 End of second range.
5224  * @param __result Start of output range.
5225  * @return End of the output range.
5226  * @ingroup set_algorithms
5227  *
5228  * This operation iterates over both ranges, copying elements present in
5229  * both ranges in order to the output range. Iterators increment for each
5230  * range. When the current element of one range is less than the other,
5231  * that iterator advances. If an element is contained in both ranges, the
5232  * element from the first range is copied and both ranges advance. The
5233  * output range may not overlap either input range.
5234  */
5235  template<typename _InputIterator1, typename _InputIterator2,
5236  typename _OutputIterator>
5237  inline _OutputIterator
5238  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5239  _InputIterator2 __first2, _InputIterator2 __last2,
5240  _OutputIterator __result)
5241  {
5242  // concept requirements
5243  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5244  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5245  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5246  typename iterator_traits<_InputIterator1>::value_type>)
5247  __glibcxx_function_requires(_LessThanOpConcept<
5248  typename iterator_traits<_InputIterator1>::value_type,
5249  typename iterator_traits<_InputIterator2>::value_type>)
5250  __glibcxx_function_requires(_LessThanOpConcept<
5251  typename iterator_traits<_InputIterator2>::value_type,
5252  typename iterator_traits<_InputIterator1>::value_type>)
5253  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5254  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5255  __glibcxx_requires_irreflexive2(__first1, __last1);
5256  __glibcxx_requires_irreflexive2(__first2, __last2);
5257 
5258  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5259  __first2, __last2, __result,
5260  __gnu_cxx::__ops::__iter_less_iter());
5261  }
5262 
5263  /**
5264  * @brief Return the intersection of two sorted ranges using comparison
5265  * functor.
5266  * @ingroup set_algorithms
5267  * @param __first1 Start of first range.
5268  * @param __last1 End of first range.
5269  * @param __first2 Start of second range.
5270  * @param __last2 End of second range.
5271  * @param __result Start of output range.
5272  * @param __comp The comparison functor.
5273  * @return End of the output range.
5274  * @ingroup set_algorithms
5275  *
5276  * This operation iterates over both ranges, copying elements present in
5277  * both ranges in order to the output range. Iterators increment for each
5278  * range. When the current element of one range is less than the other
5279  * according to @p __comp, that iterator advances. If an element is
5280  * contained in both ranges according to @p __comp, the element from the
5281  * first range is copied and both ranges advance. The output range may not
5282  * overlap either input range.
5283  */
5284  template<typename _InputIterator1, typename _InputIterator2,
5285  typename _OutputIterator, typename _Compare>
5286  inline _OutputIterator
5287  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5288  _InputIterator2 __first2, _InputIterator2 __last2,
5289  _OutputIterator __result, _Compare __comp)
5290  {
5291  // concept requirements
5292  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5293  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5294  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5295  typename iterator_traits<_InputIterator1>::value_type>)
5296  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5297  typename iterator_traits<_InputIterator1>::value_type,
5298  typename iterator_traits<_InputIterator2>::value_type>)
5299  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5300  typename iterator_traits<_InputIterator2>::value_type,
5301  typename iterator_traits<_InputIterator1>::value_type>)
5302  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5303  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5304  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5305  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5306 
5307  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5308  __first2, __last2, __result,
5309  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5310  }
5311 
5312  template<typename _InputIterator1, typename _InputIterator2,
5313  typename _OutputIterator,
5314  typename _Compare>
5315  _OutputIterator
5316  __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5317  _InputIterator2 __first2, _InputIterator2 __last2,
5318  _OutputIterator __result, _Compare __comp)
5319  {
5320  while (__first1 != __last1 && __first2 != __last2)
5321  if (__comp(__first1, __first2))
5322  {
5323  *__result = *__first1;
5324  ++__first1;
5325  ++__result;
5326  }
5327  else if (__comp(__first2, __first1))
5328  ++__first2;
5329  else
5330  {
5331  ++__first1;
5332  ++__first2;
5333  }
5334  return std::copy(__first1, __last1, __result);
5335  }
5336 
5337  /**
5338  * @brief Return the difference of two sorted ranges.
5339  * @ingroup set_algorithms
5340  * @param __first1 Start of first range.
5341  * @param __last1 End of first range.
5342  * @param __first2 Start of second range.
5343  * @param __last2 End of second range.
5344  * @param __result Start of output range.
5345  * @return End of the output range.
5346  * @ingroup set_algorithms
5347  *
5348  * This operation iterates over both ranges, copying elements present in
5349  * the first range but not the second in order to the output range.
5350  * Iterators increment for each range. When the current element of the
5351  * first range is less than the second, that element is copied and the
5352  * iterator advances. If the current element of the second range is less,
5353  * the iterator advances, but no element is copied. If an element is
5354  * contained in both ranges, no elements are copied and both ranges
5355  * advance. The output range may not overlap either input range.
5356  */
5357  template<typename _InputIterator1, typename _InputIterator2,
5358  typename _OutputIterator>
5359  inline _OutputIterator
5360  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5361  _InputIterator2 __first2, _InputIterator2 __last2,
5362  _OutputIterator __result)
5363  {
5364  // concept requirements
5365  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5366  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5367  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5368  typename iterator_traits<_InputIterator1>::value_type>)
5369  __glibcxx_function_requires(_LessThanOpConcept<
5370  typename iterator_traits<_InputIterator1>::value_type,
5371  typename iterator_traits<_InputIterator2>::value_type>)
5372  __glibcxx_function_requires(_LessThanOpConcept<
5373  typename iterator_traits<_InputIterator2>::value_type,
5374  typename iterator_traits<_InputIterator1>::value_type>)
5375  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5376  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5377  __glibcxx_requires_irreflexive2(__first1, __last1);
5378  __glibcxx_requires_irreflexive2(__first2, __last2);
5379 
5380  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5381  __first2, __last2, __result,
5382  __gnu_cxx::__ops::__iter_less_iter());
5383  }
5384 
5385  /**
5386  * @brief Return the difference of two sorted ranges using comparison
5387  * functor.
5388  * @ingroup set_algorithms
5389  * @param __first1 Start of first range.
5390  * @param __last1 End of first range.
5391  * @param __first2 Start of second range.
5392  * @param __last2 End of second range.
5393  * @param __result Start of output range.
5394  * @param __comp The comparison functor.
5395  * @return End of the output range.
5396  * @ingroup set_algorithms
5397  *
5398  * This operation iterates over both ranges, copying elements present in
5399  * the first range but not the second in order to the output range.
5400  * Iterators increment for each range. When the current element of the
5401  * first range is less than the second according to @p __comp, that element
5402  * is copied and the iterator advances. If the current element of the
5403  * second range is less, no element is copied and the iterator advances.
5404  * If an element is contained in both ranges according to @p __comp, no
5405  * elements are copied and both ranges advance. The output range may not
5406  * overlap either input range.
5407  */
5408  template<typename _InputIterator1, typename _InputIterator2,
5409  typename _OutputIterator, typename _Compare>
5410  inline _OutputIterator
5411  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5412  _InputIterator2 __first2, _InputIterator2 __last2,
5413  _OutputIterator __result, _Compare __comp)
5414  {
5415  // concept requirements
5416  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5417  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5418  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5419  typename iterator_traits<_InputIterator1>::value_type>)
5420  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5421  typename iterator_traits<_InputIterator1>::value_type,
5422  typename iterator_traits<_InputIterator2>::value_type>)
5423  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5424  typename iterator_traits<_InputIterator2>::value_type,
5425  typename iterator_traits<_InputIterator1>::value_type>)
5426  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5427  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5428  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5429  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5430 
5431  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5432  __first2, __last2, __result,
5433  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5434  }
5435 
5436  template<typename _InputIterator1, typename _InputIterator2,
5437  typename _OutputIterator,
5438  typename _Compare>
5439  _OutputIterator
5440  __set_symmetric_difference(_InputIterator1 __first1,
5441  _InputIterator1 __last1,
5442  _InputIterator2 __first2,
5443  _InputIterator2 __last2,
5444  _OutputIterator __result,
5445  _Compare __comp)
5446  {
5447  while (__first1 != __last1 && __first2 != __last2)
5448  if (__comp(__first1, __first2))
5449  {
5450  *__result = *__first1;
5451  ++__first1;
5452  ++__result;
5453  }
5454  else if (__comp(__first2, __first1))
5455  {
5456  *__result = *__first2;
5457  ++__first2;
5458  ++__result;
5459  }
5460  else
5461  {
5462  ++__first1;
5463  ++__first2;
5464  }
5465  return std::copy(__first2, __last2,
5466  std::copy(__first1, __last1, __result));
5467  }
5468 
5469  /**
5470  * @brief Return the symmetric difference of two sorted ranges.
5471  * @ingroup set_algorithms
5472  * @param __first1 Start of first range.
5473  * @param __last1 End of first range.
5474  * @param __first2 Start of second range.
5475  * @param __last2 End of second range.
5476  * @param __result Start of output range.
5477  * @return End of the output range.
5478  * @ingroup set_algorithms
5479  *
5480  * This operation iterates over both ranges, copying elements present in
5481  * one range but not the other in order to the output range. Iterators
5482  * increment for each range. When the current element of one range is less
5483  * than the other, that element is copied and the iterator advances. If an
5484  * element is contained in both ranges, no elements are copied and both
5485  * ranges advance. The output range may not overlap either input range.
5486  */
5487  template<typename _InputIterator1, typename _InputIterator2,
5488  typename _OutputIterator>
5489  inline _OutputIterator
5490  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5491  _InputIterator2 __first2, _InputIterator2 __last2,
5492  _OutputIterator __result)
5493  {
5494  // concept requirements
5495  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5496  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5497  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5498  typename iterator_traits<_InputIterator1>::value_type>)
5499  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5500  typename iterator_traits<_InputIterator2>::value_type>)
5501  __glibcxx_function_requires(_LessThanOpConcept<
5502  typename iterator_traits<_InputIterator1>::value_type,
5503  typename iterator_traits<_InputIterator2>::value_type>)
5504  __glibcxx_function_requires(_LessThanOpConcept<
5505  typename iterator_traits<_InputIterator2>::value_type,
5506  typename iterator_traits<_InputIterator1>::value_type>)
5507  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5508  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5509  __glibcxx_requires_irreflexive2(__first1, __last1);
5510  __glibcxx_requires_irreflexive2(__first2, __last2);
5511 
5512  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5513  __first2, __last2, __result,
5514  __gnu_cxx::__ops::__iter_less_iter());
5515  }
5516 
5517  /**
5518  * @brief Return the symmetric difference of two sorted ranges using
5519  * comparison functor.
5520  * @ingroup set_algorithms
5521  * @param __first1 Start of first range.
5522  * @param __last1 End of first range.
5523  * @param __first2 Start of second range.
5524  * @param __last2 End of second range.
5525  * @param __result Start of output range.
5526  * @param __comp The comparison functor.
5527  * @return End of the output range.
5528  * @ingroup set_algorithms
5529  *
5530  * This operation iterates over both ranges, copying elements present in
5531  * one range but not the other in order to the output range. Iterators
5532  * increment for each range. When the current element of one range is less
5533  * than the other according to @p comp, that element is copied and the
5534  * iterator advances. If an element is contained in both ranges according
5535  * to @p __comp, no elements are copied and both ranges advance. The output
5536  * range may not overlap either input range.
5537  */
5538  template<typename _InputIterator1, typename _InputIterator2,
5539  typename _OutputIterator, typename _Compare>
5540  inline _OutputIterator
5541  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5542  _InputIterator2 __first2, _InputIterator2 __last2,
5543  _OutputIterator __result,
5544  _Compare __comp)
5545  {
5546  // concept requirements
5547  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5548  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5549  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5550  typename iterator_traits<_InputIterator1>::value_type>)
5551  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5552  typename iterator_traits<_InputIterator2>::value_type>)
5553  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5554  typename iterator_traits<_InputIterator1>::value_type,
5555  typename iterator_traits<_InputIterator2>::value_type>)
5556  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5557  typename iterator_traits<_InputIterator2>::value_type,
5558  typename iterator_traits<_InputIterator1>::value_type>)
5559  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5560  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5561  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5562  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5563 
5564  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5565  __first2, __last2, __result,
5566  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5567  }
5568 
5569  template<typename _ForwardIterator, typename _Compare>
5570  _GLIBCXX14_CONSTEXPR
5571  _ForwardIterator
5572  __min_element(_ForwardIterator __first, _ForwardIterator __last,
5573  _Compare __comp)
5574  {
5575  if (__first == __last)
5576  return __first;
5577  _ForwardIterator __result = __first;
5578  while (++__first != __last)
5579  if (__comp(__first, __result))
5580  __result = __first;
5581  return __result;
5582  }
5583 
5584  /**
5585  * @brief Return the minimum element in a range.
5586  * @ingroup sorting_algorithms
5587  * @param __first Start of range.
5588  * @param __last End of range.
5589  * @return Iterator referencing the first instance of the smallest value.
5590  */
5591  template<typename _ForwardIterator>
5592  _GLIBCXX14_CONSTEXPR
5593  _ForwardIterator
5594  inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5595  {
5596  // concept requirements
5597  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5598  __glibcxx_function_requires(_LessThanComparableConcept<
5599  typename iterator_traits<_ForwardIterator>::value_type>)
5600  __glibcxx_requires_valid_range(__first, __last);
5601  __glibcxx_requires_irreflexive(__first, __last);
5602 
5603  return _GLIBCXX_STD_A::__min_element(__first, __last,
5604  __gnu_cxx::__ops::__iter_less_iter());
5605  }
5606 
5607  /**
5608  * @brief Return the minimum element in a range using comparison functor.
5609  * @ingroup sorting_algorithms
5610  * @param __first Start of range.
5611  * @param __last End of range.
5612  * @param __comp Comparison functor.
5613  * @return Iterator referencing the first instance of the smallest value
5614  * according to __comp.
5615  */
5616  template<typename _ForwardIterator, typename _Compare>
5617  _GLIBCXX14_CONSTEXPR
5618  inline _ForwardIterator
5619  min_element(_ForwardIterator __first, _ForwardIterator __last,
5620  _Compare __comp)
5621  {
5622  // concept requirements
5623  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5624  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5625  typename iterator_traits<_ForwardIterator>::value_type,
5626  typename iterator_traits<_ForwardIterator>::value_type>)
5627  __glibcxx_requires_valid_range(__first, __last);
5628  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5629 
5630  return _GLIBCXX_STD_A::__min_element(__first, __last,
5631  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5632  }
5633 
5634  template<typename _ForwardIterator, typename _Compare>
5635  _GLIBCXX14_CONSTEXPR
5636  _ForwardIterator
5637  __max_element(_ForwardIterator __first, _ForwardIterator __last,
5638  _Compare __comp)
5639  {
5640  if (__first == __last) return __first;
5641  _ForwardIterator __result = __first;
5642  while (++__first != __last)
5643  if (__comp(__result, __first))
5644  __result = __first;
5645  return __result;
5646  }
5647 
5648  /**
5649  * @brief Return the maximum element in a range.
5650  * @ingroup sorting_algorithms
5651  * @param __first Start of range.
5652  * @param __last End of range.
5653  * @return Iterator referencing the first instance of the largest value.
5654  */
5655  template<typename _ForwardIterator>
5656  _GLIBCXX14_CONSTEXPR
5657  inline _ForwardIterator
5658  max_element(_ForwardIterator __first, _ForwardIterator __last)
5659  {
5660  // concept requirements
5661  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5662  __glibcxx_function_requires(_LessThanComparableConcept<
5663  typename iterator_traits<_ForwardIterator>::value_type>)
5664  __glibcxx_requires_valid_range(__first, __last);
5665  __glibcxx_requires_irreflexive(__first, __last);
5666 
5667  return _GLIBCXX_STD_A::__max_element(__first, __last,
5668  __gnu_cxx::__ops::__iter_less_iter());
5669  }
5670 
5671  /**
5672  * @brief Return the maximum element in a range using comparison functor.
5673  * @ingroup sorting_algorithms
5674  * @param __first Start of range.
5675  * @param __last End of range.
5676  * @param __comp Comparison functor.
5677  * @return Iterator referencing the first instance of the largest value
5678  * according to __comp.
5679  */
5680  template<typename _ForwardIterator, typename _Compare>
5681  _GLIBCXX14_CONSTEXPR
5682  inline _ForwardIterator
5683  max_element(_ForwardIterator __first, _ForwardIterator __last,
5684  _Compare __comp)
5685  {
5686  // concept requirements
5687  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5688  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5689  typename iterator_traits<_ForwardIterator>::value_type,
5690  typename iterator_traits<_ForwardIterator>::value_type>)
5691  __glibcxx_requires_valid_range(__first, __last);
5692  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5693 
5694  return _GLIBCXX_STD_A::__max_element(__first, __last,
5695  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5696  }
5697 
5698 #if __cplusplus >= 201402L
5699  /// Reservoir sampling algorithm.
5700  template<typename _InputIterator, typename _RandomAccessIterator,
5701  typename _Size, typename _UniformRandomBitGenerator>
5702  _RandomAccessIterator
5703  __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5704  _RandomAccessIterator __out, random_access_iterator_tag,
5705  _Size __n, _UniformRandomBitGenerator&& __g)
5706  {
5707  using __distrib_type = uniform_int_distribution<_Size>;
5708  using __param_type = typename __distrib_type::param_type;
5709  __distrib_type __d{};
5710  _Size __sample_sz = 0;
5711  while (__first != __last && __sample_sz != __n)
5712  {
5713  __out[__sample_sz++] = *__first;
5714  ++__first;
5715  }
5716  for (auto __pop_sz = __sample_sz; __first != __last;
5717  ++__first, (void) ++__pop_sz)
5718  {
5719  const auto __k = __d(__g, __param_type{0, __pop_sz});
5720  if (__k < __n)
5721  __out[__k] = *__first;
5722  }
5723  return __out + __sample_sz;
5724  }
5725 
5726  /// Selection sampling algorithm.
5727  template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5728  typename _Size, typename _UniformRandomBitGenerator>
5729  _OutputIterator
5730  __sample(_ForwardIterator __first, _ForwardIterator __last,
5732  _OutputIterator __out, _Cat,
5733  _Size __n, _UniformRandomBitGenerator&& __g)
5734  {
5735  using __distrib_type = uniform_int_distribution<_Size>;
5736  using __param_type = typename __distrib_type::param_type;
5737  using _USize = make_unsigned_t<_Size>;
5740 
5741  __distrib_type __d{};
5742  _Size __unsampled_sz = std::distance(__first, __last);
5743  __n = std::min(__n, __unsampled_sz);
5744 
5745  // If possible, we use __gen_two_uniform_ints to efficiently produce
5746  // two random numbers using a single distribution invocation:
5747 
5748  const __uc_type __urngrange = __g.max() - __g.min();
5749  if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5750  // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5751  // wrapping issues.
5752  {
5753  while (__n != 0 && __unsampled_sz >= 2)
5754  {
5755  const pair<_Size, _Size> __p =
5756  __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
5757 
5758  --__unsampled_sz;
5759  if (__p.first < __n)
5760  {
5761  *__out++ = *__first;
5762  --__n;
5763  }
5764 
5765  ++__first;
5766 
5767  if (__n == 0) break;
5768 
5769  --__unsampled_sz;
5770  if (__p.second < __n)
5771  {
5772  *__out++ = *__first;
5773  --__n;
5774  }
5775 
5776  ++__first;
5777  }
5778  }
5779 
5780  // The loop above is otherwise equivalent to this one-at-a-time version:
5781 
5782  for (; __n != 0; ++__first)
5783  if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5784  {
5785  *__out++ = *__first;
5786  --__n;
5787  }
5788  return __out;
5789  }
5790 
5791 #if __cplusplus > 201402L
5792 #define __cpp_lib_sample 201603
5793  /// Take a random sample from a population.
5794  template<typename _PopulationIterator, typename _SampleIterator,
5795  typename _Distance, typename _UniformRandomBitGenerator>
5796  _SampleIterator
5797  sample(_PopulationIterator __first, _PopulationIterator __last,
5798  _SampleIterator __out, _Distance __n,
5799  _UniformRandomBitGenerator&& __g)
5800  {
5801  using __pop_cat = typename
5802  std::iterator_traits<_PopulationIterator>::iterator_category;
5803  using __samp_cat = typename
5804  std::iterator_traits<_SampleIterator>::iterator_category;
5805 
5806  static_assert(
5807  __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5808  is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5809  "output range must use a RandomAccessIterator when input range"
5810  " does not meet the ForwardIterator requirements");
5811 
5812  static_assert(is_integral<_Distance>::value,
5813  "sample size must be an integer type");
5814 
5815  typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5816  return _GLIBCXX_STD_A::
5817  __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5818  std::forward<_UniformRandomBitGenerator>(__g));
5819  }
5820 #endif // C++17
5821 #endif // C++14
5822 
5823 _GLIBCXX_END_NAMESPACE_ALGO
5824 _GLIBCXX_END_NAMESPACE_VERSION
5825 } // namespace std
5826 
5827 #endif /* _STL_ALGO_H */
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
Definition: stl_algo.h:5619
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
Definition: stl_algo.h:1657
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
Definition: stl_algo.h:257
Marking output iterators.
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
Definition: stl_algo.h:3286
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1885
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
Definition: stl_algo.h:3905
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
Definition: stl_algobase.h:123
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
Definition: stl_algo.h:5703
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1810
ISO C++ entities toplevel namespace is std.
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
Definition: stl_algo.h:525
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1540
Marking input iterators.
_InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
Definition: stl_algo.h:181
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
Definition: stl_algo.h:5730
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
Definition: stl_algo.h:5683
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
Definition: stl_algo.h:1478
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2461
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
_GLIBCXX14_CONSTEXPR pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
Definition: stl_algo.h:3415
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
Definition: stl_algo.h:101
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
Definition: stl_algo.h:168
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
Definition: stl_algo.h:2623
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition: type_traits:1870
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:222
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
Definition: stl_algo.h:1539
void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
Definition: stl_algo.h:78
Random-access iterators support a superset of bidirectional iterator operations.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
Definition: stl_algo.h:1232
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1869
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1906
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
Definition: stl_algo.h:1049
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1829
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
Definition: stl_algo.h:2319
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
Definition: stl_algo.h:2293
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1852
common_type
Definition: type_traits:2111
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Definition: stl_algobase.h:169
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
Definition: stl_algo.h:1132
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
Definition: stl_algo.h:3753
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
Bidirectional iterators support a superset of forward iterator operations.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
Definition: stl_algo.h:1249
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
Definition: stl_algo.h:558
Forward iterators support a superset of input iterator operations.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
Definition: stl_algo.h:2745
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:198
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2400
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
Definition: stl_algo.h:1419
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
Definition: type_traits:2426
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
Definition: stl_algo.h:3260
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
Definition: stl_algo.h:2362
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1929