Clang Project

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