1 // Bits and pieces used in algorithms -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
45 * Copyright (c) 1996-1998
46 * Silicon Graphics Computer Systems, Inc.
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
57 /** @file stl_algobase.h
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
62 #ifndef _STL_ALGOBASE_H
63 #define _STL_ALGOBASE_H 1
65 #include <bits/c++config.h>
67 #include <bits/functexcept.h>
68 #include <bits/cpp_type_traits.h>
69 #include <ext/type_traits.h>
70 #include <ext/numeric_traits.h>
71 #include <bits/algorithmfwd.h>
72 #include <bits/stl_iterator_base_funcs.h>
73 #include <bits/stl_iterator.h>
74 #include <bits/concept_check.h>
75 #include <debug/debug.h>
77 _GLIBCXX_BEGIN_NAMESPACE(std
)
80 * @brief Swaps two values.
81 * @param a A thing of arbitrary type.
82 * @param b Another thing of arbitrary type.
85 * This is the simple classic generic implementation. It will work on
86 * any type which has a copy constructor and an assignment operator.
88 template<typename _Tp
>
90 swap(_Tp
& __a
, _Tp
& __b
)
92 // concept requirements
93 __glibcxx_function_requires(_SGIAssignableConcept
<_Tp
>)
100 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
101 // nutshell, we are partially implementing the resolution of DR 187,
102 // when it's safe, i.e., the value_types are equal.
103 template<bool _BoolType
>
106 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
108 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
110 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
112 _ValueType1 __tmp
= *__a
;
119 struct __iter_swap
<true>
121 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
123 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
130 * @brief Swaps the contents of two iterators.
131 * @param a An iterator.
132 * @param b Another iterator.
135 * This function swaps the values pointed to by two iterators, not the
136 * iterators themselves.
138 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
140 iter_swap(_ForwardIterator1 __a
, _ForwardIterator2 __b
)
142 typedef typename iterator_traits
<_ForwardIterator1
>::value_type
144 typedef typename iterator_traits
<_ForwardIterator2
>::value_type
147 // concept requirements
148 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
150 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
152 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType1
,
154 __glibcxx_function_requires(_ConvertibleConcept
<_ValueType2
,
157 typedef typename iterator_traits
<_ForwardIterator1
>::reference
159 typedef typename iterator_traits
<_ForwardIterator2
>::reference
161 std::__iter_swap
<__are_same
<_ValueType1
, _ValueType2
>::__value
162 && __are_same
<_ValueType1
&, _ReferenceType1
>::__value
163 && __are_same
<_ValueType2
&, _ReferenceType2
>::__value
>::
168 * @brief Swap the elements of two sequences.
169 * @param first1 A forward iterator.
170 * @param last1 A forward iterator.
171 * @param first2 A forward iterator.
172 * @return An iterator equal to @p first2+(last1-first1).
174 * Swaps each element in the range @p [first1,last1) with the
175 * corresponding element in the range @p [first2,(last1-first1)).
176 * The ranges must not overlap.
178 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
180 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
181 _ForwardIterator2 __first2
)
183 // concept requirements
184 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
186 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
188 __glibcxx_function_requires(_ConvertibleConcept
<
189 typename iterator_traits
<_ForwardIterator1
>::value_type
,
190 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
191 __glibcxx_function_requires(_ConvertibleConcept
<
192 typename iterator_traits
<_ForwardIterator2
>::value_type
,
193 typename iterator_traits
<_ForwardIterator1
>::value_type
>)
194 __glibcxx_requires_valid_range(__first1
, __last1
);
196 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
197 std::iter_swap(__first1
, __first2
);
202 * @brief This does what you think it does.
203 * @param a A thing of arbitrary type.
204 * @param b Another thing of arbitrary type.
205 * @return The lesser of the parameters.
207 * This is the simple classic generic implementation. It will work on
208 * temporary expressions, since they are only evaluated once, unlike a
209 * preprocessor macro.
211 template<typename _Tp
>
213 min(const _Tp
& __a
, const _Tp
& __b
)
215 // concept requirements
216 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
217 //return __b < __a ? __b : __a;
224 * @brief This does what you think it does.
225 * @param a A thing of arbitrary type.
226 * @param b Another thing of arbitrary type.
227 * @return The greater of the parameters.
229 * This is the simple classic generic implementation. It will work on
230 * temporary expressions, since they are only evaluated once, unlike a
231 * preprocessor macro.
233 template<typename _Tp
>
235 max(const _Tp
& __a
, const _Tp
& __b
)
237 // concept requirements
238 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
239 //return __a < __b ? __b : __a;
246 * @brief This does what you think it does.
247 * @param a A thing of arbitrary type.
248 * @param b Another thing of arbitrary type.
249 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
250 * @return The lesser of the parameters.
252 * This will work on temporary expressions, since they are only evaluated
253 * once, unlike a preprocessor macro.
255 template<typename _Tp
, typename _Compare
>
257 min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
259 //return __comp(__b, __a) ? __b : __a;
260 if (__comp(__b
, __a
))
266 * @brief This does what you think it does.
267 * @param a A thing of arbitrary type.
268 * @param b Another thing of arbitrary type.
269 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
270 * @return The greater of the parameters.
272 * This will work on temporary expressions, since they are only evaluated
273 * once, unlike a preprocessor macro.
275 template<typename _Tp
, typename _Compare
>
277 max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
279 //return __comp(__a, __b) ? __b : __a;
280 if (__comp(__a
, __b
))
286 // If _Iterator is a __normal_iterator return its base (a plain pointer,
287 // normally) otherwise return it untouched. See copy, fill, ...
288 template<typename _Iterator
,
289 bool _BoolType
= __is_normal_iterator
<_Iterator
>::__value
>
292 static const _Iterator
&
293 __b(const _Iterator
& __it
)
297 template<typename _Iterator
>
298 struct __niter_base
<_Iterator
, true>
300 static const typename
_Iterator::_Iterator_type
&
301 __b(const _Iterator
& __it
)
302 { return __it
.base(); }
305 // All of these auxiliary structs serve two purposes. (1) Replace
306 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
307 // because the input and output ranges are permitted to overlap.)
308 // (2) If we're using random access iterators, then write the loop as
309 // a for loop with an explicit count.
311 template<bool, typename
>
314 template<typename _II
, typename _OI
>
316 copy(_II __first
, _II __last
, _OI __result
)
318 for (; __first
!= __last
; ++__result
, ++__first
)
319 *__result
= *__first
;
324 template<bool _BoolType
>
325 struct __copy
<_BoolType
, random_access_iterator_tag
>
327 template<typename _II
, typename _OI
>
329 copy(_II __first
, _II __last
, _OI __result
)
331 typedef typename iterator_traits
<_II
>::difference_type _Distance
;
332 for(_Distance __n
= __last
- __first
; __n
> 0; --__n
)
334 *__result
= *__first
;
343 struct __copy
<true, random_access_iterator_tag
>
345 template<typename _Tp
>
347 copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
349 __builtin_memmove(__result
, __first
,
350 sizeof(_Tp
) * (__last
- __first
));
351 return __result
+ (__last
- __first
);
355 template<typename _II
, typename _OI
>
357 __copy_aux(_II __first
, _II __last
, _OI __result
)
359 typedef typename iterator_traits
<_II
>::value_type _ValueTypeI
;
360 typedef typename iterator_traits
<_OI
>::value_type _ValueTypeO
;
361 typedef typename iterator_traits
<_II
>::iterator_category _Category
;
362 const bool __simple
= (__is_pod(_ValueTypeI
)
363 && __is_pointer
<_II
>::__value
364 && __is_pointer
<_OI
>::__value
365 && __are_same
<_ValueTypeI
, _ValueTypeO
>::__value
);
367 return std::__copy
<__simple
, _Category
>::copy(__first
, __last
, __result
);
370 // Helpers for streambuf iterators (either istream or ostream).
371 // NB: avoid including <iosfwd>, relatively large.
372 template<typename _CharT
>
375 template<typename _CharT
, typename _Traits
>
376 class istreambuf_iterator
;
378 template<typename _CharT
, typename _Traits
>
379 class ostreambuf_iterator
;
381 template<typename _CharT
>
382 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
383 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
384 __copy_aux(_CharT
*, _CharT
*,
385 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
387 template<typename _CharT
>
388 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
389 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> > >::__type
390 __copy_aux(const _CharT
*, const _CharT
*,
391 ostreambuf_iterator
<_CharT
, char_traits
<_CharT
> >);
393 template<typename _CharT
>
394 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
396 __copy_aux(istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >,
397 istreambuf_iterator
<_CharT
, char_traits
<_CharT
> >, _CharT
*);
400 * @brief Copies the range [first,last) into result.
401 * @param first An input iterator.
402 * @param last An input iterator.
403 * @param result An output iterator.
404 * @return result + (first - last)
406 * This inline function will boil down to a call to @c memmove whenever
407 * possible. Failing that, if random access iterators are passed, then the
408 * loop count will be known (and therefore a candidate for compiler
409 * optimizations such as unrolling). Result may not be contained within
410 * [first,last); the copy_backward function should be used instead.
412 * Note that the end of the output range is permitted to be contained
413 * within [first,last).
415 template<typename _II
, typename _OI
>
417 copy(_II __first
, _II __last
, _OI __result
)
419 // concept requirements
420 __glibcxx_function_requires(_InputIteratorConcept
<_II
>)
421 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
,
422 typename iterator_traits
<_II
>::value_type
>)
423 __glibcxx_requires_valid_range(__first
, __last
);
425 return _OI(std::__copy_aux(__niter_base
<_II
>::__b(__first
),
426 __niter_base
<_II
>::__b(__last
),
427 __niter_base
<_OI
>::__b(__result
)));
431 template<bool, typename
>
432 struct __copy_backward
434 template<typename _BI1
, typename _BI2
>
436 __copy_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
438 while (__first
!= __last
)
439 *--__result
= *--__last
;
444 template<bool _BoolType
>
445 struct __copy_backward
<_BoolType
, random_access_iterator_tag
>
447 template<typename _BI1
, typename _BI2
>
449 __copy_b(_BI1 __first
, _BI1 __last
, _BI2 __result
)
451 typename iterator_traits
<_BI1
>::difference_type __n
;
452 for (__n
= __last
- __first
; __n
> 0; --__n
)
453 *--__result
= *--__last
;
459 struct __copy_backward
<true, random_access_iterator_tag
>
461 template<typename _Tp
>
463 __copy_b(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
465 const ptrdiff_t _Num
= __last
- __first
;
466 __builtin_memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
467 return __result
- _Num
;
471 template<typename _BI1
, typename _BI2
>
473 __copy_backward_aux(_BI1 __first
, _BI1 __last
, _BI2 __result
)
475 typedef typename iterator_traits
<_BI1
>::value_type _ValueType1
;
476 typedef typename iterator_traits
<_BI2
>::value_type _ValueType2
;
477 typedef typename iterator_traits
<_BI1
>::iterator_category _Category
;
478 const bool __simple
= (__is_pod(_ValueType1
)
479 && __is_pointer
<_BI1
>::__value
480 && __is_pointer
<_BI2
>::__value
481 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
483 return std::__copy_backward
<__simple
, _Category
>::__copy_b(__first
,
489 * @brief Copies the range [first,last) into result.
490 * @param first A bidirectional iterator.
491 * @param last A bidirectional iterator.
492 * @param result A bidirectional iterator.
493 * @return result - (first - last)
495 * The function has the same effect as copy, but starts at the end of the
496 * range and works its way to the start, returning the start of the result.
497 * This inline function will boil down to a call to @c memmove whenever
498 * possible. Failing that, if random access iterators are passed, then the
499 * loop count will be known (and therefore a candidate for compiler
500 * optimizations such as unrolling).
502 * Result may not be in the range [first,last). Use copy instead. Note
503 * that the start of the output range may overlap [first,last).
505 template <typename _BI1
, typename _BI2
>
507 copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
509 // concept requirements
510 __glibcxx_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
511 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
512 __glibcxx_function_requires(_ConvertibleConcept
<
513 typename iterator_traits
<_BI1
>::value_type
,
514 typename iterator_traits
<_BI2
>::value_type
>)
515 __glibcxx_requires_valid_range(__first
, __last
);
517 return _BI2(std::__copy_backward_aux(__niter_base
<_BI1
>::__b(__first
),
518 __niter_base
<_BI1
>::__b(__last
),
519 __niter_base
<_BI2
>::__b(__result
)));
526 template<typename _ForwardIterator
, typename _Tp
>
528 fill(_ForwardIterator __first
, _ForwardIterator __last
,
531 for (; __first
!= __last
; ++__first
)
539 template<typename _ForwardIterator
, typename _Tp
>
541 fill(_ForwardIterator __first
, _ForwardIterator __last
,
544 const _Tp __tmp
= __value
;
545 for (; __first
!= __last
; ++__first
)
550 template<typename _ForwardIterator
, typename _Tp
>
552 __fill_aux(_ForwardIterator __first
, _ForwardIterator __last
,
555 const bool __scalar
= __is_scalar
<_Tp
>::__value
;
556 std::__fill
<__scalar
>::fill(__first
, __last
, __value
);
559 // Specialization: for char types we can use memset.
561 __fill_aux(unsigned char* __first
, unsigned char* __last
, unsigned char __c
)
562 { __builtin_memset(__first
, __c
, __last
- __first
); }
565 __fill_aux(signed char* __first
, signed char* __last
, signed char __c
)
566 { __builtin_memset(__first
, static_cast<unsigned char>(__c
),
570 __fill_aux(char* __first
, char* __last
, char __c
)
571 { __builtin_memset(__first
, static_cast<unsigned char>(__c
),
575 * @brief Fills the range [first,last) with copies of value.
576 * @param first A forward iterator.
577 * @param last A forward iterator.
578 * @param value A reference-to-const of arbitrary type.
581 * This function fills a range with copies of the same value. For char
582 * types filling contiguous areas of memory, this becomes an inline call
583 * to @c memset or @c wmemset.
585 template<typename _ForwardIterator
, typename _Tp
>
587 fill(_ForwardIterator __first
, _ForwardIterator __last
, const _Tp
& __value
)
589 // concept requirements
590 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
592 __glibcxx_requires_valid_range(__first
, __last
);
594 std::__fill_aux(__niter_base
<_ForwardIterator
>::__b(__first
),
595 __niter_base
<_ForwardIterator
>::__b(__last
), __value
);
601 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
602 static _OutputIterator
603 fill_n(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
605 for (; __n
> 0; --__n
, ++__first
)
612 struct __fill_n
<true>
614 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
615 static _OutputIterator
616 fill_n(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
618 const _Tp __tmp
= __value
;
619 for (; __n
> 0; --__n
, ++__first
)
625 template<typename _OutputIterator
, typename _Size
, typename _Tp
>
626 inline _OutputIterator
627 __fill_n_aux(_OutputIterator __first
, _Size __n
, const _Tp
& __value
)
629 const bool __scalar
= __is_scalar
<_Tp
>::__value
;
630 return std::__fill_n
<__scalar
>::fill_n(__first
, __n
, __value
);
633 template<typename _Size
>
634 inline unsigned char*
635 __fill_n_aux(unsigned char* __first
, _Size __n
, unsigned char __c
)
637 std::__fill_aux(__first
, __first
+ __n
, __c
);
638 return __first
+ __n
;
641 template<typename _Size
>
643 __fill_n_aux(signed char* __first
, _Size __n
, signed char __c
)
645 std::__fill_aux(__first
, __first
+ __n
, __c
);
646 return __first
+ __n
;
649 template<typename _Size
>
651 __fill_n_aux(char* __first
, _Size __n
, char __c
)
653 std::__fill_aux(__first
, __first
+ __n
, __c
);
654 return __first
+ __n
;
658 * @brief Fills the range [first,first+n) with copies of value.
659 * @param first An output iterator.
660 * @param n The count of copies to perform.
661 * @param value A reference-to-const of arbitrary type.
662 * @return The iterator at first+n.
664 * This function fills a range with copies of the same value. For char
665 * types filling contiguous areas of memory, this becomes an inline call
666 * to @c memset or @ wmemset.
668 template<typename _OI
, typename _Size
, typename _Tp
>
670 fill_n(_OI __first
, _Size __n
, const _Tp
& __value
)
672 // concept requirements
673 __glibcxx_function_requires(_OutputIteratorConcept
<_OI
, _Tp
>)
675 return _OI(std::__fill_n_aux(__niter_base
<_OI
>::__b(__first
), __n
,
679 template<bool _BoolType
>
682 template<typename _II1
, typename _II2
>
684 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
686 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
687 if (!(*__first1
== *__first2
))
696 template<typename _Tp
>
698 equal(const _Tp
* __first1
, const _Tp
* __last1
, const _Tp
* __first2
)
700 return !__builtin_memcmp(__first1
, __first2
, sizeof(_Tp
)
701 * (__last1
- __first1
));
705 template<typename _II1
, typename _II2
>
707 __equal_aux(_II1 __first1
, _II1 __last1
, _II2 __first2
)
709 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
710 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
711 const bool __simple
= (__is_integer
<_ValueType1
>::__value
712 && __is_pointer
<_II1
>::__value
713 && __is_pointer
<_II2
>::__value
714 && __are_same
<_ValueType1
, _ValueType2
>::__value
);
716 return std::__equal
<__simple
>::equal(__first1
, __last1
, __first2
);
720 template<typename
, typename
>
723 template<typename _II1
, typename _II2
>
725 __newlast1(_II1
, _II1 __last1
, _II2
, _II2
)
728 template<typename _II
>
730 __cnd2(_II __first
, _II __last
)
731 { return __first
!= __last
; }
735 struct __lc_rai
<random_access_iterator_tag
, random_access_iterator_tag
>
737 template<typename _RAI1
, typename _RAI2
>
739 __newlast1(_RAI1 __first1
, _RAI1 __last1
,
740 _RAI2 __first2
, _RAI2 __last2
)
742 const typename iterator_traits
<_RAI1
>::difference_type
743 __diff1
= __last1
- __first1
;
744 const typename iterator_traits
<_RAI2
>::difference_type
745 __diff2
= __last2
- __first2
;
746 return __diff2
< __diff1
? __first1
+ __diff2
: __last1
;
749 template<typename _RAI
>
755 // XXX should these be enabled-if'd for signed/unsigned types instead?
757 lexicographical_compare(const unsigned char* __first1
,
758 const unsigned char* __last1
,
759 const unsigned char* __first2
,
760 const unsigned char* __last2
)
762 __glibcxx_requires_valid_range(__first1
, __last1
);
763 __glibcxx_requires_valid_range(__first2
, __last2
);
765 const size_t __len1
= __last1
- __first1
;
766 const size_t __len2
= __last2
- __first2
;
767 const int __result
= __builtin_memcmp(__first1
, __first2
,
768 std::min(__len1
, __len2
));
769 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
773 lexicographical_compare(const char* __first1
, const char* __last1
,
774 const char* __first2
, const char* __last2
)
776 __glibcxx_requires_valid_range(__first1
, __last1
);
777 __glibcxx_requires_valid_range(__first2
, __last2
);
779 if (__gnu_cxx::__numeric_traits
<char>::__is_signed
)
781 typedef const signed char* value_type
;
782 value_type __f1
= reinterpret_cast<value_type
>(__first1
);
783 value_type __l1
= reinterpret_cast<value_type
>(__last1
);
784 value_type __f2
= reinterpret_cast<value_type
>(__first2
);
785 value_type __l2
= reinterpret_cast<value_type
>(__last2
);
786 return _GLIBCXX_STD_P::lexicographical_compare(__f1
, __l1
, __f2
, __l2
);
790 typedef const unsigned char* value_type
;
791 value_type __f1
= reinterpret_cast<value_type
>(__first1
);
792 value_type __l1
= reinterpret_cast<value_type
>(__last1
);
793 value_type __f2
= reinterpret_cast<value_type
>(__first2
);
794 value_type __l2
= reinterpret_cast<value_type
>(__last2
);
795 return _GLIBCXX_STD_P::lexicographical_compare(__f1
, __l1
, __f2
, __l2
);
799 _GLIBCXX_END_NAMESPACE
801 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std
, _GLIBCXX_STD_P
)
804 * @brief Tests a range for element-wise equality.
805 * @param first1 An input iterator.
806 * @param last1 An input iterator.
807 * @param first2 An input iterator.
808 * @return A boolean true or false.
810 * This compares the elements of two ranges using @c == and returns true or
811 * false depending on whether all of the corresponding elements of the
814 template<typename _II1
, typename _II2
>
816 equal(_II1 __first1
, _II1 __last1
, _II2 __first2
)
818 // concept requirements
819 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
820 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
821 __glibcxx_function_requires(_EqualOpConcept
<
822 typename iterator_traits
<_II1
>::value_type
,
823 typename iterator_traits
<_II2
>::value_type
>)
824 __glibcxx_requires_valid_range(__first1
, __last1
);
826 return std::__equal_aux(__niter_base
<_II1
>::__b(__first1
),
827 __niter_base
<_II1
>::__b(__last1
),
828 __niter_base
<_II2
>::__b(__first2
));
832 * @brief Tests a range for element-wise equality.
833 * @param first1 An input iterator.
834 * @param last1 An input iterator.
835 * @param first2 An input iterator.
836 * @param binary_pred A binary predicate @link s20_3_1_base
838 * @return A boolean true or false.
840 * This compares the elements of two ranges using the binary_pred
841 * parameter, and returns true or
842 * false depending on whether all of the corresponding elements of the
845 template<typename _IIter1
, typename _IIter2
, typename _BinaryPredicate
>
847 equal(_IIter1 __first1
, _IIter1 __last1
,
848 _IIter2 __first2
, _BinaryPredicate __binary_pred
)
850 // concept requirements
851 __glibcxx_function_requires(_InputIteratorConcept
<_IIter1
>)
852 __glibcxx_function_requires(_InputIteratorConcept
<_IIter2
>)
853 __glibcxx_requires_valid_range(__first1
, __last1
);
855 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
856 if (!bool(__binary_pred(*__first1
, *__first2
)))
862 * @brief Performs "dictionary" comparison on ranges.
863 * @param first1 An input iterator.
864 * @param last1 An input iterator.
865 * @param first2 An input iterator.
866 * @param last2 An input iterator.
867 * @return A boolean true or false.
869 * "Returns true if the sequence of elements defined by the range
870 * [first1,last1) is lexicographically less than the sequence of elements
871 * defined by the range [first2,last2). Returns false otherwise."
872 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
873 * then this is an inline call to @c memcmp.
875 template<typename _II1
, typename _II2
>
877 lexicographical_compare(_II1 __first1
, _II1 __last1
,
878 _II2 __first2
, _II2 __last2
)
880 typedef typename iterator_traits
<_II1
>::iterator_category _Category1
;
881 typedef typename iterator_traits
<_II2
>::iterator_category _Category2
;
883 // concept requirements
884 typedef typename iterator_traits
<_II1
>::value_type _ValueType1
;
885 typedef typename iterator_traits
<_II2
>::value_type _ValueType2
;
886 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
887 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
888 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
889 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
890 __glibcxx_requires_valid_range(__first1
, __last1
);
891 __glibcxx_requires_valid_range(__first2
, __last2
);
893 __last1
= __lc_rai
<_Category1
, _Category2
>::__newlast1(__first1
,
897 for (; __first1
!= __last1
898 && __lc_rai
<_Category1
, _Category2
>::__cnd2(__first2
, __last2
);
899 ++__first1
, ++__first2
)
901 if (*__first1
< *__first2
)
903 if (*__first2
< *__first1
)
906 return __first1
== __last1
&& __first2
!= __last2
;
910 * @brief Performs "dictionary" comparison on ranges.
911 * @param first1 An input iterator.
912 * @param last1 An input iterator.
913 * @param first2 An input iterator.
914 * @param last2 An input iterator.
915 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
916 * @return A boolean true or false.
918 * The same as the four-parameter @c lexicographical_compare, but uses the
919 * comp parameter instead of @c <.
921 template<typename _II1
, typename _II2
, typename _Compare
>
923 lexicographical_compare(_II1 __first1
, _II1 __last1
,
924 _II2 __first2
, _II2 __last2
, _Compare __comp
)
926 typedef typename iterator_traits
<_II1
>::iterator_category _Category1
;
927 typedef typename iterator_traits
<_II2
>::iterator_category _Category2
;
928 typedef __lc_rai
<_Category1
, _Category2
> __rai_type
;
930 // concept requirements
931 __glibcxx_function_requires(_InputIteratorConcept
<_II1
>)
932 __glibcxx_function_requires(_InputIteratorConcept
<_II2
>)
933 __glibcxx_requires_valid_range(__first1
, __last1
);
934 __glibcxx_requires_valid_range(__first2
, __last2
);
936 __last1
= __rai_type::__newlast1(__first1
, __last1
, __first2
, __last2
);
937 for (; __first1
!= __last1
&& __rai_type::__cnd2(__first2
, __last2
);
938 ++__first1
, ++__first2
)
940 if (__comp(*__first1
, *__first2
))
942 if (__comp(*__first2
, *__first1
))
945 return __first1
== __last1
&& __first2
!= __last2
;
950 * @brief Finds the places in ranges which don't match.
951 * @param first1 An input iterator.
952 * @param last1 An input iterator.
953 * @param first2 An input iterator.
954 * @return A pair of iterators pointing to the first mismatch.
956 * This compares the elements of two ranges using @c == and returns a pair
957 * of iterators. The first iterator points into the first range, the
958 * second iterator points into the second range, and the elements pointed
959 * to by the iterators are not equal.
961 template<typename _InputIterator1
, typename _InputIterator2
>
962 pair
<_InputIterator1
, _InputIterator2
>
963 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
964 _InputIterator2 __first2
)
966 // concept requirements
967 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
968 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
969 __glibcxx_function_requires(_EqualOpConcept
<
970 typename iterator_traits
<_InputIterator1
>::value_type
,
971 typename iterator_traits
<_InputIterator2
>::value_type
>)
972 __glibcxx_requires_valid_range(__first1
, __last1
);
974 while (__first1
!= __last1
&& *__first1
== *__first2
)
979 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
983 * @brief Finds the places in ranges which don't match.
984 * @param first1 An input iterator.
985 * @param last1 An input iterator.
986 * @param first2 An input iterator.
987 * @param binary_pred A binary predicate @link s20_3_1_base
989 * @return A pair of iterators pointing to the first mismatch.
991 * This compares the elements of two ranges using the binary_pred
992 * parameter, and returns a pair
993 * of iterators. The first iterator points into the first range, the
994 * second iterator points into the second range, and the elements pointed
995 * to by the iterators are not equal.
997 template<typename _InputIterator1
, typename _InputIterator2
,
998 typename _BinaryPredicate
>
999 pair
<_InputIterator1
, _InputIterator2
>
1000 mismatch(_InputIterator1 __first1
, _InputIterator1 __last1
,
1001 _InputIterator2 __first2
, _BinaryPredicate __binary_pred
)
1003 // concept requirements
1004 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
1005 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
1006 __glibcxx_requires_valid_range(__first1
, __last1
);
1008 while (__first1
!= __last1
&& bool(__binary_pred(*__first1
, *__first2
)))
1013 return pair
<_InputIterator1
, _InputIterator2
>(__first1
, __first2
);
1016 _GLIBCXX_END_NESTED_NAMESPACE
1018 // NB: This file is included within many other C++ includes, as a way
1019 // of getting the base algorithms. So, make sure that parallel bits
1020 // come in too if requested.
1021 #ifdef _GLIBCXX_PARALLEL
1022 //# include <parallel/algorithm>
1023 # include <parallel/algobase.h>