1    	// Algorithm implementation -*- C++ -*-
2    	
3    	// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4    	//
5    	// This file is part of the GNU ISO C++ Library.  This library is free
6    	// software; you can redistribute it and/or modify it under the
7    	// terms of the GNU General Public License as published by the
8    	// Free Software Foundation; either version 3, or (at your option)
9    	// any later version.
10   	
11   	// This library is distributed in the hope that it will be useful,
12   	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13   	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   	// GNU General Public License for more details.
15   	
16   	// Under Section 7 of GPL version 3, you are granted additional
17   	// permissions described in the GCC Runtime Library Exception, version
18   	// 3.1, as published by the Free Software Foundation.
19   	
20   	// You should have received a copy of the GNU General Public License and
21   	// a copy of the GCC Runtime Library Exception along with this program;
22   	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23   	// <http://www.gnu.org/licenses/>.
24   	
25   	/*
26   	 *
27   	 * Copyright (c) 1994
28   	 * Hewlett-Packard Company
29   	 *
30   	 * Permission to use, copy, modify, distribute and sell this software
31   	 * and its documentation for any purpose is hereby granted without fee,
32   	 * provided that the above copyright notice appear in all copies and
33   	 * that both that copyright notice and this permission notice appear
34   	 * in supporting documentation.  Hewlett-Packard Company makes no
35   	 * representations about the suitability of this software for any
36   	 * purpose.  It is provided "as is" without express or implied warranty.
37   	 *
38   	 *
39   	 * Copyright (c) 1996
40   	 * Silicon Graphics Computer Systems, Inc.
41   	 *
42   	 * Permission to use, copy, modify, distribute and sell this software
43   	 * and its documentation for any purpose is hereby granted without fee,
44   	 * provided that the above copyright notice appear in all copies and
45   	 * that both that copyright notice and this permission notice appear
46   	 * in supporting documentation.  Silicon Graphics makes no
47   	 * representations about the suitability of this software for any
48   	 * purpose.  It is provided "as is" without express or implied warranty.
49   	 */
50   	
51   	/** @file bits/stl_algo.h
52   	 *  This is an internal header file, included by other library headers.
53   	 *  Do not attempt to use it directly. @headername{algorithm}
54   	 */
55   	
56   	#ifndef _STL_ALGO_H
57   	#define _STL_ALGO_H 1
58   	
59   	#include <cstdlib>	     // for rand
60   	#include <bits/algorithmfwd.h>
61   	#include <bits/stl_heap.h>
62   	#include <bits/stl_tempbuf.h>  // for _Temporary_buffer
63   	#include <bits/predefined_ops.h>
64   	
65   	#if __cplusplus >= 201103L
66   	#include <bits/uniform_int_dist.h>
67   	#endif
68   	
69   	// See concept_check.h for the __glibcxx_*_requires macros.
70   	
71   	namespace std _GLIBCXX_VISIBILITY(default)
72   	{
73   	_GLIBCXX_BEGIN_NAMESPACE_VERSION
74   	
75   	  /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76   	  template<typename _Iterator, typename _Compare>
77   	    void
78   	    __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
79   				   _Iterator __c, _Compare __comp)
80   	    {
81   	      if (__comp(__a, __b))
82   		{
83   		  if (__comp(__b, __c))
84   		    std::iter_swap(__result, __b);
85   		  else if (__comp(__a, __c))
86   		    std::iter_swap(__result, __c);
87   		  else
88   		    std::iter_swap(__result, __a);
89   		}
90   	      else if (__comp(__a, __c))
91   		std::iter_swap(__result, __a);
92   	      else if (__comp(__b, __c))
93   		std::iter_swap(__result, __c);
94   	      else
95   		std::iter_swap(__result, __b);
96   	    }
97   	
98   	  /// This is an overload used by find algos for the Input Iterator case.
99   	  template<typename _InputIterator, typename _Predicate>
100  	    inline _InputIterator
101  	    __find_if(_InputIterator __first, _InputIterator __last,
102  		      _Predicate __pred, input_iterator_tag)
103  	    {
104  	      while (__first != __last && !__pred(__first))
105  		++__first;
106  	      return __first;
107  	    }
108  	
109  	  /// This is an overload used by find algos for the RAI case.
110  	  template<typename _RandomAccessIterator, typename _Predicate>
111  	    _RandomAccessIterator
112  	    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
113  		      _Predicate __pred, random_access_iterator_tag)
114  	    {
115  	      typename iterator_traits<_RandomAccessIterator>::difference_type
116  		__trip_count = (__last - __first) >> 2;
117  	
118  	      for (; __trip_count > 0; --__trip_count)
119  		{
120  		  if (__pred(__first))
121  		    return __first;
122  		  ++__first;
123  	
124  		  if (__pred(__first))
125  		    return __first;
126  		  ++__first;
127  	
128  		  if (__pred(__first))
129  		    return __first;
130  		  ++__first;
131  	
132  		  if (__pred(__first))
133  		    return __first;
134  		  ++__first;
135  		}
136  	
137  	      switch (__last - __first)
138  		{
139  		case 3:
140  		  if (__pred(__first))
141  		    return __first;
142  		  ++__first;
143  		case 2:
144  		  if (__pred(__first))
145  		    return __first;
146  		  ++__first;
147  		case 1:
148  		  if (__pred(__first))
149  		    return __first;
150  		  ++__first;
151  		case 0:
152  		default:
153  		  return __last;
154  		}
155  	    }
156  	
157  	  template<typename _Iterator, typename _Predicate>
158  	    inline _Iterator
159  	    __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
160  	    {
161  	      return __find_if(__first, __last, __pred,
162  			       std::__iterator_category(__first));
163  	    }
164  	
165  	  /// Provided for stable_partition to use.
166  	  template<typename _InputIterator, typename _Predicate>
167  	    inline _InputIterator
168  	    __find_if_not(_InputIterator __first, _InputIterator __last,
169  			  _Predicate __pred)
170  	    {
171  	      return std::__find_if(__first, __last,
172  				    __gnu_cxx::__ops::__negate(__pred),
173  				    std::__iterator_category(__first));
174  	    }
175  	
176  	  /// Like find_if_not(), but uses and updates a count of the
177  	  /// remaining range length instead of comparing against an end
178  	  /// iterator.
179  	  template<typename _InputIterator, typename _Predicate, typename _Distance>
180  	    _InputIterator
181  	    __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
182  	    {
183  	      for (; __len; --__len, ++__first)
184  		if (!__pred(__first))
185  		  break;
186  	      return __first;
187  	    }
188  	
189  	  // set_difference
190  	  // set_intersection
191  	  // set_symmetric_difference
192  	  // set_union
193  	  // for_each
194  	  // find
195  	  // find_if
196  	  // find_first_of
197  	  // adjacent_find
198  	  // count
199  	  // count_if
200  	  // search
201  	
202  	  template<typename _ForwardIterator1, typename _ForwardIterator2,
203  		   typename _BinaryPredicate>
204  	    _ForwardIterator1
205  	    __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206  		     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207  		     _BinaryPredicate  __predicate)
208  	    {
209  	      // Test for empty ranges
210  	      if (__first1 == __last1 || __first2 == __last2)
211  		return __first1;
212  	
213  	      // Test for a pattern of length 1.
214  	      _ForwardIterator2 __p1(__first2);
215  	      if (++__p1 == __last2)
216  		return std::__find_if(__first1, __last1,
217  			__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
218  	
219  	      // General case.
220  	      _ForwardIterator2 __p;
221  	      _ForwardIterator1 __current = __first1;
222  	
223  	      for (;;)
224  		{
225  		  __first1 =
226  		    std::__find_if(__first1, __last1,
227  			__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
228  	
229  		  if (__first1 == __last1)
230  		    return __last1;
231  	
232  		  __p = __p1;
233  		  __current = __first1;
234  		  if (++__current == __last1)
235  		    return __last1;
236  	
237  		  while (__predicate(__current, __p))
238  		    {
239  		      if (++__p == __last2)
240  			return __first1;
241  		      if (++__current == __last1)
242  			return __last1;
243  		    }
244  		  ++__first1;
245  		}
246  	      return __first1;
247  	    }
248  	
249  	  // search_n
250  	
251  	  /**
252  	   *  This is an helper function for search_n overloaded for forward iterators.
253  	  */
254  	  template<typename _ForwardIterator, typename _Integer,
255  		   typename _UnaryPredicate>
256  	    _ForwardIterator
257  	    __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
258  			   _Integer __count, _UnaryPredicate __unary_pred,
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