1 // Core algorithmic facilities -*- C++ -*-
3 // Copyright (C) 2001-2013 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 and _GLIBCXX_MOVE
71 #include <bits/predefined_ops.h>
73 namespace std
_GLIBCXX_VISIBILITY(default)
75 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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
>
84 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
86 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
88 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
90 _ValueType1 __tmp
= _GLIBCXX_MOVE(*__a
);
91 *__a
= _GLIBCXX_MOVE(*__b
);
92 *__b
= _GLIBCXX_MOVE(__tmp
);
97 struct __iter_swap
<true>
99 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
101 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
109 * @brief Swaps the contents of two iterators.
110 * @ingroup mutating_algorithms
111 * @param __a An iterator.
112 * @param __b Another iterator.
115 * This function swaps the values pointed to by two iterators, not the
116 * iterators themselves.
118 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
120 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
122 // concept requirements
123 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
125 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
128 #if __cplusplus < 201103L
129 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
131 typedef typename iterator_traits
<_ForwardIterator2
>::value_type
134 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType1
,
136 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType2
,
139 typedef typename iterator_traits
<_ForwardIterator1
>::reference
141 typedef typename iterator_traits
<_ForwardIterator2
>::reference
143 std::__iter_swap
<__are_same
<_ValueType1
, _ValueType2
>::__value
144 && __are_same
<_ValueType1
&, _ReferenceType1
>::__value
145 && __are_same
<_ValueType2
&, _ReferenceType2
>::__value
>::
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).
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.
164 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
166 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
167 _ForwardIterator2 __first2
)
169 // concept requirements
170 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
172 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
174 __glibcxx_requires_valid_range(__first1
, __last1
);
176 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
177 std::iter_swap(__first1
, __first2
);
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.
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.
192 template<typename _Tp
>
194 min(const _Tp
& __a
, const _Tp
& __b
)
196 // concept requirements
197 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
198 //return __b < __a ? __b : __a;
205 * @brief This does what you think it does.
206 * @ingroup sorting_algorithms
207 * @param __a A thing of arbitrary type.
208 * @param __b Another thing of arbitrary type.
209 * @return The greater of the parameters.
211 * This is the simple classic generic implementation. It will work on
212 * temporary expressions, since they are only evaluated once, unlike a
213 * preprocessor macro.
215 template<typename _Tp
>
217 max(const _Tp
& __a
, const _Tp
& __b
)
219 // concept requirements
220 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
221 //return __a < __b ? __b : __a;
228 * @brief This does what you think it does.
229 * @ingroup sorting_algorithms
230 * @param __a A thing of arbitrary type.
231 * @param __b Another thing of arbitrary type.
232 * @param __comp A @link comparison_functors comparison functor@endlink.
233 * @return The lesser of the parameters.
235 * This will work on temporary expressions, since they are only evaluated
236 * once, unlike a preprocessor macro.
238 template<typename _Tp
, typename _Compare
>
240 min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
242 //return __comp(__b, __a) ? __b : __a;
243 if (__comp(__b
, __a
))
249 * @brief This does what you think it does.
250 * @ingroup sorting_algorithms
251 * @param __a A thing of arbitrary type.
252 * @param __b Another thing of arbitrary type.
253 * @param __comp A @link comparison_functors comparison functor@endlink.
254 * @return The greater of the parameters.
256 * This will work on temporary expressions, since they are only evaluated
257 * once, unlike a preprocessor macro.
259 template<typename _Tp
, typename _Compare
>
261 max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
263 //return __comp(__a, __b) ? __b : __a;
264 if (__comp(__a
, __b
))
269 // If _Iterator is a __normal_iterator return its base (a plain pointer,
270 // normally) otherwise return it untouched. See copy, fill, ...
271 template<typename _Iterator
>
273 : _Iter_base
<_Iterator
, __is_normal_iterator
<_Iterator
>::__value
>
276 template<typename _Iterator
>
277 inline typename _Niter_base
<_Iterator
>::iterator_type
278 __niter_base(_Iterator __it
)
279 { return std::_Niter_base
<_Iterator
>::_S_base(__it
); }
281 // Likewise, for move_iterator.
282 template<typename _Iterator
>
284 : _Iter_base
<_Iterator
, __is_move_iterator
<_Iterator
>::__value
>
287 template<typename _Iterator
>
288 inline typename _Miter_base
<_Iterator
>::iterator_type
289 __miter_base(_Iterator __it
)
290 { return std::_Miter_base
<_Iterator
>::_S_base(__it
); }
292 // All of these auxiliary structs serve two purposes. (1) Replace
293 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
294 // because the input and output ranges are permitted to overlap.)
295 // (2) If we're using random access iterators, then write the loop as
296 // a for loop with an explicit count.
298 template<bool, bool, typename
>
301 template<typename _II
, typename _OI
>
303 __copy_m(_II __first
, _II __last
, _OI __result
)
305 for (; __first
!= __last
; ++__result
, ++__first
)
306 *__result
= *__first
;
311 #if __cplusplus >= 201103L
312 template<typename _Category
>
313 struct __copy_move
<true, false, _Category
>
315 template<typename _II
, typename _OI
>
317 __copy_m(_II __first
, _II __last
, _OI __result
)
319 for (; __first
!= __last
; ++__result
, ++__first
)
320 *__result
= std::move(*__first
);
327 struct __copy_move
<false, false, random_access_iterator_tag
>
329 template<typename _II
, typename _OI
>
331 __copy_m(_II __first
, _II __last
, _OI __result
)
333 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
334 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
336 *__result
= *__first
;
344 #if __cplusplus >= 201103L
346 struct __copy_move
<true, false, random_access_iterator_tag
>
348 template<typename _II
, typename _OI
>
350 __copy_m(_II __first
, _II __last
, _OI __result
)
352 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
353 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
355 *__result
= std::move(*__first
);
364 template<bool _IsMove
>
365 struct __copy_move
<_IsMove
, true, random_access_iterator_tag
>
367 template<typename _Tp
>
369 __copy_m(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
371 const ptrdiff_t _Num
= __last
- __first
;
373 __builtin_memmove(__result
, __first
, sizeof(_Tp
) * _Num
);
374 return __result
+ _Num
;
378 template<bool _IsMove
, typename _II
, typename _OI
>
380 __copy_move_a(_II __first
, _II __last
, _OI __result
)
382 typedef typename iterator_traits
<_II
>::value_type _ValueTypeI
;
383 typedef typename iterator_traits
<_OI
>::value_type _ValueTypeO
;
384 typedef typename iterator_traits
<_II
>::iterator_category _Category
;
385 const bool __simple
= (__is_trivial(_ValueTypeI
)
386 && __is_pointer
<_II
>::__value
387 && __is_pointer
<_OI
>::__value
388 && __are_same
<_ValueTypeI
, _ValueTypeO
>::__value
);
390 return std::__copy_move
<_IsMove
, __simple
,
391 _Category
>::__copy_m(__first
, __last
, __result
);
394 // Helpers for streambuf iterators (either istream or ostream).
395 // NB: avoid including <iosfwd>, relatively large.
396 template<typename _CharT
>
399 template<typename _CharT
, typename _Traits
>
400 class istreambuf_iterator
;
402 template<typename _CharT
, typename _Traits
>
403 class ostreambuf_iterator
;
405 template<bool _IsMove
, typename _CharT
>
406 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
407 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
408 __copy_move_a2(_CharT
*, _CharT
*,
409 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
411 template<bool _IsMove
, typename _CharT
>
412 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
413 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
414 __copy_move_a2(const _CharT
*, const _CharT
*,
415 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
417 template<bool _IsMove
, typename _CharT
>
418 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
420 __copy_move_a2(istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >,
421 istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >, _CharT
*);
423 template<bool _IsMove
, typename _II
, typename _OI
>
425 __copy_move_a2(_II __first
, _II __last
, _OI __result
)
427 return _OI(std::__copy_move_a
<_IsMove
>(std::__niter_base(__first
),
428 std::__niter_base(__last
),
429 std::__niter_base(__result
)));
433 * @brief Copies the range [first,last) into result.
434 * @ingroup mutating_algorithms
435 * @param __first An input iterator.
436 * @param __last An input iterator.
437 * @param __result An output iterator.
438 * @return result + (first - last)
440 * This inline function will boil down to a call to @c memmove whenever
441 * possible. Failing that, if random access iterators are passed, then the
442 * loop count will be known (and therefore a candidate for compiler
443 * optimizations such as unrolling). Result may not be contained within
444 * [first,last); the copy_backward function should be used instead.
446 * Note that the end of the output range is permitted to be contained
447 * within [first,last).
449 template<typename _II
, typename _OI
>
451 copy(_II __first
, _II __last
, _OI __result
)
453 // concept requirements
454 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
455 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
456 typename iterator_traits
<_II
>::value_type
>)
457 __glibcxx_requires_valid_range(__first
, __last
);
459 return (std::__copy_move_a2
<__is_move_iterator
<_II
>::__value
>
460 (std::__miter_base(__first
), std::__miter_base(__last
),
464 #if __cplusplus >= 201103L
466 * @brief Moves the range [first,last) into result.
467 * @ingroup mutating_algorithms
468 * @param __first An input iterator.
469 * @param __last An input iterator.
470 * @param __result An output iterator.
471 * @return result + (first - last)
473 * This inline function will boil down to a call to @c memmove whenever
474 * possible. Failing that, if random access iterators are passed, then the
475 * loop count will be known (and therefore a candidate for compiler
476 * optimizations such as unrolling). Result may not be contained within
477 * [first,last); the move_backward function should be used instead.
479 * Note that the end of the output range is permitted to be contained
480 * within [first,last).
482 template<typename _II
, typename _OI
>
484 move(_II __first
, _II __last
, _OI __result
)
486 // concept requirements
487 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
488 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
489 typename iterator_traits
<_II
>::value_type
>)
490 __glibcxx_requires_valid_range(__first
, __last
);
492 return std::__copy_move_a2
<true>(std::__miter_base(__first
),
493 std::__miter_base(__last
), __result
);
496 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
498 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
501 template<bool, bool, typename
>
502 struct __copy_move_backward
504 template<typename _BI1
, typename _BI2
>
506 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
508 while (__first
!= __last
)
509 *--__result
= *--__last
;
514 #if __cplusplus >= 201103L
515 template<typename _Category
>
516 struct __copy_move_backward
<true, false, _Category
>
518 template<typename _BI1
, typename _BI2
>
520 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
522 while (__first
!= __last
)
523 *--__result
= std::move(*--__last
);
530 struct __copy_move_backward
<false, false, random_access_iterator_tag
>
532 template<typename _BI1
, typename _BI2
>
534 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
536 typename iterator_traits
<_BI1
>::difference_type __n
;
537 for (__n
= __last
- __first
; __n
> 0; --__n
)
538 *--__result
= *--__last
;
543 #if __cplusplus >= 201103L
545 struct __copy_move_backward
<true, false, random_access_iterator_tag
>
547 template<typename _BI1
, typename _BI2
>
549 __copy_move_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
551 typename iterator_traits
<_BI1
>::difference_type __n
;
552 for (__n
= __last
- __first
; __n
> 0; --__n
)
553 *--__result
= std::move(*--__last
);
559 template<bool _IsMove
>
560 struct __copy_move_backward
<_IsMove
, true, random_access_iterator_tag
>
562 template<typename _Tp
>
564 __copy_move_b(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
566 const ptrdiff_t _Num
= __last
- __first
;
568 __builtin_memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
569 return __result
- _Num
;
573 template<bool _IsMove
, typename _BI1
, typename _BI2
>
575 __copy_move_backward_a(_BI1 __first
, _BI1 __last
, _BI2 __result
)
577 typedef typename iterator_traits
<_BI1
>::value_type _ValueType1
;
578 typedef typename iterator_traits
<_BI2
>::value_type _ValueType2
;
579 typedef typename iterator_traits
<_BI1
>::iterator_category _Category
;
580 const bool __simple
= (__is_trivial(_ValueType1
)
581 && __is_pointer
<_BI1
>::__value
582 && __is_pointer
<_BI2
>::__value
583 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
585 return std::__copy_move_backward
<_IsMove
, __simple
,
586 _Category
>::__copy_move_b(__first
,
591 template<bool _IsMove
, typename _BI1
, typename _BI2
>
593 __copy_move_backward_a2(_BI1 __first
, _BI1 __last
, _BI2 __result
)
595 return _BI2(std::__copy_move_backward_a
<_IsMove
>
596 (std::__niter_base(__first
), std::__niter_base(__last
),
597 std::__niter_base(__result
)));
601 * @brief Copies the range [first,last) into result.
602 * @ingroup mutating_algorithms
603 * @param __first A bidirectional iterator.
604 * @param __last A bidirectional iterator.
605 * @param __result A bidirectional iterator.
606 * @return result - (first - last)
608 * The function has the same effect as copy, but starts at the end of the
609 * range and works its way to the start, returning the start of the result.
610 * This inline function will boil down to a call to @c memmove whenever
611 * possible. Failing that, if random access iterators are passed, then the
612 * loop count will be known (and therefore a candidate for compiler
613 * optimizations such as unrolling).
615 * Result may not be in the range (first,last]. Use copy instead. Note
616 * that the start of the output range may overlap [first,last).
618 template<typename _BI1
, typename _BI2
>
620 copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
622 // concept requirements
623 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
624 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
625 __glibcxx_function_requires(_ConvertibleConcept
<
626 typename iterator_traits
<_BI1
>::value_type
,
627 typename iterator_traits
<_BI2
>::value_type
>)
628 __glibcxx_requires_valid_range(__first
, __last
);
630 return (std::__copy_move_backward_a2
<__is_move_iterator
<_BI1
>::__value
>
631 (std::__miter_base(__first
), std::__miter_base(__last
),
635 #if __cplusplus >= 201103L
637 * @brief Moves the range [first,last) into result.
638 * @ingroup mutating_algorithms
639 * @param __first A bidirectional iterator.
640 * @param __last A bidirectional iterator.
641 * @param __result A bidirectional iterator.
642 * @return result - (first - last)
644 * The function has the same effect as move, but starts at the end of the
645 * range and works its way to the start, returning the start of the result.
646 * This inline function will boil down to a call to @c memmove whenever
647 * possible. Failing that, if random access iterators are passed, then the
648 * loop count will be known (and therefore a candidate for compiler
649 * optimizations such as unrolling).
651 * Result may not be in the range (first,last]. Use move instead. Note
652 * that the start of the output range may overlap [first,last).
654 template<typename _BI1
, typename _BI2
>
656 move_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
658 // concept requirements
659 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
660 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
661 __glibcxx_function_requires(_ConvertibleConcept
<
662 typename iterator_traits
<_BI1
>::value_type
,
663 typename iterator_traits
<_BI2
>::value_type
>)
664 __glibcxx_requires_valid_range(__first
, __last
);
666 return std::__copy_move_backward_a2
<true>(std::__miter_base(__first
),
667 std::__miter_base(__last
),
671 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
673 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
676 template<typename _ForwardIterator
, typename _Tp
>
678 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, void>::__type
679 __fill_a(_ForwardIterator __first
, _ForwardIterator __last
,
682 for (; __first
!= __last
; ++__first
)
686 template<typename _ForwardIterator
, typename _Tp
>
688 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, void>::__type
689 __fill_a(_ForwardIterator __first
, _ForwardIterator __last
,
692 const _Tp __tmp
= __value
;
693 for (; __first
!= __last
; ++__first
)
697 // Specialization: for char types we can use memset.
698 template<typename _Tp
>
700 __gnu_cxx::__enable_if
<__is_byte
<_Tp
>::__value
, void>::__type
701 __fill_a(_Tp
* __first
, _Tp
* __last
, const _Tp
& __c
)
703 const _Tp __tmp
= __c
;
704 __builtin_memset(__first
, static_cast<unsigned char>(__tmp
),
709 * @brief Fills the range [first,last) with copies of value.
710 * @ingroup mutating_algorithms
711 * @param __first A forward iterator.
712 * @param __last A forward iterator.
713 * @param __value A reference-to-const of arbitrary type.
716 * This function fills a range with copies of the same value. For char
717 * types filling contiguous areas of memory, this becomes an inline call
718 * to @c memset or @c wmemset.
720 template<typename _ForwardIterator
, typename _Tp
>
722 fill(_ForwardIterator __first
, _ForwardIterator __last
, const _Tp
& __value
)
724 // concept requirements
725 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
727 __glibcxx_requires_valid_range(__first
, __last
);
729 std::__fill_a(std::__niter_base(__first
), std::__niter_base(__last
),
733 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
735 __gnu_cxx::__enable_if
<!__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
736 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
738 for (__decltype(__n
+ 0) __niter
= __n
;
739 __niter
> 0; --__niter
, ++__first
)
744 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
746 __gnu_cxx::__enable_if
<__is_scalar
<_Tp
>::__value
, _OutputIterator
>::__type
747 __fill_n_a(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
749 const _Tp __tmp
= __value
;
750 for (__decltype(__n
+ 0) __niter
= __n
;
751 __niter
> 0; --__niter
, ++__first
)
756 template<typename _Size
, typename _Tp
>
758 __gnu_cxx::__enable_if
<__is_byte
<_Tp
>::__value
, _Tp
*>::__type
759 __fill_n_a(_Tp
* __first
, _Size __n
, const _Tp
& __c
)
761 std::__fill_a(__first
, __first
+ __n
, __c
);
762 return __first
+ __n
;
766 * @brief Fills the range [first,first+n) with copies of value.
767 * @ingroup mutating_algorithms
768 * @param __first An output iterator.
769 * @param __n The count of copies to perform.
770 * @param __value A reference-to-const of arbitrary type.
771 * @return The iterator at first+n.
773 * This function fills a range with copies of the same value. For char
774 * types filling contiguous areas of memory, this becomes an inline call
775 * to @c memset or @ wmemset.
777 * _GLIBCXX_RESOLVE_LIB_DEFECTS
778 * DR 865. More algorithms that throw away information
780 template<typename _OI
, typename _Size
, typename _Tp
>
782 fill_n(_OI __first
, _Size __n
, const _Tp
& __value
)
784 // concept requirements
785 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
, _Tp
>)
787 return _OI(std::__fill_n_a(std::__niter_base(__first
), __n
, __value
));
790 template<bool _BoolType
>
793 template<typename _II1
, typename _II2
>
795 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
797 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
798 if (!(*__first1
== *__first2
))
807 template<typename _Tp
>
809 equal(const _Tp
* __first1
, const _Tp
* __last1
, const _Tp
* __first2
)
811 return !__builtin_memcmp(__first1
, __first2
, sizeof(_Tp
)
812 * (__last1
- __first1
));
816 template<typename _II1
, typename _II2
>
818 __equal_aux(_II1 __first1
, _II1 __last1
, _II2 __first2
)
820 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
821 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
822 const bool __simple
= ((__is_integer
<_ValueType1
>::__value
823 || __is_pointer
<_ValueType1
>::__value
)
824 && __is_pointer
<_II1
>::__value
825 && __is_pointer
<_II2
>::__value
826 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
828 return std::__equal
<__simple
>::equal(__first1
, __last1
, __first2
);
831 template<typename
, typename
>
834 template<typename _II1
, typename _II2
>
836 __newlast1(_II1
, _II1 __last1
, _II2
, _II2
)
839 template<typename _II
>
841 __cnd2(_II __first
, _II __last
)
842 { return __first
!= __last
; }
846 struct __lc_rai
<random_access_iterator_tag
, random_access_iterator_tag
>
848 template<typename _RAI1
, typename _RAI2
>
850 __newlast1(_RAI1 __first1
, _RAI1 __last1
,
851 _RAI2 __first2
, _RAI2 __last2
)
853 const typename iterator_traits
<_RAI1
>::difference_type
854 __diff1
= __last1
- __first1
;
855 const typename iterator_traits
<_RAI2
>::difference_type
856 __diff2
= __last2
- __first2
;
857 return __diff2
< __diff1
? __first1
+ __diff2
: __last1
;
860 template<typename _RAI
>
866 template<typename _II1
, typename _II2
, typename _Compare
>
868 __lexicographical_compare_impl(_II1 __first1
, _II1 __last1
,
869 _II2 __first2
, _II2 __last2
,
872 typedef typename iterator_traits
<_II1
>::iterator_category _Category1
;
873 typedef typename iterator_traits
<_II2
>::iterator_category _Category2
;
874 typedef std::__lc_rai
<_Category1
, _Category2
> __rai_type
;
876 __last1
= __rai_type::__newlast1(__first1
, __last1
, __first2
, __last2
);
877 for (; __first1
!= __last1
&& __rai_type::__cnd2(__first2
, __last2
);
878 ++__first1
, ++__first2
)
880 if (__comp(__first1
, __first2
))
882 if (__comp(__first2
, __first1
))
885 return __first1
== __last1
&& __first2
!= __last2
;
888 template<bool _BoolType
>
889 struct __lexicographical_compare
891 template<typename _II1
, typename _II2
>
892 static bool __lc(_II1
, _II1
, _II2
, _II2
);
895 template<bool _BoolType
>
896 template<typename _II1
, typename _II2
>
898 __lexicographical_compare
<_BoolType
>::
899 __lc(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
901 return std::__lexicographical_compare_impl(
902 __first1
, __last1
, __first2
, __last2
,
903 __gnu_cxx::__ops::__iter_less_iter());
907 struct __lexicographical_compare
<true>
909 template<typename _Tp
, typename _Up
>
911 __lc(const _Tp
* __first1
, const _Tp
* __last1
,
912 const _Up
* __first2
, const _Up
* __last2
)
914 const size_t __len1
= __last1
- __first1
;
915 const size_t __len2
= __last2
- __first2
;
916 const int __result
= __builtin_memcmp(__first1
, __first2
,
917 std::min(__len1
, __len2
));
918 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
922 template<typename _II1
, typename _II2
>
924 __lexicographical_compare_aux(_II1 __first1
, _II1 __last1
,
925 _II2 __first2
, _II2 __last2
)
927 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
928 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
929 const bool __simple
=
930 (__is_byte
<_ValueType1
>::__value
&& __is_byte
<_ValueType2
>::__value
931 && !__gnu_cxx::__numeric_traits
<_ValueType1
>::__is_signed
932 && !__gnu_cxx::__numeric_traits
<_ValueType2
>::__is_signed
933 && __is_pointer
<_II1
>::__value
934 && __is_pointer
<_II2
>::__value
);
936 return std::__lexicographical_compare
<__simple
>::__lc(__first1
, __last1
,
940 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
942 __lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
943 const _Tp
& __val
, _Compare __comp
)
945 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
948 _DistanceType __len
= std::distance(__first
, __last
);
952 _DistanceType __half
= __len
>> 1;
953 _ForwardIterator __middle
= __first
;
954 std::advance(__middle
, __half
);
955 if (__comp(__middle
, __val
))
959 __len
= __len
- __half
- 1;
968 * @brief Finds the first position in which @a val could be inserted
969 * without changing the ordering.
970 * @param __first An iterator.
971 * @param __last Another iterator.
972 * @param __val The search term.
973 * @return An iterator pointing to the first element <em>not less
974 * than</em> @a val, or end() if every element is less than
976 * @ingroup binary_search_algorithms
978 template<typename _ForwardIterator
, typename _Tp
>
980 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
983 // concept requirements
984 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
985 __glibcxx_function_requires(_LessThanOpConcept
<
986 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
987 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
989 return std::__lower_bound(__first
, __last
, __val
,
990 __gnu_cxx::__ops::__iter_less_val());
993 /// This is a helper function for the sort routines and for random.tcc.
994 // Precondition: __n > 0.
995 inline _GLIBCXX_CONSTEXPR
int
997 { return sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
999 inline _GLIBCXX_CONSTEXPR
unsigned
1001 { return sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
1003 inline _GLIBCXX_CONSTEXPR
long
1005 { return sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1007 inline _GLIBCXX_CONSTEXPR
unsigned long
1008 __lg(unsigned long __n
)
1009 { return sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
1011 inline _GLIBCXX_CONSTEXPR
long long
1013 { return sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1015 inline _GLIBCXX_CONSTEXPR
unsigned long long
1016 __lg(unsigned long long __n
)
1017 { return sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
1019 _GLIBCXX_END_NAMESPACE_VERSION
1021 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1024 * @brief Tests a range for element-wise equality.
1025 * @ingroup non_mutating_algorithms
1026 * @param __first1 An input iterator.
1027 * @param __last1 An input iterator.
1028 * @param __first2 An input iterator.
1029 * @return A boolean true or false.
1031 * This compares the elements of two ranges using @c == and returns true or
1032 * false depending on whether all of the corresponding elements of the
1035 template<typename _II1
, typename _II2
>
1037 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
1039 // concept requirements
1040 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1041 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1042 __glibcxx_function_requires(_EqualOpConcept
<
1043 typename iterator_traits
<_II1
>::value_type
,
1044 typename iterator_traits
<_II2
>::value_type
>)
1045 __glibcxx_requires_valid_range(__first1
, __last1
);
1047 return std::__equal_aux(std::__niter_base(__first1
),
1048 std::__niter_base(__last1
),
1049 std::__niter_base(__first2
));
1053 * @brief Tests a range for element-wise equality.
1054 * @ingroup non_mutating_algorithms
1055 * @param __first1 An input iterator.
1056 * @param __last1 An input iterator.
1057 * @param __first2 An input iterator.
1058 * @param __binary_pred A binary predicate @link functors
1060 * @return A boolean true or false.
1062 * This compares the elements of two ranges using the binary_pred
1063 * parameter, and returns true or
1064 * false depending on whether all of the corresponding elements of the
1067 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1069 equal(_IIter1 __first1
, _IIter1 __last1
,
1070 _IIter2 __first2
, _BinaryPredicate __binary_pred
)
1072 // concept requirements
1073 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1074 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1075 __glibcxx_requires_valid_range(__first1
, __last1
);
1077 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
1078 if (!bool(__binary_pred(*__first1
, *__first2
)))
1083 #if __cplusplus > 201103L
1085 * @brief Tests a range for element-wise equality.
1086 * @ingroup non_mutating_algorithms
1087 * @param __first1 An input iterator.
1088 * @param __last1 An input iterator.
1089 * @param __first2 An input iterator.
1090 * @param __last2 An input iterator.
1091 * @return A boolean true or false.
1093 * This compares the elements of two ranges using @c == and returns true or
1094 * false depending on whether all of the corresponding elements of the
1097 template<typename _II1
, typename _II2
>
1099 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
, _II2 __last2
)
1101 // concept requirements
1102 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1103 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1104 __glibcxx_function_requires(_EqualOpConcept
<
1105 typename iterator_traits
<_II1
>::value_type
,
1106 typename iterator_traits
<_II2
>::value_type
>)
1107 __glibcxx_requires_valid_range(__first1
, __last1
);
1108 __glibcxx_requires_valid_range(__first2
, __last2
);
1110 using _RATag
= random_access_iterator_tag
;
1111 using _Cat1
= typename iterator_traits
<_II1
>::iterator_category
;
1112 using _Cat2
= typename iterator_traits
<_II2
>::iterator_category
;
1113 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1116 auto __d1
= std::distance(__first1
, __last1
);
1117 auto __d2
= std::distance(__first2
, __last2
);
1120 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
);
1123 for (; __first1
!= __last1
&& __first2
!= __last2
; ++__first1
, ++__first2
)
1124 if (!(*__first1
== *__first2
))
1126 return __first1
== __last1
&& __first2
== __last2
;
1130 * @brief Tests a range for element-wise equality.
1131 * @ingroup non_mutating_algorithms
1132 * @param __first1 An input iterator.
1133 * @param __last1 An input iterator.
1134 * @param __first2 An input iterator.
1135 * @param __last2 An input iterator.
1136 * @param __binary_pred A binary predicate @link functors
1138 * @return A boolean true or false.
1140 * This compares the elements of two ranges using the binary_pred
1141 * parameter, and returns true or
1142 * false depending on whether all of the corresponding elements of the
1145 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
1147 equal(_IIter1 __first1
, _IIter1 __last1
,
1148 _IIter2 __first2
, _IIter2 __last2
, _BinaryPredicate __binary_pred
)
1150 // concept requirements
1151 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
1152 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
1153 __glibcxx_requires_valid_range(__first1
, __last1
);
1154 __glibcxx_requires_valid_range(__first2
, __last2
);
1156 using _RATag
= random_access_iterator_tag
;
1157 using _Cat1
= typename iterator_traits
<_IIter1
>::iterator_category
;
1158 using _Cat2
= typename iterator_traits
<_IIter2
>::iterator_category
;
1159 using _RAIters
= __and_
<is_same
<_Cat1
, _RATag
>, is_same
<_Cat2
, _RATag
>>;
1162 auto __d1
= std::distance(__first1
, __last1
);
1163 auto __d2
= std::distance(__first2
, __last2
);
1166 return _GLIBCXX_STD_A::equal(__first1
, __last1
, __first2
,
1170 for (; __first1
!= __last1
&& __first2
!= __last2
; ++__first1
, ++__first2
)
1171 if (!bool(__binary_pred(*__first1
, *__first2
)))
1173 return __first1
== __last1
&& __first2
== __last2
;
1178 * @brief Performs @b dictionary comparison on ranges.
1179 * @ingroup sorting_algorithms
1180 * @param __first1 An input iterator.
1181 * @param __last1 An input iterator.
1182 * @param __first2 An input iterator.
1183 * @param __last2 An input iterator.
1184 * @return A boolean true or false.
1186 * <em>Returns true if the sequence of elements defined by the range
1187 * [first1,last1) is lexicographically less than the sequence of elements
1188 * defined by the range [first2,last2). Returns false otherwise.</em>
1189 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1190 * then this is an inline call to @c memcmp.
1192 template<typename _II1
, typename _II2
>
1194 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1195 _II2 __first2
, _II2 __last2
)
1197 #ifdef _GLIBCXX_CONCEPT_CHECKS
1198 // concept requirements
1199 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
1200 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
1202 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1203 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1204 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
1205 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
1206 __glibcxx_requires_valid_range(__first1
, __last1
);
1207 __glibcxx_requires_valid_range(__first2
, __last2
);
1209 return std::__lexicographical_compare_aux(std::__niter_base(__first1
),
1210 std::__niter_base(__last1
),
1211 std::__niter_base(__first2
),
1212 std::__niter_base(__last2
));
1216 * @brief Performs @b dictionary comparison on ranges.
1217 * @ingroup sorting_algorithms
1218 * @param __first1 An input iterator.
1219 * @param __last1 An input iterator.
1220 * @param __first2 An input iterator.
1221 * @param __last2 An input iterator.
1222 * @param __comp A @link comparison_functors comparison functor@endlink.
1223 * @return A boolean true or false.
1225 * The same as the four-parameter @c lexicographical_compare, but uses the
1226 * comp parameter instead of @c <.
1228 template<typename _II1
, typename _II2
, typename _Compare
>
1230 lexicographical_compare(_II1 __first1
, _II1 __last1
,
1231 _II2 __first2
, _II2 __last2
, _Compare __comp
)
1233 // concept requirements
1234 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
1235 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
1236 __glibcxx_requires_valid_range(__first1
, __last1
);
1237 __glibcxx_requires_valid_range(__first2
, __last2
);
1239 return std::__lexicographical_compare_impl
1240 (__first1
, __last1
, __first2
, __last2
,
1241 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
1244 template<typename _InputIterator1
, typename _InputIterator2
,
1245 typename _BinaryPredicate
>
1246 pair
<_InputIterator1
, _InputIterator2
>
1247 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1248 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1250 while (__first1
!= __last1
&& __binary_pred(__first1
, __first2
))
1255 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1259 * @brief Finds the places in ranges which don't match.
1260 * @ingroup non_mutating_algorithms
1261 * @param __first1 An input iterator.
1262 * @param __last1 An input iterator.
1263 * @param __first2 An input iterator.
1264 * @return A pair of iterators pointing to the first mismatch.
1266 * This compares the elements of two ranges using @c == and returns a pair
1267 * of iterators. The first iterator points into the first range, the
1268 * second iterator points into the second range, and the elements pointed
1269 * to by the iterators are not equal.
1271 template<typename _InputIterator1
, typename _InputIterator2
>
1272 pair
<_InputIterator1
, _InputIterator2
>
1273 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1274 _InputIterator2 __first2
)
1276 // concept requirements
1277 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1278 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1279 __glibcxx_function_requires(_EqualOpConcept
<
1280 typename iterator_traits
<_InputIterator1
>::value_type
,
1281 typename iterator_traits
<_InputIterator2
>::value_type
>)
1282 __glibcxx_requires_valid_range(__first1
, __last1
);
1284 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1285 __gnu_cxx::__ops::__iter_equal_to_iter());
1289 * @brief Finds the places in ranges which don't match.
1290 * @ingroup non_mutating_algorithms
1291 * @param __first1 An input iterator.
1292 * @param __last1 An input iterator.
1293 * @param __first2 An input iterator.
1294 * @param __binary_pred A binary predicate @link functors
1296 * @return A pair of iterators pointing to the first mismatch.
1298 * This compares the elements of two ranges using the binary_pred
1299 * parameter, and returns a pair
1300 * of iterators. The first iterator points into the first range, the
1301 * second iterator points into the second range, and the elements pointed
1302 * to by the iterators are not equal.
1304 template<typename _InputIterator1
, typename _InputIterator2
,
1305 typename _BinaryPredicate
>
1306 pair
<_InputIterator1
, _InputIterator2
>
1307 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1308 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1310 // concept requirements
1311 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1312 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1313 __glibcxx_requires_valid_range(__first1
, __last1
);
1315 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
,
1316 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1319 #if __cplusplus > 201103L
1321 template<typename _InputIterator1
, typename _InputIterator2
,
1322 typename _BinaryPredicate
>
1323 pair
<_InputIterator1
, _InputIterator2
>
1324 __mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1325 _InputIterator2 __first2
, _InputIterator2 __last2
,
1326 _BinaryPredicate __binary_pred
)
1328 while (__first1
!= __last1
&& __first2
!= __last2
1329 && __binary_pred(__first1
, __first2
))
1334 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1338 * @brief Finds the places in ranges which don't match.
1339 * @ingroup non_mutating_algorithms
1340 * @param __first1 An input iterator.
1341 * @param __last1 An input iterator.
1342 * @param __first2 An input iterator.
1343 * @param __last2 An input iterator.
1344 * @return A pair of iterators pointing to the first mismatch.
1346 * This compares the elements of two ranges using @c == 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 pair
<_InputIterator1
, _InputIterator2
>
1353 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1354 _InputIterator2 __first2
, _InputIterator2 __last2
)
1356 // concept requirements
1357 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1358 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1359 __glibcxx_function_requires(_EqualOpConcept
<
1360 typename iterator_traits
<_InputIterator1
>::value_type
,
1361 typename iterator_traits
<_InputIterator2
>::value_type
>)
1362 __glibcxx_requires_valid_range(__first1
, __last1
);
1363 __glibcxx_requires_valid_range(__first2
, __last2
);
1365 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1366 __gnu_cxx::__ops::__iter_equal_to_iter());
1370 * @brief Finds the places in ranges which don't match.
1371 * @ingroup non_mutating_algorithms
1372 * @param __first1 An input iterator.
1373 * @param __last1 An input iterator.
1374 * @param __first2 An input iterator.
1375 * @param __last2 An input iterator.
1376 * @param __binary_pred A binary predicate @link functors
1378 * @return A pair of iterators pointing to the first mismatch.
1380 * This compares the elements of two ranges using the binary_pred
1381 * parameter, and returns a pair
1382 * of iterators. The first iterator points into the first range, the
1383 * second iterator points into the second range, and the elements pointed
1384 * to by the iterators are not equal.
1386 template<typename _InputIterator1
, typename _InputIterator2
,
1387 typename _BinaryPredicate
>
1388 pair
<_InputIterator1
, _InputIterator2
>
1389 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1390 _InputIterator2 __first2
, _InputIterator2 __last2
,
1391 _BinaryPredicate __binary_pred
)
1393 // concept requirements
1394 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1395 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1396 __glibcxx_requires_valid_range(__first1
, __last1
);
1397 __glibcxx_requires_valid_range(__first2
, __last2
);
1399 return _GLIBCXX_STD_A::__mismatch(__first1
, __last1
, __first2
, __last2
,
1400 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred
));
1404 _GLIBCXX_END_NAMESPACE_ALGO
1407 // NB: This file is included within many other C++ includes, as a way
1408 // of getting the base algorithms. So, make sure that parallel bits
1409 // come in too if requested.
1410 #ifdef _GLIBCXX_PARALLEL
1411 # include <parallel/algobase.h>