1 // Core algorithmic facilities -*- C++ -*-
3 // Copyright (C) 2001-2019 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
56 #ifndef _STL_ALGOBASE_H
57 #define _STL_ALGOBASE_H 1
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
71 #include <bits/predefined_ops.h>
72 #if __cplusplus >= 201103L
73 # include <type_traits>
76 namespace std
_GLIBCXX_VISIBILITY(default)
78 _GLIBCXX_BEGIN_NAMESPACE_VERSION
80 #if __cplusplus < 201103L
81 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
82 // nutshell, we are partially implementing the resolution of DR 187,
83 // when it's safe, i.e., the value_types are equal.
84 template<bool _BoolType
>
87 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
89 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
91 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
93 _ValueType1 __tmp
= *__a
;
100 struct __iter_swap
<true>
102 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
104 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
112 * @brief Swaps the contents of two iterators.
113 * @ingroup mutating_algorithms
114 * @param __a An iterator.
115 * @param __b Another iterator.
118 * This function swaps the values pointed to by two iterators, not the
119 * iterators themselves.
121 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
123 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
125 // concept requirements
126 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
128 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
131 #if __cplusplus < 201103L
132 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
134 typedef typename iterator_traits
<_ForwardIterator2
>::value_type
137 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType1
,
139 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType2
,
142 typedef typename iterator_traits
<_ForwardIterator1
>::reference
144 typedef typename iterator_traits
<_ForwardIterator2
>::reference
146 std::__iter_swap
<__are_same
<_ValueType1
, _ValueType2
>::__value
147 && __are_same
<_ValueType1
&, _ReferenceType1
>::__value
148 && __are_same
<_ValueType2
&, _ReferenceType2
>::__value
>::
156 * @brief Swap the elements of two sequences.
157 * @ingroup mutating_algorithms
158 * @param __first1 A forward iterator.
159 * @param __last1 A forward iterator.
160 * @param __first2 A forward iterator.
161 * @return An iterator equal to @p first2+(last1-first1).
163 * Swaps each element in the range @p [first1,last1) with the
164 * corresponding element in the range @p [first2,(last1-first1)).
165 * The ranges must not overlap.
167 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
169 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
170 _ForwardIterator2 __first2
)
172 // concept requirements
173 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
175 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
177 __glibcxx_requires_valid_range(__first1
, __last1
);
179 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
180 std::iter_swap(__first1
, __first2
);
185 * @brief This does what you think it does.
186 * @ingroup sorting_algorithms
187 * @param __a A thing of arbitrary type.
188 * @param __b Another thing of arbitrary type.
189 * @return The lesser of the parameters.
191 * This is the simple classic generic implementation. It will work on
192 * temporary expressions, since they are only evaluated once, unlike a
193 * preprocessor macro.
195 template<typename _Tp
>
198 min(const _Tp
& __a
, const _Tp
& __b
)
200 // concept requirements
201 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
202 //return __b < __a ? __b : __a;
209 * @brief This does what you think it does.
210 * @ingroup sorting_algorithms
211 * @param __a A thing of arbitrary type.
212 * @param __b Another thing of arbitrary type.
213 * @return The greater of the parameters.
215 * This is the simple classic generic implementation. It will work on
216 * temporary expressions, since they are only evaluated once, unlike a
217 * preprocessor macro.
219 template<typename _Tp
>
222 max(const _Tp
& __a
, const _Tp
& __b
)
224 // concept requirements
225 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
226 //return __a < __b ? __b : __a;
233 * @brief This does what you think it does.
234 * @ingroup sorting_algorithms
235 * @param __a A thing of arbitrary type.
236 * @param __b Another thing of arbitrary type.
237 * @param __comp A @link comparison_functors comparison functor@endlink.
238 * @return The lesser of the parameters.
240 * This will work on temporary expressions, since they are only evaluated
241 * once, unlike a preprocessor macro.
243 template<typename _Tp
, typename _Compare
>
246 min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
248 //return __comp(__b, __a) ? __b : __a;
249 if (__comp(__b
, __a
))
255 * @brief This does what you think it does.
256 * @ingroup sorting_algorithms
257 * @param __a A thing of arbitrary type.
258 * @param __b Another thing of arbitrary type.
259 * @param __comp A @link comparison_functors comparison functor@endlink.
260 * @return The greater of the parameters.
262 * This will work on temporary expressions, since they are only evaluated
263 * once, unlike a preprocessor macro.
265 template<typename _Tp
, typename _Compare
>
268 max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
270 //return __comp(__a, __b) ? __b : __a;
271 if (__comp(__a
, __b
))
276 // Fallback implementation of the function in bits/stl_iterator.h used to
277 // remove the __normal_iterator wrapper. See copy, fill, ...
278 template<typename _Iterator
>
280 __niter_base(_Iterator __it
)
281 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible
<_Iterator
>::value
)
284 // Reverse the __niter_base transformation to get a
285 // __normal_iterator back again (this assumes that __normal_iterator
286 // is only used to wrap random access iterators, like pointers).
287 template<typename _From
, typename _To
>
289 __niter_wrap(_From __from
, _To __res
)
290 { return __from
+ (__res
- std::__niter_base(__from
)); }
292 // No need to wrap, iterator already has the right type.
293 template<typename _Iterator
>
295 __niter_wrap(const _Iterator
&, _Iterator __res
)
298 // All of these auxiliary structs serve two purposes. (1) Replace
299 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
300 // because the input and output ranges are permitted to overlap.)
301 // (2) If we're using random access iterators, then write the loop as
302 // a for loop with an explicit count.
304 template<bool, bool, typename
>
307 template<typename _II
, typename _OI
>
309 __copy_m(_II __first
, _II __last
, _OI __result
)
311 for (; __first
!= __last
; ++__result
, (void)++__first
)
312 *__result
= *__first
;
317 #if __cplusplus >= 201103L
318 template<typename _Category
>
319 struct __copy_move
<true, false, _Category
>
321 template<typename _II
, typename _OI
>
323 __copy_m(_II __first
, _II __last
, _OI __result
)
325 for (; __first
!= __last
; ++__result
, (void)++__first
)
326 *__result
= std::move(*__first
);
333 struct __copy_move
<false, false, random_access_iterator_tag
>
335 template<typename _II
, typename _OI
>
337 __copy_m(_II __first
, _II __last
, _OI __result
)
339 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
340 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
342 *__result
= *__first
;
350 #if __cplusplus >= 201103L
352 struct __copy_move
<true, false, random_access_iterator_tag
>
354 template<typename _II
, typename _OI
>
356 __copy_m(_II __first
, _II __last
, _OI __result
)
358 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
359 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
361 *__result
= std::move(*__first
);
370 template<bool _IsMove
>
371 struct __copy_move
<_IsMove
, true, random_access_iterator_tag
>
373 template<typename _Tp
>
375 __copy_m(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
377 #if __cplusplus >= 201103L
378 using __assignable
= conditional
<_IsMove
,
379 is_move_assignable
<_Tp
>,
380 is_copy_assignable
<_Tp
>>;
381 // trivial types can have deleted assignment
382 static_assert( __assignable::type::value
, "type is not assignable" );
384 const ptrdiff_t _Num
= __last
- __first
;
386 __builtin_memmove(__result
, __first
, sizeof(_Tp
) * _Num
);
387 return __result
+ _Num
;
391 template<bool _IsMove
, typename _II
, typename _OI
>
393 __copy_move_a(_II __first
, _II __last
, _OI __result
)
395 typedef typename iterator_traits
<_II
>::value_type _ValueTypeI
;
396 typedef typename iterator_traits
<_OI
>::value_type _ValueTypeO
;
397 typedef typename iterator_traits
<_II
>::iterator_category _Category
;
398 const bool __simple
= (__is_trivially_copyable(_ValueTypeI
)
399 && __is_pointer
<_II
>::__value
400 && __is_pointer
<_OI
>::__value
401 && __are_same
<_ValueTypeI
, _ValueTypeO
>::__value
);
403 return std::__copy_move
<_IsMove
, __simple
,
404 _Category
>::__copy_m(__first
, __last
, __result
);
407 // Helpers for streambuf iterators (either istream or ostream).
408 // NB: avoid including <iosfwd>, relatively large.
409 template<typename _CharT
>
412 template<typename _CharT
, typename _Traits
>
413 class istreambuf_iterator
;
415 template<typename _CharT
, typename _Traits
>
416 class ostreambuf_iterator
;
418 template<bool _IsMove
, typename _CharT
>
419 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
420 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
421 __copy_move_a2(_CharT
*, _CharT
*,
422 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
424 template<bool _IsMove
, typename _CharT
>
425 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
426 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
427 __copy_move_a2(const _CharT
*, const _CharT
*,
428 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
430 template<bool _IsMove
, typename _CharT
>
431 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
433 __copy_move_a2(istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >,
434 istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >, _CharT
*);
436 template<bool _IsMove
, typename _II
, typename _OI
>
438 __copy_move_a2(_II __first
, _II __last
, _OI __result
)
440 return std::__niter_wrap(__result
,
441 std::__copy_move_a
<_IsMove
>(std::__niter_base(__first
),
442 std::__niter_base(__last
),
443 std::__niter_base(__result
)));
447 * @brief Copies the range [first,last) into result.
448 * @ingroup mutating_algorithms
449 * @param __first An input iterator.
450 * @param __last An input iterator.
451 * @param __result An output iterator.
452 * @return result + (first - last)
454 * This inline function will boil down to a call to @c memmove whenever
455 * possible. Failing that, if random access iterators are passed, then the
456 * loop count will be known (and therefore a candidate for compiler
457 * optimizations such as unrolling). Result may not be contained within
458 * [first,last); the copy_backward function should be used instead.
460 * Note that the end of the output range is permitted to be contained
461 * within [first,last).
463 template<typename _II
, typename _OI
>
465 copy(_II __first
, _II __last
, _OI __result
)
467 // concept requirements
468 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
469 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
470 typename iterator_traits
<_II
>::value_type
>)
471 __glibcxx_requires_can_increment_range(__first
, __last
, __result
);
473 return std::__copy_move_a2
<__is_move_iterator
<_II
>::__value
>
474 (std::__miter_base(__first
), std::__miter_base(__last
), __result
);
477 #if __cplusplus >= 201103L
479 * @brief Moves the range [first,last) into result.
480 * @ingroup mutating_algorithms
481 * @param __first An input iterator.
482 * @param __last An input iterator.
483 * @param __result An output iterator.
484 * @return result + (first - last)
486 * This inline function will boil down to a call to @c memmove whenever
487 * possible. Failing that, if random access iterators are passed, then the
488 * loop count will be known (and therefore a candidate for compiler
489 * optimizations such as unrolling). Result may not be contained within
490 * [first,last); the move_backward function should be used instead.
492 * Note that the end of the output range is permitted to be contained
493 * within [first,last).
495 template<typename _II
, typename _OI
>
497 move(_II __first
, _II __last
, _OI __result
)
499 // concept requirements
500 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
501 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
502 typename iterator_traits
<_II
>::value_type
>)
503 __glibcxx_requires_can_increment_range(__first
, __last
, __result
);
505 return std::__copy_move_a2
<true>(std::__miter_base(__first
),
506 std::__miter_base(__last
), __result
);
509 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
511 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
514 template<bool, bool, typename
>
515 struct __copy_move_backward
517 template<typename _BI1
, typename _BI2
>
519 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
521 while (__first
!= __last
)
522 *--__result
= *--__last
;
527 #if __cplusplus >= 201103L
528 template<typename _Category
>
529 struct __copy_move_backward
<true, false, _Category
>
531 template<typename _BI1
, typename _BI2
>
533 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
535 while (__first
!= __last
)
536 *--__result
= std::move(*--__last
);
543 struct __copy_move_backward
<false, false, random_access_iterator_tag
>
545 template<typename _BI1
, typename _BI2
>
547 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
549 typename iterator_traits
<_BI1
>::difference_type __n
;
550 for (__n
= __last
- __first
; __n
> 0; --__n
)
551 *--__result
= *--__last
;
556 #if __cplusplus >= 201103L
558 struct __copy_move_backward
<true, false, random_access_iterator_tag
>
560 template<typename _BI1
, typename _BI2
>
562 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
564 typename iterator_traits
<_BI1
>::difference_type __n
;
565 for (__n
= __last
- __first
; __n
> 0; --__n
)
566 *--__result
= std::move(*--__last
);
572 template<bool _IsMove
>
573 struct __copy_move_backward
<_IsMove
, true, random_access_iterator_tag
>
575 template<typename _Tp
>
577 __copy_move_b(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
579 #if __cplusplus >= 201103L
580 using __assignable
= conditional
<_IsMove
,
581 is_move_assignable
<_Tp
>,
582 is_copy_assignable
<_Tp
>>;
583 // trivial types can have deleted assignment
584 static_assert( __assignable::type::value
, "type is not assignable" );
586 const ptrdiff_t _Num
= __last
- __first
;
588 __builtin_memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
589 return __result
- _Num
;
593 template<bool _IsMove
, typename _BI1
, typename _BI2
>
595 __copy_move_backward_a(_BI1 __first
, _BI1 __last
, _BI2 __result
)
597 typedef typename iterator_traits
<_BI1
>::value_type _ValueType1
;
598 typedef typename iterator_traits
<_BI2
>::value_type _ValueType2
;
599 typedef typename iterator_traits
<_BI1
>::iterator_category _Category
;
600 const bool __simple
= (__is_trivially_copyable(_ValueType1
)
601 && __is_pointer
<_BI1
>::__value
602 && __is_pointer
<_BI2
>::__value
603 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
605 return std::__copy_move_backward
<_IsMove
, __simple
,
606 _Category
>::__copy_move_b(__first
,
611 template<bool _IsMove
, typename _BI1
, typename _BI2
>
613 __copy_move_backward_a2(_BI1 __first
, _BI1 __last
, _BI2 __result
)
615 return std::__niter_wrap(__result
,
616 std::__copy_move_backward_a
<_IsMove
>
617 (std::__niter_base(__first
), std::__niter_base(__last
),
618 std::__niter_base(__result
)));
622 * @brief Copies the range [first,last) into result.
623 * @ingroup mutating_algorithms
624 * @param __first A bidirectional iterator.
625 * @param __last A bidirectional iterator.
626 * @param __result A bidirectional iterator.
627 * @return result - (first - last)
629 * The function has the same effect as copy, but starts at the end of the
630 * range and works its way to the start, returning the start of the result.
631 * This inline function will boil down to a call to @c memmove whenever
632 * possible. Failing that, if random access iterators are passed, then the
633 * loop count will be known (and therefore a candidate for compiler
634 * optimizations such as unrolling).
636 * Result may not be in the range (first,last]. Use copy instead. Note
637 * that the start of the output range may overlap [first,last).
639 template<typename _BI1
, typename _BI2
>
641 copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
643 // concept requirements
644 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
645 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
646 __glibcxx_function_requires(_ConvertibleConcept
<
647 typename iterator_traits
<_BI1
>::value_type
,
648 typename iterator_traits
<_BI2
>::value_type
>)
649 __glibcxx_requires_can_decrement_range(__first
, __last
, __result
);
651 return std::__copy_move_backward_a2
<__is_move_iterator
<_BI1
>::__value
>
652 (std::__miter_base(__first
), std::__miter_base(__last
), __result
);
655 #if __cplusplus >= 201103L
657 * @brief Moves the range [first,last) into result.
658 * @ingroup mutating_algorithms
659 * @param __first A bidirectional iterator.
660 * @param __last A bidirectional iterator.
661 * @param __result A bidirectional iterator.
662 * @return result - (first - last)
664 * The function has the same effect as move, but starts at the end of the
665 * range and works its way to the start, returning the start of the result.
666 * This inline function will boil down to a call to @c memmove whenever
667 * possible. Failing that, if random access iterators are passed, then the
668 * loop count will be known (and therefore a candidate for compiler
669 * optimizations such as unrolling).
671 * Result may not be in the range (first,last]. Use move instead. Note
672 * that the start of the output range may overlap [first,last).
674 template<typename _BI1
, typename _BI2
>
676 move_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
678 // concept requirements
679 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
680 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
681 __glibcxx_function_requires(_ConvertibleConcept
<
682 typename iterator_traits
<_BI1
>::value_type
,
683 typename iterator_traits
<_BI2
>::value_type
>)
684 __glibcxx_requires_can_decrement_range(__first
, __last
, __result
);
686 return std::__copy_move_backward_a2
<true>(std::__miter_base(__first
),
687 std::__miter_base(__last
),
691 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
693 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
696 template<typename _ForwardIterator
, typename _Tp
>
698 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, void>::__type
699 __fill_a(_ForwardIterator __first
, _ForwardIterator __last
,
702 for (; __first
!= __last
; ++__first
)
706 template<typename _ForwardIterator
, typename _Tp
>
708 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, void>::__type
709 __fill_a(_ForwardIterator __first
, _ForwardIterator __last
,
712 const _Tp __tmp
= __value
;
713 for (; __first
!= __last
; ++__first
)
717 // Specialization: for char types we can use memset.
718 template<typename _Tp
>
720 __gnu_cxx::__enable_if
<__is_byte
<_Tp
>::__value
, void>::__type
721 __fill_a(_Tp
* __first
, _Tp
* __last
, const _Tp
& __c
)
723 const _Tp __tmp
= __c
;
724 if (const size_t __len
= __last
- __first
)
725 __builtin_memset(__first
, static_cast<unsigned char>(__tmp
), __len
);
729 * @brief Fills the range [first,last) with copies of value.
730 * @ingroup mutating_algorithms
731 * @param __first A forward iterator.
732 * @param __last A forward iterator.
733 * @param __value A reference-to-const of arbitrary type.
736 * This function fills a range with copies of the same value. For char
737 * types filling contiguous areas of memory, this becomes an inline call
738 * to @c memset or @c wmemset.
740 template<typename _ForwardIterator
, typename _Tp
>
742 fill(_ForwardIterator __first
, _ForwardIterator __last
, const _Tp
& __value
)
744 // concept requirements
745 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
747 __glibcxx_requires_valid_range(__first
, __last
);
749 std::__fill_a(std::__niter_base(__first
), std::__niter_base(__last
),
753 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
755 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
756 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
758 for (__decltype(__n
+ 0) __niter
= __n
;
759 __niter
> 0; --__niter
, (void) ++__first
)
764 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
766 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
767 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
769 const _Tp __tmp
= __value
;
770 for (__decltype(__n
+ 0) __niter
= __n
;
771 __niter
> 0; --__niter
, (void) ++__first
)
776 template<typename _Size
, typename _Tp
>
778 __gnu_cxx::__enable_if
<__is_byte
<_Tp
>::__value
, _Tp
*>::__type
779 __fill_n_a(_Tp
* __first
, _Size __n
, const _Tp
& __c
)
781 std::__fill_a(__first
, __first
+ __n
, __c
);
782 return __first
+ __n
;
786 * @brief Fills the range [first,first+n) with copies of value.
787 * @ingroup mutating_algorithms
788 * @param __first An output iterator.
789 * @param __n The count of copies to perform.
790 * @param __value A reference-to-const of arbitrary type.
791 * @return The iterator at first+n.
793 * This function fills a range with copies of the same value. For char
794 * types filling contiguous areas of memory, this becomes an inline call
795 * to @c memset or @ wmemset.
797 * _GLIBCXX_RESOLVE_LIB_DEFECTS
798 * DR 865. More algorithms that throw away information
800 template<typename _OI
, typename _Size
, typename _Tp
>
802 fill_n(_OI __first
, _Size __n
, const _Tp
& __value
)
804 // concept requirements
805 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
, _Tp
>)
806 __glibcxx_requires_can_increment(__first
, __n
);
808 return std::__niter_wrap(__first
,
809 std::__fill_n_a(std::__niter_base(__first
), __n
, __value
));
812 template<bool _BoolType
>
815 template<typename _II1
, typename _II2
>
817 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
819 for (; __first1
!= __last1
; ++__first1
, (void) ++__first2
)
820 if (!(*__first1
== *__first2
))
829 template<typename _Tp
>
831 equal(const _Tp
* __first1
, const _Tp
* __last1
, const _Tp
* __first2
)
833 if (const size_t __len
= (__last1
- __first1
))
834 return !__builtin_memcmp(__first1
, __first2
, sizeof(_Tp
) * __len
);
839 template<typename _II1
, typename _II2
>
841 __equal_aux(_II1 __first1
, _II1 __last1
, _II2 __first2
)
843 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
844 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
845 const bool __simple
= ((__is_integer
<_ValueType1
>::__value
846 || __is_pointer
<_ValueType1
>::__value
)
847 && __is_pointer
<_II1
>::__value
848 && __is_pointer
<_II2
>::__value
849 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
851 return std::__equal
<__simple
>::equal(__first1
, __last1
, __first2
);
854 template<typename
, typename
>
857 template<typename _II1
, typename _II2
>
859 __newlast1(_II1
, _II1 __last1
, _II2
, _II2
)
862 template<typename _II
>
864 __cnd2(_II __first
, _II __last
)
865 { return __first
!= __last
; }
869 struct __lc_rai
<random_access_iterator_tag
, random_access_iterator_tag
>
871 template<typename _RAI1
, typename _RAI2
>
873 __newlast1(_RAI1 __first1
, _RAI1 __last1
,
874 _RAI2 __first2
, _RAI2 __last2
)
876 const typename iterator_traits
<_RAI1
>::difference_type
877 __diff1
= __last1
- __first1
;
878 const typename iterator_traits
<_RAI2
>::difference_type
879 __diff2
= __last2
- __first2
;
880 return __diff2
< __diff1
? __first1
+ __diff2
: __last1
;
883 template<typename _RAI
>
889 template<typename _II1
, typename _II2
, typename _Compare
>
891 __lexicographical_compare_impl(_II1 __first1
, _II1 __last1
,
892 _II2 __first2
, _II2 __last2
,
895 typedef typename iterator_traits
<_II1
>::iterator_category _Category1
;
896 typedef typename iterator_traits
<_II2
>::iterator_category _Category2
;
897 typedef std::__lc_rai
<_Category1
, _Category2
> __rai_type
;
899 __last1
= __rai_type::__newlast1(__first1
, __last1
, __first2
, __last2
);
900 for (; __first1
!= __last1
&& __rai_type::__cnd2(__first2
, __last2
);
901 ++__first1
, (void)++__first2
)
903 if (__comp(__first1
, __first2
))
905 if (__comp(__first2
, __first1
))
908 return __first1
== __last1
&& __first2
!= __last2
;
911 template<bool _BoolType
>
912 struct __lexicographical_compare
914 template<typename _II1
, typename _II2
>
915 static bool __lc(_II1
, _II1
, _II2
, _II2
);
918 template<bool _BoolType
>
919 template<typename _II1
, typename _II2
>
921 __lexicographical_compare
<_BoolType
>::
922 __lc(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
924 return std::__lexicographical_compare_impl(__first1
, __last1
,
926 __gnu_cxx::__ops::__iter_less_iter());
930 struct __lexicographical_compare
<true>
932 template<typename _Tp
, typename _Up
>
934 __lc(const _Tp
* __first1
, const _Tp
* __last1
,
935 const _Up
* __first2
, const _Up
* __last2
)
937 const size_t __len1
= __last1
- __first1
;
938 const size_t __len2
= __last2
- __first2
;
939 if (const size_t __len
= std::min(__len1
, __len2
))
940 if (int __result
= __builtin_memcmp(__first1
, __first2
, __len
))
942 return __len1
< __len2
;
946 template<typename _II1
, typename _II2
>
948 __lexicographical_compare_aux(_II1 __first1
, _II1 __last1
,
949 _II2 __first2
, _II2 __last2
)
951 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
952 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
953 const bool __simple
=
954 (__is_byte
<_ValueType1
>::__value
&& __is_byte
<_ValueType2
>::__value
955 && !__gnu_cxx::__numeric_traits
<_ValueType1
>::__is_signed
956 && !__gnu_cxx::__numeric_traits
<_ValueType2
>::__is_signed
957 && __is_pointer
<_II1
>::__value
958 && __is_pointer
<_II2
>::__value
);
960 return std::__lexicographical_compare
<__simple
>::__lc(__first1
, __last1
,
964 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
966 __lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
967 const _Tp
& __val
, _Compare __comp
)
969 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
972 _DistanceType __len
= std::distance(__first
, __last
);
976 _DistanceType __half
= __len
>> 1;
977 _ForwardIterator __middle
= __first
;
978 std::advance(__middle
, __half
);
979 if (__comp(__middle
, __val
))
983 __len
= __len
- __half
- 1;
992 * @brief Finds the first position in which @a val could be inserted
993 * without changing the ordering.
994 * @param __first An iterator.
995 * @param __last Another iterator.
996 * @param __val The search term.
997 * @return An iterator pointing to the first element <em>not less
998 * than</em> @a val, or end() if every element is less than
1000 * @ingroup binary_search_algorithms
1002 template<typename _ForwardIterator
, typename _Tp
>
1003 inline _ForwardIterator
1004 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
1007 // concept requirements
1008 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1009 __glibcxx_function_requires(_LessThanOpConcept
<
1010 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1011 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
1013 return std::__lower_bound(__first
, __last
, __val
,
1014 __gnu_cxx::__ops::__iter_less_val());
1017 /// This is a helper function for the sort routines and for random.tcc.
1018 // Precondition: __n > 0.
1019 inline _GLIBCXX_CONSTEXPR
int
1021 { return sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
1023 inline _GLIBCXX_CONSTEXPR
unsigned
1025 { return sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
1027 inline _GLIBCXX_CONSTEXPR
long
1029 { return sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1031 inline _GLIBCXX_CONSTEXPR
unsigned long
1032 __lg(unsigned long __n
)
1033 { return sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1035 inline _GLIBCXX_CONSTEXPR
long long
1037 { return sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1039 inline _GLIBCXX_CONSTEXPR
unsigned long long
1040 __lg(unsigned long long __n
)
1041 { return sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1043 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1046 * @brief Tests a range for element-wise equality.
1047 * @ingroup non_mutating_algorithms
1048 * @param __first1 An input iterator.
1049 * @param __last1 An input iterator.
1050 * @param __first2 An input iterator.
1051 * @return A boolean true or false.
1053 * This compares the elements of two ranges using @c == and returns true or
1054 * false depending on whether all of the corresponding elements of the
1057 template<typename _II1
, typename _II2
>
1059 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1061 // concept requirements
1062 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1063 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1064 __glibcxx_function_requires(_EqualOpConcept
<
1065 typename iterator_traits
<_II1
>::value_type
,
1066 typename iterator_traits
<_II2
>::value_type
>)
1067 __glibcxx_requires_can_increment_range(__first1
, __last1
, __first2
);
1069 return std::__equal_aux(std::__niter_base(__first1
),
1070 std::__niter_base(__last1
),
1071 std::__niter_base(__first2
));
1075 * @brief Tests a range for element-wise equality.
1076 * @ingroup non_mutating_algorithms
1077 * @param __first1 An input iterator.
1078 * @param __last1 An input iterator.
1079 * @param __first2 An input iterator.
1080 * @param __binary_pred A binary predicate @link functors
1082 * @return A boolean true or false.
1084 * This compares the elements of two ranges using the binary_pred
1085 * parameter, and returns true or
1086 * false depending on whether all of the corresponding elements of the
1089 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1091 equal(_IIter1 __first1
, _IIter1 __last1
,
1092 _IIter2 __first2
, _BinaryPredicate __binary_pred
)
1094 // concept requirements
1095 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1096 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1097 __glibcxx_requires_valid_range(__first1
, __last1
);
1099 for (; __first1
!= __last1
; ++__first1
, (void)++__first2
)
1100 if (!bool(__binary_pred(*__first1
, *__first2
)))
1105 #if __cplusplus >= 201103L
1106 // 4-iterator version of std::equal<It1, It2> for use in C++11.
1107 template<typename _II1
, typename _II2
>
1109 __equal4(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1111 using _RATag
= random_access_iterator_tag
;
1112 using _Cat1
= typename iterator_traits
<_II1
>::iterator_category
;
1113 using _Cat2
= typename iterator_traits
<_II2
>::iterator_category
;
1114 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1117 auto __d1
= std::distance(__first1
, __last1
);
1118 auto __d2
= std::distance(__first2
, __last2
);
1121 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
);
1124 for (; __first1
!= __last1
&& __first2
!= __last2
;
1125 ++__first1
, (void)++__first2
)
1126 if (!(*__first1
== *__first2
))
1128 return __first1
== __last1
&& __first2
== __last2
;
1131 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1132 template<typename _II1
, typename _II2
, typename _BinaryPredicate
>
1134 __equal4(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
,
1135 _BinaryPredicate __binary_pred
)
1137 using _RATag
= random_access_iterator_tag
;
1138 using _Cat1
= typename iterator_traits
<_II1
>::iterator_category
;
1139 using _Cat2
= typename iterator_traits
<_II2
>::iterator_category
;
1140 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1143 auto __d1
= std::distance(__first1
, __last1
);
1144 auto __d2
= std::distance(__first2
, __last2
);
1147 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
,
1151 for (; __first1
!= __last1
&& __first2
!= __last2
;
1152 ++__first1
, (void)++__first2
)
1153 if (!bool(__binary_pred(*__first1
, *__first2
)))
1155 return __first1
== __last1
&& __first2
== __last2
;
1159 #if __cplusplus > 201103L
1161 #define __cpp_lib_robust_nonmodifying_seq_ops 201304
1164 * @brief Tests a range for element-wise equality.
1165 * @ingroup non_mutating_algorithms
1166 * @param __first1 An input iterator.
1167 * @param __last1 An input iterator.
1168 * @param __first2 An input iterator.
1169 * @param __last2 An input iterator.
1170 * @return A boolean true or false.
1172 * This compares the elements of two ranges using @c == and returns true or
1173 * false depending on whether all of the corresponding elements of the
1176 template<typename _II1
, typename _II2
>
1178 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1180 // concept requirements
1181 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1182 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1183 __glibcxx_function_requires(_EqualOpConcept
<
1184 typename iterator_traits
<_II1
>::value_type
,
1185 typename iterator_traits
<_II2
>::value_type
>)
1186 __glibcxx_requires_valid_range(__first1
, __last1
);
1187 __glibcxx_requires_valid_range(__first2
, __last2
);
1189 return _GLIBCXX_STD_A::__equal4(__first1
, __last1
, __first2
, __last2
);
1193 * @brief Tests a range for element-wise equality.
1194 * @ingroup non_mutating_algorithms
1195 * @param __first1 An input iterator.
1196 * @param __last1 An input iterator.
1197 * @param __first2 An input iterator.
1198 * @param __last2 An input iterator.
1199 * @param __binary_pred A binary predicate @link functors
1201 * @return A boolean true or false.
1203 * This compares the elements of two ranges using the binary_pred
1204 * parameter, and returns true or
1205 * false depending on whether all of the corresponding elements of the
1208 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1210 equal(_IIter1 __first1
, _IIter1 __last1
,
1211 _IIter2 __first2
, _IIter2 __last2
, _BinaryPredicate __binary_pred
)
1213 // concept requirements
1214 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1215 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1216 __glibcxx_requires_valid_range(__first1
, __last1
);
1217 __glibcxx_requires_valid_range(__first2
, __last2
);
1219 return _GLIBCXX_STD_A::__equal4(__first1
, __last1
, __first2
, __last2
,
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 * @return A boolean true or false.
1233 * <em>Returns true if the sequence of elements defined by the range
1234 * [first1,last1) is lexicographically less than the sequence of elements
1235 * defined by the range [first2,last2). Returns false otherwise.</em>
1236 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1237 * then this is an inline call to @c memcmp.
1239 template<typename _II1
, typename _II2
>
1241 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1242 _II2 __first2
, _II2 __last2
)
1244 #ifdef _GLIBCXX_CONCEPT_CHECKS
1245 // concept requirements
1246 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
1247 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
1249 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1250 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1251 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
1252 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
1253 __glibcxx_requires_valid_range(__first1
, __last1
);
1254 __glibcxx_requires_valid_range(__first2
, __last2
);
1256 return std::__lexicographical_compare_aux(std::__niter_base(__first1
),
1257 std::__niter_base(__last1
),
1258 std::__niter_base(__first2
),
1259 std::__niter_base(__last2
));
1263 * @brief Performs @b dictionary comparison on ranges.
1264 * @ingroup sorting_algorithms
1265 * @param __first1 An input iterator.
1266 * @param __last1 An input iterator.
1267 * @param __first2 An input iterator.
1268 * @param __last2 An input iterator.
1269 * @param __comp A @link comparison_functors comparison functor@endlink.
1270 * @return A boolean true or false.
1272 * The same as the four-parameter @c lexicographical_compare, but uses the
1273 * comp parameter instead of @c <.
1275 template<typename _II1
, typename _II2
, typename _Compare
>
1277 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1278 _II2 __first2
, _II2 __last2
, _Compare __comp
)
1280 // concept requirements
1281 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1282 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1283 __glibcxx_requires_valid_range(__first1
, __last1
);
1284 __glibcxx_requires_valid_range(__first2
, __last2
);
1286 return std::__lexicographical_compare_impl
1287 (__first1
, __last1
, __first2
, __last2
,
1288 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
1291 template<typename _InputIterator1
, typename _InputIterator2
,
1292 typename _BinaryPredicate
>
1293 pair
<_InputIterator1
, _InputIterator2
>
1294 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1295 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1297 while (__first1
!= __last1
&& __binary_pred(__first1
, __first2
))
1302 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1306 * @brief Finds the places in ranges which don't match.
1307 * @ingroup non_mutating_algorithms
1308 * @param __first1 An input iterator.
1309 * @param __last1 An input iterator.
1310 * @param __first2 An input iterator.
1311 * @return A pair of iterators pointing to the first mismatch.
1313 * This compares the elements of two ranges using @c == and returns a pair
1314 * of iterators. The first iterator points into the first range, the
1315 * second iterator points into the second range, and the elements pointed
1316 * to by the iterators are not equal.
1318 template<typename _InputIterator1
, typename _InputIterator2
>
1319 inline pair
<_InputIterator1
, _InputIterator2
>
1320 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1321 _InputIterator2 __first2
)
1323 // concept requirements
1324 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1325 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1326 __glibcxx_function_requires(_EqualOpConcept
<
1327 typename iterator_traits
<_InputIterator1
>::value_type
,
1328 typename iterator_traits
<_InputIterator2
>::value_type
>)
1329 __glibcxx_requires_valid_range(__first1
, __last1
);
1331 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1332 __gnu_cxx::__ops::__iter_equal_to_iter());
1336 * @brief Finds the places in ranges which don't match.
1337 * @ingroup non_mutating_algorithms
1338 * @param __first1 An input iterator.
1339 * @param __last1 An input iterator.
1340 * @param __first2 An input iterator.
1341 * @param __binary_pred A binary predicate @link functors
1343 * @return A pair of iterators pointing to the first mismatch.
1345 * This compares the elements of two ranges using the binary_pred
1346 * parameter, and returns a pair
1347 * of iterators. The first iterator points into the first range, the
1348 * second iterator points into the second range, and the elements pointed
1349 * to by the iterators are not equal.
1351 template<typename _InputIterator1
, typename _InputIterator2
,
1352 typename _BinaryPredicate
>
1353 inline pair
<_InputIterator1
, _InputIterator2
>
1354 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1355 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1357 // concept requirements
1358 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1359 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1360 __glibcxx_requires_valid_range(__first1
, __last1
);
1362 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1363 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1366 #if __cplusplus > 201103L
1368 template<typename _InputIterator1
, typename _InputIterator2
,
1369 typename _BinaryPredicate
>
1370 pair
<_InputIterator1
, _InputIterator2
>
1371 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1372 _InputIterator2 __first2
, _InputIterator2 __last2
,
1373 _BinaryPredicate __binary_pred
)
1375 while (__first1
!= __last1
&& __first2
!= __last2
1376 && __binary_pred(__first1
, __first2
))
1381 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1385 * @brief Finds the places in ranges which don't match.
1386 * @ingroup non_mutating_algorithms
1387 * @param __first1 An input iterator.
1388 * @param __last1 An input iterator.
1389 * @param __first2 An input iterator.
1390 * @param __last2 An input iterator.
1391 * @return A pair of iterators pointing to the first mismatch.
1393 * This compares the elements of two ranges using @c == and returns a pair
1394 * of iterators. The first iterator points into the first range, the
1395 * second iterator points into the second range, and the elements pointed
1396 * to by the iterators are not equal.
1398 template<typename _InputIterator1
, typename _InputIterator2
>
1399 inline pair
<_InputIterator1
, _InputIterator2
>
1400 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1401 _InputIterator2 __first2
, _InputIterator2 __last2
)
1403 // concept requirements
1404 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1405 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1406 __glibcxx_function_requires(_EqualOpConcept
<
1407 typename iterator_traits
<_InputIterator1
>::value_type
,
1408 typename iterator_traits
<_InputIterator2
>::value_type
>)
1409 __glibcxx_requires_valid_range(__first1
, __last1
);
1410 __glibcxx_requires_valid_range(__first2
, __last2
);
1412 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1413 __gnu_cxx::__ops::__iter_equal_to_iter());
1417 * @brief Finds the places in ranges which don't match.
1418 * @ingroup non_mutating_algorithms
1419 * @param __first1 An input iterator.
1420 * @param __last1 An input iterator.
1421 * @param __first2 An input iterator.
1422 * @param __last2 An input iterator.
1423 * @param __binary_pred A binary predicate @link functors
1425 * @return A pair of iterators pointing to the first mismatch.
1427 * This compares the elements of two ranges using the binary_pred
1428 * parameter, and returns a pair
1429 * of iterators. The first iterator points into the first range, the
1430 * second iterator points into the second range, and the elements pointed
1431 * to by the iterators are not equal.
1433 template<typename _InputIterator1
, typename _InputIterator2
,
1434 typename _BinaryPredicate
>
1435 inline pair
<_InputIterator1
, _InputIterator2
>
1436 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1437 _InputIterator2 __first2
, _InputIterator2 __last2
,
1438 _BinaryPredicate __binary_pred
)
1440 // concept requirements
1441 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1442 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1443 __glibcxx_requires_valid_range(__first1
, __last1
);
1444 __glibcxx_requires_valid_range(__first2
, __last2
);
1446 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1447 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1451 _GLIBCXX_END_NAMESPACE_ALGO
1452 _GLIBCXX_END_NAMESPACE_VERSION
1455 // NB: This file is included within many other C++ includes, as a way
1456 // of getting the base algorithms. So, make sure that parallel bits
1457 // come in too if requested.
1458 #ifdef _GLIBCXX_PARALLEL
1459 # include <parallel/algobase.h>