File Coverage

/usr/include/c++/5/bits/stl_algobase.h
Criterion Covered Total %
statement 24 24 100.0
branch 7 8 87.5
condition n/a
subroutine n/a
pod n/a
total 31 32 96.8


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