1    	// Core algorithmic facilities -*- 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-1998
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_algobase.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_ALGOBASE_H
57   	#define _STL_ALGOBASE_H 1
58   	
59   	#include <bits/c++config.h>
60   	#include <bits/functexcept.h>
61   	#include <bits/cpp_type_traits.h>
62   	#include <ext/type_traits.h>
63   	#include <ext/numeric_traits.h>
64   	#include <bits/stl_pair.h>
65   	#include <bits/stl_iterator_base_types.h>
66   	#include <bits/stl_iterator_base_funcs.h>
67   	#include <bits/stl_iterator.h>
68   	#include <bits/concept_check.h>
69   	#include <debug/debug.h>
70   	#include <bits/move.h> // For std::swap and _GLIBCXX_MOVE
71   	#include <bits/predefined_ops.h>
72   	
73   	namespace std _GLIBCXX_VISIBILITY(default)
74   	{
75   	_GLIBCXX_BEGIN_NAMESPACE_VERSION
76   	
77   	#if __cplusplus < 201103L
78   	  // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
79   	  // nutshell, we are partially implementing the resolution of DR 187,
80   	  // when it's safe, i.e., the value_types are equal.
81   	  template<bool _BoolType>
82   	    struct __iter_swap
83   	    {
84   	      template<typename _ForwardIterator1, typename _ForwardIterator2>
85   	        static void
86   	        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
87   	        {
88   	          typedef typename iterator_traits<_ForwardIterator1>::value_type
89   	            _ValueType1;
90   	          _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
91   	          *__a = _GLIBCXX_MOVE(*__b);
92   	          *__b = _GLIBCXX_MOVE(__tmp);
93   		}
94   	    };
95   	
96   	  template<>
97   	    struct __iter_swap<true>
98   	    {
99   	      template<typename _ForwardIterator1, typename _ForwardIterator2>
100  	        static void 
101  	        iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
102  	        {
103  	          swap(*__a, *__b);
104  	        }
105  	    };
106  	#endif
107  	
108  	  /**
109  	   *  @brief Swaps the contents of two iterators.
110  	   *  @ingroup mutating_algorithms
111  	   *  @param  __a  An iterator.
112  	   *  @param  __b  Another iterator.
113  	   *  @return   Nothing.
114  	   *
115  	   *  This function swaps the values pointed to by two iterators, not the
116  	   *  iterators themselves.
117  	  */
118  	  template<typename _ForwardIterator1, typename _ForwardIterator2>
119  	    inline void
120  	    iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
121  	    {
122  	      // concept requirements
123  	      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
124  					  _ForwardIterator1>)
125  	      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
126  					  _ForwardIterator2>)
127  	
128  	#if __cplusplus < 201103L
129  	      typedef typename iterator_traits<_ForwardIterator1>::value_type
130  		_ValueType1;
131  	      typedef typename iterator_traits<_ForwardIterator2>::value_type
132  		_ValueType2;
133  	
134  	      __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
135  					  _ValueType2>)
136  	      __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
137  					  _ValueType1>)
138  	
139  	      typedef typename iterator_traits<_ForwardIterator1>::reference
140  		_ReferenceType1;
141  	      typedef typename iterator_traits<_ForwardIterator2>::reference
142  		_ReferenceType2;
143  	      std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
144  		&& __are_same<_ValueType1&, _ReferenceType1>::__value
145  		&& __are_same<_ValueType2&, _ReferenceType2>::__value>::
146  		iter_swap(__a, __b);
147  	#else
148  	      swap(*__a, *__b);
149  	#endif
150  	    }
151  	
152  	  /**
153  	   *  @brief Swap the elements of two sequences.
154  	   *  @ingroup mutating_algorithms
155  	   *  @param  __first1  A forward iterator.
156  	   *  @param  __last1   A forward iterator.
157  	   *  @param  __first2  A forward iterator.
158  	   *  @return   An iterator equal to @p first2+(last1-first1).
159  	   *
160  	   *  Swaps each element in the range @p [first1,last1) with the
161  	   *  corresponding element in the range @p [first2,(last1-first1)).
162  	   *  The ranges must not overlap.
163  	  */
164  	  template<typename _ForwardIterator1, typename _ForwardIterator2>
165  	    _ForwardIterator2
166  	    swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
167  			_ForwardIterator2 __first2)
168  	    {
169  	      // concept requirements
170  	      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
171  					  _ForwardIterator1>)
172  	      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
173  					  _ForwardIterator2>)
174  	      __glibcxx_requires_valid_range(__first1, __last1);
175  	
176  	      for (; __first1 != __last1; ++__first1, (void)++__first2)
177  		std::iter_swap(__first1, __first2);
178  	      return __first2;
179  	    }
180  	
181  	  /**
182  	   *  @brief This does what you think it does.
183  	   *  @ingroup sorting_algorithms
184  	   *  @param  __a  A thing of arbitrary type.
185  	   *  @param  __b  Another thing of arbitrary type.
186  	   *  @return   The lesser of the parameters.
187  	   *
188  	   *  This is the simple classic generic implementation.  It will work on
189  	   *  temporary expressions, since they are only evaluated once, unlike a
190  	   *  preprocessor macro.
191  	  */
192  	  template<typename _Tp>
193  	    _GLIBCXX14_CONSTEXPR
194  	    inline const _Tp&
195  	    min(const _Tp& __a, const _Tp& __b)
196  	    {
197  	      // concept requirements
198  	      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
199  	      //return __b < __a ? __b : __a;
200  	      if (__b < __a)
201  		return __b;
202  	      return __a;
203  	    }
204  	
205  	  /**
206  	   *  @brief This does what you think it does.
207  	   *  @ingroup sorting_algorithms
208  	   *  @param  __a  A thing of arbitrary type.
209  	   *  @param  __b  Another thing of arbitrary type.
210  	   *  @return   The greater of the parameters.
211  	   *
212  	   *  This is the simple classic generic implementation.  It will work on
213  	   *  temporary expressions, since they are only evaluated once, unlike a
214  	   *  preprocessor macro.
215  	  */
216  	  template<typename _Tp>
217  	    _GLIBCXX14_CONSTEXPR
218  	    inline const _Tp&
219  	    max(const _Tp& __a, const _Tp& __b)
220  	    {
221  	      // concept requirements
222  	      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
223  	      //return  __a < __b ? __b : __a;
224  	      if (__a < __b)
225  		return __b;
226  	      return __a;
227  	    }
228  	
229  	  /**
230  	   *  @brief This does what you think it does.
231  	   *  @ingroup sorting_algorithms
232  	   *  @param  __a  A thing of arbitrary type.
233  	   *  @param  __b  Another thing of arbitrary type.
234  	   *  @param  __comp  A @link comparison_functors comparison functor@endlink.
235  	   *  @return   The lesser of the parameters.
236  	   *
237  	   *  This will work on temporary expressions, since they are only evaluated
238  	   *  once, unlike a preprocessor macro.
239  	  */
240  	  template<typename _Tp, typename _Compare>
241  	    _GLIBCXX14_CONSTEXPR
242  	    inline const _Tp&
243  	    min(const _Tp& __a, const _Tp& __b, _Compare __comp)
244  	    {
245  	      //return __comp(__b, __a) ? __b : __a;
246  	      if (__comp(__b, __a))
247  		return __b;
248  	      return __a;
249  	    }
250  	
251  	  /**
252  	   *  @brief This does what you think it does.
253  	   *  @ingroup sorting_algorithms
254  	   *  @param  __a  A thing of arbitrary type.
255  	   *  @param  __b  Another thing of arbitrary type.
256  	   *  @param  __comp  A @link comparison_functors comparison functor@endlink.
257  	   *  @return   The greater of the parameters.
258  	   *
259  	   *  This will work on temporary expressions, since they are only evaluated
260  	   *  once, unlike a preprocessor macro.
261  	  */
262  	  template<typename _Tp, typename _Compare>
263  	    _GLIBCXX14_CONSTEXPR
264  	    inline const _Tp&
265  	    max(const _Tp& __a, const _Tp& __b, _Compare __comp)
266  	    {
267  	      //return __comp(__a, __b) ? __b : __a;
268  	      if (__comp(__a, __b))
269  		return __b;
270  	      return __a;
271  	    }
272  	
273  	  // Fallback implementation of the function in bits/stl_iterator.h used to
274  	  // remove the __normal_iterator wrapper. See copy, fill, ...
275  	  template<typename _Iterator>
276  	    inline _Iterator
277  	    __niter_base(_Iterator __it)
278  	    { return __it; }
279  	
280  	  // All of these auxiliary structs serve two purposes.  (1) Replace
281  	  // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
282  	  // because the input and output ranges are permitted to overlap.)
283  	  // (2) If we're using random access iterators, then write the loop as
284  	  // a for loop with an explicit count.
285  	
286  	  template<bool, bool, typename>
287  	    struct __copy_move
288  	    {
289  	      template<typename _II, typename _OI>
290  	        static _OI
291  	        __copy_m(_II __first, _II __last, _OI __result)
292  	        {
293  		  for (; __first != __last; ++__result, (void)++__first)
294  		    *__result = *__first;
295  		  return __result;
296  		}
297  	    };
298  	
299  	#if __cplusplus >= 201103L
300  	  template<typename _Category>
301  	    struct __copy_move<true, false, _Category>
302  	    {
303  	      template<typename _II, typename _OI>
304  	        static _OI
305  	        __copy_m(_II __first, _II __last, _OI __result)
306  	        {
307  		  for (; __first != __last; ++__result, (void)++__first)
308  		    *__result = std::move(*__first);
309  		  return __result;
310  		}
311  	    };
312  	#endif
313  	
314  	  template<>
315  	    struct __copy_move<false, false, random_access_iterator_tag>
316  	    {
317  	      template<typename _II, typename _OI>
318  	        static _OI
319  	        __copy_m(_II __first, _II __last, _OI __result)
320  	        { 
321  		  typedef typename iterator_traits<_II>::difference_type _Distance;
322  		  for(_Distance __n = __last - __first; __n > 0; --__n)
323  		    {
324  		      *__result = *__first;
325  		      ++__first;
326  		      ++__result;
327  		    }
328  		  return __result;
329  		}
330  	    };
331  	
332  	#if __cplusplus >= 201103L
333  	  template<>
334  	    struct __copy_move<true, false, random_access_iterator_tag>
335  	    {
336  	      template<typename _II, typename _OI>
337  	        static _OI
338  	        __copy_m(_II __first, _II __last, _OI __result)
339  	        { 
340  		  typedef typename iterator_traits<_II>::difference_type _Distance;
341  		  for(_Distance __n = __last - __first; __n > 0; --__n)
342  		    {
343  		      *__result = std::move(*__first);
344  		      ++__first;
345  		      ++__result;
346  		    }
347  		  return __result;
348  		}
349  	    };
350  	#endif
351  	
352  	  template<bool _IsMove>
353  	    struct __copy_move<_IsMove, true, random_access_iterator_tag>
354  	    {
355  	      template<typename _Tp>
356  	        static _Tp*
357  	        __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
358  	        {
359  	#if __cplusplus >= 201103L
360  		  using __assignable = conditional<_IsMove,
361  						   is_move_assignable<_Tp>,
362  						   is_copy_assignable<_Tp>>;
363  		  // trivial types can have deleted assignment
364  		  static_assert( __assignable::type::value, "type is not assignable" );
365  	#endif
366  		  const ptrdiff_t _Num = __last - __first;
367  		  if (_Num)
368  		    __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
369  		  return __result + _Num;
370  		}
371  	    };
372  	
373  	  template<bool _IsMove, typename _II, typename _OI>
374  	    inline _OI
375  	    __copy_move_a(_II __first, _II __last, _OI __result)
376  	    {
377  	      typedef typename iterator_traits<_II>::value_type _ValueTypeI;
378  	      typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
379  	      typedef typename iterator_traits<_II>::iterator_category _Category;
380  	      const bool __simple = (__is_trivial(_ValueTypeI)
381  		                     && __is_pointer<_II>::__value
382  		                     && __is_pointer<_OI>::__value
383  				     && __are_same<_ValueTypeI, _ValueTypeO>::__value);
384  	
385  	      return std::__copy_move<_IsMove, __simple,
386  		                      _Category>::__copy_m(__first, __last, __result);
387  	    }
388  	
389  	  // Helpers for streambuf iterators (either istream or ostream).
390  	  // NB: avoid including <iosfwd>, relatively large.
391  	  template<typename _CharT>
392  	    struct char_traits;
393  	
394  	  template<typename _CharT, typename _Traits>
395  	    class istreambuf_iterator;
396  	
397  	  template<typename _CharT, typename _Traits>
398  	    class ostreambuf_iterator;
399  	
400  	  template<bool _IsMove, typename _CharT>
401  	    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
402  		     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
403  	    __copy_move_a2(_CharT*, _CharT*,
404  			   ostreambuf_iterator<_CharT, char_traits<_CharT> >);
405  	
406  	  template<bool _IsMove, typename _CharT>
407  	    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
408  		     ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
409  	    __copy_move_a2(const _CharT*, const _CharT*,
410  			   ostreambuf_iterator<_CharT, char_traits<_CharT> >);
411  	
412  	  template<bool _IsMove, typename _CharT>
413  	    typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
414  					    _CharT*>::__type
415  	    __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
416  			   istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
417  	
418  	  template<bool _IsMove, typename _II, typename _OI>
419  	    inline _OI
420  	    __copy_move_a2(_II __first, _II __last, _OI __result)
421  	    {
422  	      return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
423  						     std::__niter_base(__last),
424  						     std::__niter_base(__result)));
425  	    }
426  	
427  	  /**
428  	   *  @brief Copies the range [first,last) into result.
429  	   *  @ingroup mutating_algorithms
430  	   *  @param  __first  An input iterator.
431  	   *  @param  __last   An input iterator.
432  	   *  @param  __result An output iterator.
433  	   *  @return   result + (first - last)
434  	   *
435  	   *  This inline function will boil down to a call to @c memmove whenever
436  	   *  possible.  Failing that, if random access iterators are passed, then the
437  	   *  loop count will be known (and therefore a candidate for compiler
438  	   *  optimizations such as unrolling).  Result may not be contained within
439  	   *  [first,last); the copy_backward function should be used instead.
440  	   *
441  	   *  Note that the end of the output range is permitted to be contained
442  	   *  within [first,last).
443  	  */
444  	  template<typename _II, typename _OI>
445  	    inline _OI
446  	    copy(_II __first, _II __last, _OI __result)
447  	    {
448  	      // concept requirements
449  	      __glibcxx_function_requires(_InputIteratorConcept<_II>)
450  	      __glibcxx_function_requires(_OutputIteratorConcept<_OI,
451  		    typename iterator_traits<_II>::value_type>)
452  	      __glibcxx_requires_valid_range(__first, __last);
453  	
454  	      return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
455  		      (std::__miter_base(__first), std::__miter_base(__last),
456  		       __result));
457  	    }
458  	
459  	#if __cplusplus >= 201103L
460  	  /**
461  	   *  @brief Moves the range [first,last) into result.
462  	   *  @ingroup mutating_algorithms
463  	   *  @param  __first  An input iterator.
464  	   *  @param  __last   An input iterator.
465  	   *  @param  __result An output iterator.
466  	   *  @return   result + (first - last)
467  	   *
468  	   *  This inline function will boil down to a call to @c memmove whenever
469  	   *  possible.  Failing that, if random access iterators are passed, then the
470  	   *  loop count will be known (and therefore a candidate for compiler
471  	   *  optimizations such as unrolling).  Result may not be contained within
472  	   *  [first,last); the move_backward function should be used instead.
473  	   *
474  	   *  Note that the end of the output range is permitted to be contained
475  	   *  within [first,last).
476  	  */
477  	  template<typename _II, typename _OI>
478  	    inline _OI
479  	    move(_II __first, _II __last, _OI __result)
480  	    {
481  	      // concept requirements
482  	      __glibcxx_function_requires(_InputIteratorConcept<_II>)
483  	      __glibcxx_function_requires(_OutputIteratorConcept<_OI,
484  		    typename iterator_traits<_II>::value_type>)
485  	      __glibcxx_requires_valid_range(__first, __last);
486  	
487  	      return std::__copy_move_a2<true>(std::__miter_base(__first),
488  					       std::__miter_base(__last), __result);
489  	    }
490  	
491  	#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
492  	#else
493  	#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
494  	#endif
495  	
496  	  template<bool, bool, typename>
497  	    struct __copy_move_backward
498  	    {
499  	      template<typename _BI1, typename _BI2>
500  	        static _BI2
501  	        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
502  	        {
503  		  while (__first != __last)
504  		    *--__result = *--__last;
505  		  return __result;
506  		}
507  	    };
508  	
509  	#if __cplusplus >= 201103L
510  	  template<typename _Category>
511  	    struct __copy_move_backward<true, false, _Category>
512  	    {
513  	      template<typename _BI1, typename _BI2>
514  	        static _BI2
515  	        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
516  	        {
517  		  while (__first != __last)
518  		    *--__result = std::move(*--__last);
519  		  return __result;
520  		}
521  	    };
522  	#endif
523  	
524  	  template<>
525  	    struct __copy_move_backward<false, false, random_access_iterator_tag>
526  	    {
527  	      template<typename _BI1, typename _BI2>
528  	        static _BI2
529  	        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
530  	        {
531  		  typename iterator_traits<_BI1>::difference_type __n;
532  		  for (__n = __last - __first; __n > 0; --__n)
533  		    *--__result = *--__last;
534  		  return __result;
535  		}
536  	    };
537  	
538  	#if __cplusplus >= 201103L
539  	  template<>
540  	    struct __copy_move_backward<true, false, random_access_iterator_tag>
541  	    {
542  	      template<typename _BI1, typename _BI2>
543  	        static _BI2
544  	        __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
545  	        {
546  		  typename iterator_traits<_BI1>::difference_type __n;
547  		  for (__n = __last - __first; __n > 0; --__n)
548  		    *--__result = std::move(*--__last);
549  		  return __result;
550  		}
551  	    };
552  	#endif
553  	
554  	  template<bool _IsMove>
555  	    struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
556  	    {
557  	      template<typename _Tp>
558  	        static _Tp*
559  	        __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
560  	        {
561  	#if __cplusplus >= 201103L
562  		  using __assignable = conditional<_IsMove,
563  						   is_move_assignable<_Tp>,
564  						   is_copy_assignable<_Tp>>;
565  		  // trivial types can have deleted assignment
566  		  static_assert( __assignable::type::value, "type is not assignable" );
567  	#endif
568  		  const ptrdiff_t _Num = __last - __first;
569  		  if (_Num)
570  		    __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
571  		  return __result - _Num;
572  		}
573  	    };
574  	
575  	  template<bool _IsMove, typename _BI1, typename _BI2>
576  	    inline _BI2
577  	    __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
578  	    {
579  	      typedef typename iterator_traits<_BI1>::value_type _ValueType1;
580  	      typedef typename iterator_traits<_BI2>::value_type _ValueType2;
581  	      typedef typename iterator_traits<_BI1>::iterator_category _Category;
582  	      const bool __simple = (__is_trivial(_ValueType1)
583  		                     && __is_pointer<_BI1>::__value
584  		                     && __is_pointer<_BI2>::__value
585  				     && __are_same<_ValueType1, _ValueType2>::__value);
586  	
587  	      return std::__copy_move_backward<_IsMove, __simple,
588  		                               _Category>::__copy_move_b(__first,
589  									 __last,
590  									 __result);
591  	    }
592  	
593  	  template<bool _IsMove, typename _BI1, typename _BI2>
594  	    inline _BI2
595  	    __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
596  	    {
597  	      return _BI2(std::__copy_move_backward_a<_IsMove>
598  			  (std::__niter_base(__first), std::__niter_base(__last),
599  			   std::__niter_base(__result)));
600  	    }
601  	
602  	  /**
603  	   *  @brief Copies the range [first,last) into result.
604  	   *  @ingroup mutating_algorithms
605  	   *  @param  __first  A bidirectional iterator.
606  	   *  @param  __last   A bidirectional iterator.
607  	   *  @param  __result A bidirectional iterator.
608  	   *  @return   result - (first - last)
609  	   *
610  	   *  The function has the same effect as copy, but starts at the end of the
611  	   *  range and works its way to the start, returning the start of the result.
612  	   *  This inline function will boil down to a call to @c memmove whenever
613  	   *  possible.  Failing that, if random access iterators are passed, then the
614  	   *  loop count will be known (and therefore a candidate for compiler
615  	   *  optimizations such as unrolling).
616  	   *
617  	   *  Result may not be in the range (first,last].  Use copy instead.  Note
618  	   *  that the start of the output range may overlap [first,last).
619  	  */
620  	  template<typename _BI1, typename _BI2>
621  	    inline _BI2
622  	    copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
623  	    {
624  	      // concept requirements
625  	      __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
626  	      __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
627  	      __glibcxx_function_requires(_ConvertibleConcept<
628  		    typename iterator_traits<_BI1>::value_type,
629  		    typename iterator_traits<_BI2>::value_type>)
630  	      __glibcxx_requires_valid_range(__first, __last);
631  	
632  	      return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
633  		      (std::__miter_base(__first), std::__miter_base(__last),
634  		       __result));
635  	    }
636  	
637  	#if __cplusplus >= 201103L
638  	  /**
639  	   *  @brief Moves the range [first,last) into result.
640  	   *  @ingroup mutating_algorithms
641  	   *  @param  __first  A bidirectional iterator.
642  	   *  @param  __last   A bidirectional iterator.
643  	   *  @param  __result A bidirectional iterator.
644  	   *  @return   result - (first - last)
645  	   *
646  	   *  The function has the same effect as move, but starts at the end of the
647  	   *  range and works its way to the start, returning the start of the result.
648  	   *  This inline function will boil down to a call to @c memmove whenever
649  	   *  possible.  Failing that, if random access iterators are passed, then the
650  	   *  loop count will be known (and therefore a candidate for compiler
651  	   *  optimizations such as unrolling).
652  	   *
653  	   *  Result may not be in the range (first,last].  Use move instead.  Note
654  	   *  that the start of the output range may overlap [first,last).
655  	  */
656  	  template<typename _BI1, typename _BI2>
657  	    inline _BI2
658  	    move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
659  	    {
660  	      // concept requirements
661  	      __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
662  	      __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
663  	      __glibcxx_function_requires(_ConvertibleConcept<
664  		    typename iterator_traits<_BI1>::value_type,
665  		    typename iterator_traits<_BI2>::value_type>)
666  	      __glibcxx_requires_valid_range(__first, __last);
667  	
668  	      return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
669  							std::__miter_base(__last),
670  							__result);
671  	    }
672  	
673  	#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
674  	#else
675  	#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
676  	#endif
677  	
678  	  template<typename _ForwardIterator, typename _Tp>
679  	    inline typename
680  	    __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
681  	    __fill_a(_ForwardIterator __first, _ForwardIterator __last,
682  	 	     const _Tp& __value)
683  	    {
684  	      for (; __first != __last; ++__first)
685  		*__first = __value;
686  	    }
687  	    
688  	  template<typename _ForwardIterator, typename _Tp>
689  	    inline typename
690  	    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
691  	    __fill_a(_ForwardIterator __first, _ForwardIterator __last,
692  		     const _Tp& __value)
693  	    {
694  	      const _Tp __tmp = __value;
695  	      for (; __first != __last; ++__first)
696  		*__first = __tmp;
697  	    }
698  	
699  	  // Specialization: for char types we can use memset.
700  	  template<typename _Tp>
701  	    inline typename
702  	    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
703  	    __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
704  	    {
705  	      const _Tp __tmp = __c;
706  	      if (const size_t __len = __last - __first)
707  		__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
708  	    }
709  	
710  	  /**
711  	   *  @brief Fills the range [first,last) with copies of value.
712  	   *  @ingroup mutating_algorithms
713  	   *  @param  __first  A forward iterator.
714  	   *  @param  __last   A forward iterator.
715  	   *  @param  __value  A reference-to-const of arbitrary type.
716  	   *  @return   Nothing.
717  	   *
718  	   *  This function fills a range with copies of the same value.  For char
719  	   *  types filling contiguous areas of memory, this becomes an inline call
720  	   *  to @c memset or @c wmemset.
721  	  */
722  	  template<typename _ForwardIterator, typename _Tp>
723  	    inline void
724  	    fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
725  	    {
726  	      // concept requirements
727  	      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
728  					  _ForwardIterator>)
729  	      __glibcxx_requires_valid_range(__first, __last);
730  	
731  	      std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
732  			    __value);
733  	    }
734  	
735  	  template<typename _OutputIterator, typename _Size, typename _Tp>
736  	    inline typename
737  	    __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
738  	    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
739  	    {
740  	      for (__decltype(__n + 0) __niter = __n;
741  		   __niter > 0; --__niter, ++__first)
742  		*__first = __value;
743  	      return __first;
744  	    }
745  	
746  	  template<typename _OutputIterator, typename _Size, typename _Tp>
747  	    inline typename
748  	    __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
749  	    __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
750  	    {
751  	      const _Tp __tmp = __value;
752  	      for (__decltype(__n + 0) __niter = __n;
753  		   __niter > 0; --__niter, ++__first)
754  		*__first = __tmp;
755  	      return __first;
756  	    }
757  	
758  	  template<typename _Size, typename _Tp>
759  	    inline typename
760  	    __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
761  	    __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
762  	    {
763  	      std::__fill_a(__first, __first + __n, __c);
764  	      return __first + __n;
765  	    }
766  	
767  	  /**
768  	   *  @brief Fills the range [first,first+n) with copies of value.
769  	   *  @ingroup mutating_algorithms
770  	   *  @param  __first  An output iterator.
771  	   *  @param  __n      The count of copies to perform.
772  	   *  @param  __value  A reference-to-const of arbitrary type.
773  	   *  @return   The iterator at first+n.
774  	   *
775  	   *  This function fills a range with copies of the same value.  For char
776  	   *  types filling contiguous areas of memory, this becomes an inline call
777  	   *  to @c memset or @ wmemset.
778  	   *
779  	   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
780  	   *  DR 865. More algorithms that throw away information
781  	  */
782  	  template<typename _OI, typename _Size, typename _Tp>
783  	    inline _OI
784  	    fill_n(_OI __first, _Size __n, const _Tp& __value)
785  	    {
786  	      // concept requirements
787  	      __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
788  	
789  	      return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
790  	    }
791  	
792  	  template<bool _BoolType>
793  	    struct __equal
794  	    {
795  	      template<typename _II1, typename _II2>
796  	        static bool
797  	        equal(_II1 __first1, _II1 __last1, _II2 __first2)
798  	        {
799  		  for (; __first1 != __last1; ++__first1, (void)++__first2)
800  		    if (!(*__first1 == *__first2))
801  		      return false;
802  		  return true;
803  		}
804  	    };
805  	
806  	  template<>
807  	    struct __equal<true>
808  	    {
809  	      template<typename _Tp>
810  	        static bool
811  	        equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
812  	        {
813  		  if (const size_t __len = (__last1 - __first1))
814  		    return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len);
815  		  return true;
816  		}
817  	    };
818  	
819  	  template<typename _II1, typename _II2>
820  	    inline bool
821  	    __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
822  	    {
823  	      typedef typename iterator_traits<_II1>::value_type _ValueType1;
824  	      typedef typename iterator_traits<_II2>::value_type _ValueType2;
825  	      const bool __simple = ((__is_integer<_ValueType1>::__value
826  				      || __is_pointer<_ValueType1>::__value)
827  		                     && __is_pointer<_II1>::__value
828  		                     && __is_pointer<_II2>::__value
829  				     && __are_same<_ValueType1, _ValueType2>::__value);
830  	
831  	      return std::__equal<__simple>::equal(__first1, __last1, __first2);
832  	    }
833  	
834  	  template<typename, typename>
835  	    struct __lc_rai
836  	    {
837  	      template<typename _II1, typename _II2>
838  	        static _II1
839  	        __newlast1(_II1, _II1 __last1, _II2, _II2)
840  	        { return __last1; }
841  	
842  	      template<typename _II>
843  	        static bool
844  	        __cnd2(_II __first, _II __last)
845  	        { return __first != __last; }
846  	    };
847  	
848  	  template<>
849  	    struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
850  	    {
851  	      template<typename _RAI1, typename _RAI2>
852  	        static _RAI1
853  	        __newlast1(_RAI1 __first1, _RAI1 __last1,
854  			   _RAI2 __first2, _RAI2 __last2)
855  	        {
856  		  const typename iterator_traits<_RAI1>::difference_type
857  		    __diff1 = __last1 - __first1;
858  		  const typename iterator_traits<_RAI2>::difference_type
859  		    __diff2 = __last2 - __first2;
860  		  return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
861  		}
862  	
863  	      template<typename _RAI>
864  	        static bool
865  	        __cnd2(_RAI, _RAI)
866  	        { return true; }
867  	    };
868  	
869  	  template<typename _II1, typename _II2, typename _Compare>
870  	    bool
871  	    __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
872  					   _II2 __first2, _II2 __last2,
873  					   _Compare __comp)
874  	    {
875  	      typedef typename iterator_traits<_II1>::iterator_category _Category1;
876  	      typedef typename iterator_traits<_II2>::iterator_category _Category2;
877  	      typedef std::__lc_rai<_Category1, _Category2> __rai_type;
878  	
879  	      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
880  	      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
881  		   ++__first1, (void)++__first2)
882  		{
883  		  if (__comp(__first1, __first2))
884  		    return true;
885  		  if (__comp(__first2, __first1))
886  		    return false;
887  		}
888  	      return __first1 == __last1 && __first2 != __last2;
889  	    }
890  	
891  	  template<bool _BoolType>
892  	    struct __lexicographical_compare
893  	    {
894  	      template<typename _II1, typename _II2>
895  	        static bool __lc(_II1, _II1, _II2, _II2);
896  	    };
897  	
898  	  template<bool _BoolType>
899  	    template<typename _II1, typename _II2>
900  	      bool
901  	      __lexicographical_compare<_BoolType>::
902  	      __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
903  	      {
904  		return std::__lexicographical_compare_impl(__first1, __last1,
905  							   __first2, __last2,
906  						__gnu_cxx::__ops::__iter_less_iter());
907  	      }
908  	
909  	  template<>
910  	    struct __lexicographical_compare<true>
911  	    {
912  	      template<typename _Tp, typename _Up>
913  	        static bool
914  	        __lc(const _Tp* __first1, const _Tp* __last1,
915  		     const _Up* __first2, const _Up* __last2)
916  		{
917  		  const size_t __len1 = __last1 - __first1;
918  		  const size_t __len2 = __last2 - __first2;
919  		  if (const size_t __len = std::min(__len1, __len2))
920  		    if (int __result = __builtin_memcmp(__first1, __first2, __len))
921  		      return __result < 0;
922  		  return __len1 < __len2;
923  		}
924  	    };
925  	
926  	  template<typename _II1, typename _II2>
927  	    inline bool
928  	    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
929  					  _II2 __first2, _II2 __last2)
930  	    {
931  	      typedef typename iterator_traits<_II1>::value_type _ValueType1;
932  	      typedef typename iterator_traits<_II2>::value_type _ValueType2;
933  	      const bool __simple =
934  		(__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
935  		 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
936  		 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
937  		 && __is_pointer<_II1>::__value
938  		 && __is_pointer<_II2>::__value);
939  	
940  	      return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
941  								    __first2, __last2);
942  	    }
943  	
944  	  template<typename _ForwardIterator, typename _Tp, typename _Compare>
945  	    _ForwardIterator
946  	    __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
947  			  const _Tp& __val, _Compare __comp)
948  	    {
949  	      typedef typename iterator_traits<_ForwardIterator>::difference_type
950  		_DistanceType;
951  	
952  	      _DistanceType __len = std::distance(__first, __last);
953  	
954  	      while (__len > 0)
955  		{
956  		  _DistanceType __half = __len >> 1;
957  		  _ForwardIterator __middle = __first;
958  		  std::advance(__middle, __half);
959  		  if (__comp(__middle, __val))
960  		    {
961  		      __first = __middle;
962  		      ++__first;
963  		      __len = __len - __half - 1;
964  		    }
965  		  else
966  		    __len = __half;
967  		}
968  	      return __first;
969  	    }
970  	
971  	  /**
972  	   *  @brief Finds the first position in which @a val could be inserted
973  	   *         without changing the ordering.
974  	   *  @param  __first   An iterator.
975  	   *  @param  __last    Another iterator.
976  	   *  @param  __val     The search term.
977  	   *  @return         An iterator pointing to the first element <em>not less
978  	   *                  than</em> @a val, or end() if every element is less than 
979  	   *                  @a val.
980  	   *  @ingroup binary_search_algorithms
981  	  */
982  	  template<typename _ForwardIterator, typename _Tp>
983  	    inline _ForwardIterator
984  	    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
985  			const _Tp& __val)
986  	    {
987  	      // concept requirements
988  	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
989  	      __glibcxx_function_requires(_LessThanOpConcept<
990  		    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
991  	      __glibcxx_requires_partitioned_lower(__first, __last, __val);
992  	
993  	      return std::__lower_bound(__first, __last, __val,
994  					__gnu_cxx::__ops::__iter_less_val());
995  	    }
996  	
997  	  /// This is a helper function for the sort routines and for random.tcc.
998  	  //  Precondition: __n > 0.
999  	  inline _GLIBCXX_CONSTEXPR int
1000 	  __lg(int __n)
1001 	  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
1002 	
1003 	  inline _GLIBCXX_CONSTEXPR unsigned
1004 	  __lg(unsigned __n)
1005 	  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }
1006 	
1007 	  inline _GLIBCXX_CONSTEXPR long
1008 	  __lg(long __n)
1009 	  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1010 	
1011 	  inline _GLIBCXX_CONSTEXPR unsigned long
1012 	  __lg(unsigned long __n)
1013 	  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1014 	
1015 	  inline _GLIBCXX_CONSTEXPR long long
1016 	  __lg(long long __n)
1017 	  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1018 	
1019 	  inline _GLIBCXX_CONSTEXPR unsigned long long
1020 	  __lg(unsigned long long __n)
1021 	  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1022 	
1023 	_GLIBCXX_END_NAMESPACE_VERSION
1024 	
1025 	_GLIBCXX_BEGIN_NAMESPACE_ALGO
1026 	
1027 	  /**
1028 	   *  @brief Tests a range for element-wise equality.
1029 	   *  @ingroup non_mutating_algorithms
1030 	   *  @param  __first1  An input iterator.
1031 	   *  @param  __last1   An input iterator.
1032 	   *  @param  __first2  An input iterator.
1033 	   *  @return   A boolean true or false.
1034 	   *
1035 	   *  This compares the elements of two ranges using @c == and returns true or
1036 	   *  false depending on whether all of the corresponding elements of the
1037 	   *  ranges are equal.
1038 	  */
1039 	  template<typename _II1, typename _II2>
1040 	    inline bool
1041 	    equal(_II1 __first1, _II1 __last1, _II2 __first2)
1042 	    {
1043 	      // concept requirements
1044 	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1045 	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1046 	      __glibcxx_function_requires(_EqualOpConcept<
1047 		    typename iterator_traits<_II1>::value_type,
1048 		    typename iterator_traits<_II2>::value_type>)
1049 	      __glibcxx_requires_valid_range(__first1, __last1);
1050 	
1051 	      return std::__equal_aux(std::__niter_base(__first1),
1052 				      std::__niter_base(__last1),
1053 				      std::__niter_base(__first2));
1054 	    }
1055 	
1056 	  /**
1057 	   *  @brief Tests a range for element-wise equality.
1058 	   *  @ingroup non_mutating_algorithms
1059 	   *  @param  __first1  An input iterator.
1060 	   *  @param  __last1   An input iterator.
1061 	   *  @param  __first2  An input iterator.
1062 	   *  @param __binary_pred A binary predicate @link functors
1063 	   *                  functor@endlink.
1064 	   *  @return         A boolean true or false.
1065 	   *
1066 	   *  This compares the elements of two ranges using the binary_pred
1067 	   *  parameter, and returns true or
1068 	   *  false depending on whether all of the corresponding elements of the
1069 	   *  ranges are equal.
1070 	  */
1071 	  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1072 	    inline bool
1073 	    equal(_IIter1 __first1, _IIter1 __last1,
1074 		  _IIter2 __first2, _BinaryPredicate __binary_pred)
1075 	    {
1076 	      // concept requirements
1077 	      __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1078 	      __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1079 	      __glibcxx_requires_valid_range(__first1, __last1);
1080 	
1081 	      for (; __first1 != __last1; ++__first1, (void)++__first2)
1082 		if (!bool(__binary_pred(*__first1, *__first2)))
1083 		  return false;
1084 	      return true;
1085 	    }
1086 	
1087 	#if __cplusplus > 201103L
1088 	
1089 	#define __cpp_lib_robust_nonmodifying_seq_ops 201304
1090 	
1091 	  /**
1092 	   *  @brief Tests a range for element-wise equality.
1093 	   *  @ingroup non_mutating_algorithms
1094 	   *  @param  __first1  An input iterator.
1095 	   *  @param  __last1   An input iterator.
1096 	   *  @param  __first2  An input iterator.
1097 	   *  @param  __last2   An input iterator.
1098 	   *  @return   A boolean true or false.
1099 	   *
1100 	   *  This compares the elements of two ranges using @c == and returns true or
1101 	   *  false depending on whether all of the corresponding elements of the
1102 	   *  ranges are equal.
1103 	  */
1104 	  template<typename _II1, typename _II2>
1105 	    inline bool
1106 	    equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1107 	    {
1108 	      // concept requirements
1109 	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1110 	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1111 	      __glibcxx_function_requires(_EqualOpConcept<
1112 		    typename iterator_traits<_II1>::value_type,
1113 		    typename iterator_traits<_II2>::value_type>)
1114 	      __glibcxx_requires_valid_range(__first1, __last1);
1115 	      __glibcxx_requires_valid_range(__first2, __last2);
1116 	
1117 	      using _RATag = random_access_iterator_tag;
1118 	      using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1119 	      using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1120 	      using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1121 	      if (_RAIters())
1122 		{
1123 		  auto __d1 = std::distance(__first1, __last1);
1124 		  auto __d2 = std::distance(__first2, __last2);
1125 		  if (__d1 != __d2)
1126 		    return false;
1127 		  return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1128 		}
1129 	
1130 	      for (; __first1 != __last1 && __first2 != __last2;
1131 		  ++__first1, (void)++__first2)
1132 		if (!(*__first1 == *__first2))
1133 		  return false;
1134 	      return __first1 == __last1 && __first2 == __last2;
1135 	    }
1136 	
1137 	  /**
1138 	   *  @brief Tests a range for element-wise equality.
1139 	   *  @ingroup non_mutating_algorithms
1140 	   *  @param  __first1  An input iterator.
1141 	   *  @param  __last1   An input iterator.
1142 	   *  @param  __first2  An input iterator.
1143 	   *  @param  __last2   An input iterator.
1144 	   *  @param __binary_pred A binary predicate @link functors
1145 	   *                  functor@endlink.
1146 	   *  @return         A boolean true or false.
1147 	   *
1148 	   *  This compares the elements of two ranges using the binary_pred
1149 	   *  parameter, and returns true or
1150 	   *  false depending on whether all of the corresponding elements of the
1151 	   *  ranges are equal.
1152 	  */
1153 	  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1154 	    inline bool
1155 	    equal(_IIter1 __first1, _IIter1 __last1,
1156 		  _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1157 	    {
1158 	      // concept requirements
1159 	      __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1160 	      __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1161 	      __glibcxx_requires_valid_range(__first1, __last1);
1162 	      __glibcxx_requires_valid_range(__first2, __last2);
1163 	
1164 	      using _RATag = random_access_iterator_tag;
1165 	      using _Cat1 = typename iterator_traits<_IIter1>::iterator_category;
1166 	      using _Cat2 = typename iterator_traits<_IIter2>::iterator_category;
1167 	      using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1168 	      if (_RAIters())
1169 		{
1170 		  auto __d1 = std::distance(__first1, __last1);
1171 		  auto __d2 = std::distance(__first2, __last2);
1172 		  if (__d1 != __d2)
1173 		    return false;
1174 		  return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1175 					       __binary_pred);
1176 		}
1177 	
1178 	      for (; __first1 != __last1 && __first2 != __last2;
1179 		  ++__first1, (void)++__first2)
1180 		if (!bool(__binary_pred(*__first1, *__first2)))
1181 		  return false;
1182 	      return __first1 == __last1 && __first2 == __last2;
1183 	    }
1184 	#endif
1185 	
1186 	  /**
1187 	   *  @brief Performs @b dictionary comparison on ranges.
1188 	   *  @ingroup sorting_algorithms
1189 	   *  @param  __first1  An input iterator.
1190 	   *  @param  __last1   An input iterator.
1191 	   *  @param  __first2  An input iterator.
1192 	   *  @param  __last2   An input iterator.
1193 	   *  @return   A boolean true or false.
1194 	   *
1195 	   *  <em>Returns true if the sequence of elements defined by the range
1196 	   *  [first1,last1) is lexicographically less than the sequence of elements
1197 	   *  defined by the range [first2,last2).  Returns false otherwise.</em>
1198 	   *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
1199 	   *  then this is an inline call to @c memcmp.
1200 	  */
1201 	  template<typename _II1, typename _II2>
1202 	    inline bool
1203 	    lexicographical_compare(_II1 __first1, _II1 __last1,
1204 				    _II2 __first2, _II2 __last2)
1205 	    {
1206 	#ifdef _GLIBCXX_CONCEPT_CHECKS
1207 	      // concept requirements
1208 	      typedef typename iterator_traits<_II1>::value_type _ValueType1;
1209 	      typedef typename iterator_traits<_II2>::value_type _ValueType2;
1210 	#endif
1211 	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1212 	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1213 	      __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1214 	      __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1215 	      __glibcxx_requires_valid_range(__first1, __last1);
1216 	      __glibcxx_requires_valid_range(__first2, __last2);
1217 	
1218 	      return std::__lexicographical_compare_aux(std::__niter_base(__first1),
1219 							std::__niter_base(__last1),
1220 							std::__niter_base(__first2),
1221 							std::__niter_base(__last2));
1222 	    }
1223 	
1224 	  /**
1225 	   *  @brief Performs @b dictionary comparison on ranges.
1226 	   *  @ingroup sorting_algorithms
1227 	   *  @param  __first1  An input iterator.
1228 	   *  @param  __last1   An input iterator.
1229 	   *  @param  __first2  An input iterator.
1230 	   *  @param  __last2   An input iterator.
1231 	   *  @param  __comp  A @link comparison_functors comparison functor@endlink.
1232 	   *  @return   A boolean true or false.
1233 	   *
1234 	   *  The same as the four-parameter @c lexicographical_compare, but uses the
1235 	   *  comp parameter instead of @c <.
1236 	  */
1237 	  template<typename _II1, typename _II2, typename _Compare>
1238 	    inline bool
1239 	    lexicographical_compare(_II1 __first1, _II1 __last1,
1240 				    _II2 __first2, _II2 __last2, _Compare __comp)
1241 	    {
1242 	      // concept requirements
1243 	      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1244 	      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1245 	      __glibcxx_requires_valid_range(__first1, __last1);
1246 	      __glibcxx_requires_valid_range(__first2, __last2);
1247 	
1248 	      return std::__lexicographical_compare_impl
1249 		(__first1, __last1, __first2, __last2,
1250 		 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1251 	    }
1252 	
1253 	  template<typename _InputIterator1, typename _InputIterator2,
1254 		   typename _BinaryPredicate>
1255 	    pair<_InputIterator1, _InputIterator2>
1256 	    __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1257 		       _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1258 	    {
1259 	      while (__first1 != __last1 && __binary_pred(__first1, __first2))
1260 	        {
1261 		  ++__first1;
1262 		  ++__first2;
1263 	        }
1264 	      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1265 	    }
1266 	
1267 	  /**
1268 	   *  @brief Finds the places in ranges which don't match.
1269 	   *  @ingroup non_mutating_algorithms
1270 	   *  @param  __first1  An input iterator.
1271 	   *  @param  __last1   An input iterator.
1272 	   *  @param  __first2  An input iterator.
1273 	   *  @return   A pair of iterators pointing to the first mismatch.
1274 	   *
1275 	   *  This compares the elements of two ranges using @c == and returns a pair
1276 	   *  of iterators.  The first iterator points into the first range, the
1277 	   *  second iterator points into the second range, and the elements pointed
1278 	   *  to by the iterators are not equal.
1279 	  */
1280 	  template<typename _InputIterator1, typename _InputIterator2>
1281 	    inline pair<_InputIterator1, _InputIterator2>
1282 	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1283 		     _InputIterator2 __first2)
1284 	    {
1285 	      // concept requirements
1286 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1287 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1288 	      __glibcxx_function_requires(_EqualOpConcept<
1289 		    typename iterator_traits<_InputIterator1>::value_type,
1290 		    typename iterator_traits<_InputIterator2>::value_type>)
1291 	      __glibcxx_requires_valid_range(__first1, __last1);
1292 	
1293 	      return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1294 				     __gnu_cxx::__ops::__iter_equal_to_iter());
1295 	    }
1296 	
1297 	  /**
1298 	   *  @brief Finds the places in ranges which don't match.
1299 	   *  @ingroup non_mutating_algorithms
1300 	   *  @param  __first1  An input iterator.
1301 	   *  @param  __last1   An input iterator.
1302 	   *  @param  __first2  An input iterator.
1303 	   *  @param __binary_pred A binary predicate @link functors
1304 	   *         functor@endlink.
1305 	   *  @return   A pair of iterators pointing to the first mismatch.
1306 	   *
1307 	   *  This compares the elements of two ranges using the binary_pred
1308 	   *  parameter, and returns a pair
1309 	   *  of iterators.  The first iterator points into the first range, the
1310 	   *  second iterator points into the second range, and the elements pointed
1311 	   *  to by the iterators are not equal.
1312 	  */
1313 	  template<typename _InputIterator1, typename _InputIterator2,
1314 		   typename _BinaryPredicate>
1315 	    inline pair<_InputIterator1, _InputIterator2>
1316 	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1317 		     _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1318 	    {
1319 	      // concept requirements
1320 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1321 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1322 	      __glibcxx_requires_valid_range(__first1, __last1);
1323 	
1324 	      return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1325 		__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1326 	    }
1327 	
1328 	#if __cplusplus > 201103L
1329 	
1330 	  template<typename _InputIterator1, typename _InputIterator2,
1331 		   typename _BinaryPredicate>
1332 	    pair<_InputIterator1, _InputIterator2>
1333 	    __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1334 		       _InputIterator2 __first2, _InputIterator2 __last2,
1335 		       _BinaryPredicate __binary_pred)
1336 	    {
1337 	      while (__first1 != __last1 && __first2 != __last2
1338 		     && __binary_pred(__first1, __first2))
1339 	        {
1340 		  ++__first1;
1341 		  ++__first2;
1342 	        }
1343 	      return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1344 	    }
1345 	
1346 	  /**
1347 	   *  @brief Finds the places in ranges which don't match.
1348 	   *  @ingroup non_mutating_algorithms
1349 	   *  @param  __first1  An input iterator.
1350 	   *  @param  __last1   An input iterator.
1351 	   *  @param  __first2  An input iterator.
1352 	   *  @param  __last2   An input iterator.
1353 	   *  @return   A pair of iterators pointing to the first mismatch.
1354 	   *
1355 	   *  This compares the elements of two ranges using @c == and returns a pair
1356 	   *  of iterators.  The first iterator points into the first range, the
1357 	   *  second iterator points into the second range, and the elements pointed
1358 	   *  to by the iterators are not equal.
1359 	  */
1360 	  template<typename _InputIterator1, typename _InputIterator2>
1361 	    inline pair<_InputIterator1, _InputIterator2>
1362 	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1363 		     _InputIterator2 __first2, _InputIterator2 __last2)
1364 	    {
1365 	      // concept requirements
1366 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1367 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1368 	      __glibcxx_function_requires(_EqualOpConcept<
1369 		    typename iterator_traits<_InputIterator1>::value_type,
1370 		    typename iterator_traits<_InputIterator2>::value_type>)
1371 	      __glibcxx_requires_valid_range(__first1, __last1);
1372 	      __glibcxx_requires_valid_range(__first2, __last2);
1373 	
1374 	      return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
1375 				     __gnu_cxx::__ops::__iter_equal_to_iter());
1376 	    }
1377 	
1378 	  /**
1379 	   *  @brief Finds the places in ranges which don't match.
1380 	   *  @ingroup non_mutating_algorithms
1381 	   *  @param  __first1  An input iterator.
1382 	   *  @param  __last1   An input iterator.
1383 	   *  @param  __first2  An input iterator.
1384 	   *  @param  __last2   An input iterator.
1385 	   *  @param __binary_pred A binary predicate @link functors
1386 	   *         functor@endlink.
1387 	   *  @return   A pair of iterators pointing to the first mismatch.
1388 	   *
1389 	   *  This compares the elements of two ranges using the binary_pred
1390 	   *  parameter, and returns a pair
1391 	   *  of iterators.  The first iterator points into the first range, the
1392 	   *  second iterator points into the second range, and the elements pointed
1393 	   *  to by the iterators are not equal.
1394 	  */
1395 	  template<typename _InputIterator1, typename _InputIterator2,
1396 		   typename _BinaryPredicate>
1397 	    inline pair<_InputIterator1, _InputIterator2>
1398 	    mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1399 		     _InputIterator2 __first2, _InputIterator2 __last2,
1400 		     _BinaryPredicate __binary_pred)
1401 	    {
1402 	      // concept requirements
1403 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1404 	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1405 	      __glibcxx_requires_valid_range(__first1, __last1);
1406 	      __glibcxx_requires_valid_range(__first2, __last2);
1407 	
1408 	      return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
1409 				     __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1410 	    }
1411 	#endif
1412 	
1413 	_GLIBCXX_END_NAMESPACE_ALGO
1414 	} // namespace std
1415 	
1416 	// NB: This file is included within many other C++ includes, as a way
1417 	// of getting the base algorithms. So, make sure that parallel bits
1418 	// come in too if requested. 
1419 	#ifdef _GLIBCXX_PARALLEL
1420 	# include <parallel/algobase.h>
1421 	#endif
1422 	
1423 	#endif
1424