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