Clang Project

include/c++/7/bits/stl_algobase.h
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
73namespace 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
std::__copy_move::__copy_m
std::__copy_move::__copy_m
std::__copy_move::__copy_m
std::__copy_move::__copy_m
std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m
std::__copy_move_backward::__copy_move_b
std::__copy_move_backward::__copy_move_b
std::__copy_move_backward::__copy_move_b
std::__copy_move_backward::__copy_move_b
std::__copy_move_backward<_IsMove, true, std::random_access_iterator_tag>::__copy_move_b
std::__equal::equal
std::__equal::equal
std::__lc_rai::__newlast1
std::__lc_rai::__cnd2
std::__lc_rai::__newlast1
std::__lc_rai::__cnd2
std::__lexicographical_compare::__lc
std::__lexicographical_compare::__lc
std::__lexicographical_compare::__lc
CodeThinker, Enjoy your reading code