1 // Bits and pieces used in algorithms -*- C++ -*-
3 // Copyright (C) 2001 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 2, 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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
44 * Copyright (c) 1996-1998
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
56 /** @file stl_algobase.h
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
61 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
62 #define __SGI_STL_INTERNAL_ALGOBASE_H
64 #include <bits/c++config.h>
65 #include <bits/stl_pair.h>
66 #include <bits/type_traits.h>
67 #include <bits/std_cstring.h>
68 #include <bits/std_climits.h>
69 #include <bits/std_cstdlib.h>
70 #include <bits/std_cstddef.h>
73 #include <bits/std_iosfwd.h>
74 #include <bits/stl_iterator_base_types.h>
75 #include <bits/stl_iterator_base_funcs.h>
76 #include <bits/stl_iterator.h>
77 #include <bits/concept_check.h>
85 * @brief Swaps the contents of two iterators.
86 * @param a An iterator.
87 * @param b Another iterator.
90 * This function swaps the values pointed to by two iterators, not the
91 * iterators themselves.
93 template<typename _ForwardIter1
, typename _ForwardIter2
>
95 iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
)
97 typedef typename iterator_traits
<_ForwardIter1
>::value_type _ValueType1
;
98 typedef typename iterator_traits
<_ForwardIter2
>::value_type _ValueType2
;
100 // concept requirements
101 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter1
>)
102 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter2
>)
103 __glibcpp_function_requires(_ConvertibleConcept
<_ValueType1
, _ValueType2
>)
104 __glibcpp_function_requires(_ConvertibleConcept
<_ValueType2
, _ValueType1
>)
106 _ValueType1 __tmp
= *__a
;
112 * @brief Swaps two values.
113 * @param a A thing of arbitrary type.
114 * @param b Another thing of arbitrary type.
117 * This is the simple classic generic implementation. It will work on
118 * any type which has a copy constructor and an assignment operator.
120 template<typename _Tp
>
122 swap(_Tp
& __a
, _Tp
& __b
)
124 // concept requirements
125 __glibcpp_function_requires(_SGIAssignableConcept
<_Tp
>)
132 //--------------------------------------------------
139 * @brief This does what you think it does.
140 * @param a A thing of arbitrary type.
141 * @param b Another thing of arbitrary type.
142 * @return The lesser of the parameters.
144 * This is the simple classic generic implementation. It will work on
145 * temporary expressions, since they are only evaluated once, unlike a
146 * preprocessor macro.
148 template<typename _Tp
>
150 min(const _Tp
& __a
, const _Tp
& __b
)
152 // concept requirements
153 __glibcpp_function_requires(_LessThanComparableConcept
<_Tp
>)
154 //return __b < __a ? __b : __a;
155 if (__b
< __a
) return __b
; return __a
;
159 * @brief This does what you think it does.
160 * @param a A thing of arbitrary type.
161 * @param b Another thing of arbitrary type.
162 * @return The greater of the parameters.
164 * This is the simple classic generic implementation. It will work on
165 * temporary expressions, since they are only evaluated once, unlike a
166 * preprocessor macro.
168 template<typename _Tp
>
170 max(const _Tp
& __a
, const _Tp
& __b
)
172 // concept requirements
173 __glibcpp_function_requires(_LessThanComparableConcept
<_Tp
>)
174 //return __a < __b ? __b : __a;
175 if (__a
< __b
) return __b
; return __a
;
179 * @brief This does what you think it does.
180 * @param a A thing of arbitrary type.
181 * @param b Another thing of arbitrary type.
182 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
183 * @return The lesser of the parameters.
185 * This will work on temporary expressions, since they are only evaluated
186 * once, unlike a preprocessor macro.
188 template<typename _Tp
, typename _Compare
>
190 min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
192 //return __comp(__b, __a) ? __b : __a;
193 if (__comp(__b
, __a
)) return __b
; return __a
;
197 * @brief This does what you think it does.
198 * @param a A thing of arbitrary type.
199 * @param b Another thing of arbitrary type.
200 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
201 * @return The greater of the parameters.
203 * This will work on temporary expressions, since they are only evaluated
204 * once, unlike a preprocessor macro.
206 template<typename _Tp
, typename _Compare
>
208 max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
210 //return __comp(__a, __b) ? __b : __a;
211 if (__comp(__a
, __b
)) return __b
; return __a
;
214 //--------------------------------------------------
217 // All of these auxiliary functions serve two purposes. (1) Replace
218 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
219 // because the input and output ranges are permitted to overlap.)
220 // (2) If we're using random access iterators, then write the loop as
221 // a for loop with an explicit count.
223 template<typename _InputIter
, typename _OutputIter
>
225 __copy(_InputIter __first
, _InputIter __last
,
226 _OutputIter __result
,
229 for ( ; __first
!= __last
; ++__result
, ++__first
)
230 *__result
= *__first
;
234 template<typename _RandomAccessIter
, typename _OutputIter
>
236 __copy(_RandomAccessIter __first
, _RandomAccessIter __last
,
237 _OutputIter __result
,
238 random_access_iterator_tag
)
240 typedef typename iterator_traits
<_RandomAccessIter
>::difference_type
242 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
) {
243 *__result
= *__first
;
250 template<typename _Tp
>
252 __copy_trivial(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
254 memmove(__result
, __first
, sizeof(_Tp
) * (__last
- __first
));
255 return __result
+ (__last
- __first
);
258 template<typename _InputIter
, typename _OutputIter
>
260 __copy_aux2(_InputIter __first
, _InputIter __last
,
261 _OutputIter __result
, __false_type
)
262 { return __copy(__first
, __last
, __result
, __iterator_category(__first
)); }
264 template<typename _InputIter
, typename _OutputIter
>
266 __copy_aux2(_InputIter __first
, _InputIter __last
,
267 _OutputIter __result
, __true_type
)
268 { return __copy(__first
, __last
, __result
, __iterator_category(__first
)); }
270 template<typename _Tp
>
272 __copy_aux2(_Tp
* __first
, _Tp
* __last
,
273 _Tp
* __result
, __true_type
)
274 { return __copy_trivial(__first
, __last
, __result
); }
276 template<typename _Tp
>
278 __copy_aux2(const _Tp
* __first
, const _Tp
* __last
,
279 _Tp
* __result
, __true_type
)
280 { return __copy_trivial(__first
, __last
, __result
); }
282 template<typename _InputIter
, typename _OutputIter
>
284 __copy_ni2(_InputIter __first
, _InputIter __last
,
285 _OutputIter __result
, __true_type
)
287 typedef typename iterator_traits
<_InputIter
>::value_type
289 typedef typename __type_traits
<_ValueType
>::has_trivial_assignment_operator
291 return _OutputIter(__copy_aux2(__first
, __last
,
296 template<typename _InputIter
, typename _OutputIter
>
298 __copy_ni2(_InputIter __first
, _InputIter __last
,
299 _OutputIter __result
, __false_type
)
301 typedef typename iterator_traits
<_InputIter
>::value_type
303 typedef typename __type_traits
<_ValueType
>::has_trivial_assignment_operator
305 return __copy_aux2(__first
, __last
,
310 template<typename _InputIter
, typename _OutputIter
>
312 __copy_ni1(_InputIter __first
, _InputIter __last
,
313 _OutputIter __result
, __true_type
)
315 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
316 return __copy_ni2(__first
.base(), __last
.base(), __result
, __Normal());
319 template<typename _InputIter
, typename _OutputIter
>
321 __copy_ni1(_InputIter __first
, _InputIter __last
,
322 _OutputIter __result
, __false_type
)
324 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
325 return __copy_ni2(__first
, __last
, __result
, __Normal());
329 * @brief Copies the range [first,last) into result.
330 * @param first An input iterator.
331 * @param last An input iterator.
332 * @param result An output iterator.
333 * @return result + (first - last)
335 * This inline function will boil down to a call to @c memmove whenever
336 * possible. Failing that, if random access iterators are passed, then the
337 * loop count will be known (and therefore a candidate for compiler
338 * optimizations such as unrolling). If the input range and the output
339 * range overlap, then the copy_backward function should be used instead.
341 template<typename _InputIter
, typename _OutputIter
>
343 copy(_InputIter __first
, _InputIter __last
, _OutputIter __result
)
345 // concept requirements
346 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter
>)
347 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,
348 typename iterator_traits
<_InputIter
>::value_type
>)
350 typedef typename _Is_normal_iterator
<_InputIter
>::_Normal __Normal
;
351 return __copy_ni1(__first
, __last
, __result
, __Normal());
354 //--------------------------------------------------
357 template<typename _BidirectionalIter1
, typename _BidirectionalIter2
>
358 inline _BidirectionalIter2
359 __copy_backward(_BidirectionalIter1 __first
, _BidirectionalIter1 __last
,
360 _BidirectionalIter2 __result
,
361 bidirectional_iterator_tag
)
363 while (__first
!= __last
)
364 *--__result
= *--__last
;
368 template<typename _RandomAccessIter
, typename _BidirectionalIter
>
369 inline _BidirectionalIter
370 __copy_backward(_RandomAccessIter __first
, _RandomAccessIter __last
,
371 _BidirectionalIter __result
,
372 random_access_iterator_tag
)
374 typename iterator_traits
<_RandomAccessIter
>::difference_type __n
;
375 for (__n
= __last
- __first
; __n
> 0; --__n
)
376 *--__result
= *--__last
;
381 // This dispatch class is a workaround for compilers that do not
382 // have partial ordering of function templates. All we're doing is
383 // creating a specialization so that we can turn a call to copy_backward
384 // into a memmove whenever possible.
386 template<typename _BidirectionalIter1
, typename _BidirectionalIter2
,
388 struct __copy_backward_dispatch
390 static _BidirectionalIter2
391 copy(_BidirectionalIter1 __first
, _BidirectionalIter1 __last
,
392 _BidirectionalIter2 __result
)
394 return __copy_backward(__first
, __last
,
396 __iterator_category(__first
));
400 template<typename _Tp
>
401 struct __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
404 copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
406 const ptrdiff_t _Num
= __last
- __first
;
407 memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
408 return __result
- _Num
;
412 template<typename _Tp
>
413 struct __copy_backward_dispatch
<const _Tp
*, _Tp
*, __true_type
>
416 copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
418 return __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
419 ::copy(__first
, __last
, __result
);
423 template<typename _BI1
, typename _BI2
>
425 __copy_backward_aux(_BI1 __first
, _BI1 __last
, _BI2 __result
)
427 typedef typename __type_traits
<typename iterator_traits
<_BI2
>::value_type
>
428 ::has_trivial_assignment_operator _Trivial
;
429 return __copy_backward_dispatch
<_BI1
, _BI2
, _Trivial
>
430 ::copy(__first
, __last
, __result
);
433 template <typename _BI1
, typename _BI2
>
435 __copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
436 _BI2 __result
, __true_type
)
437 { return _BI2(__copy_backward_aux(__first
, __last
, __result
.base())); }
439 template <typename _BI1
, typename _BI2
>
441 __copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
442 _BI2 __result
, __false_type
)
443 { return __copy_backward_aux(__first
, __last
, __result
); }
445 template <typename _BI1
, typename _BI2
>
447 __copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
448 _BI2 __result
, __true_type
)
450 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
451 return __copy_backward_output_normal_iterator(__first
.base(), __last
.base(),
452 __result
, __Normal());
455 template <typename _BI1
, typename _BI2
>
457 __copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
458 _BI2 __result
, __false_type
)
460 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
461 return __copy_backward_output_normal_iterator(__first
, __last
, __result
,
466 * @brief Copies the range [first,last) into result.
467 * @param first An input iterator.
468 * @param last An input iterator.
469 * @param result An output iterator.
470 * @return result - (first - last)
472 * The function has the same effect as copy, but starts at the end of the
473 * range and works its way to the start, returning the start of the result.
474 * This inline function will boil down to a call to @c memmove whenever
475 * possible. Failing that, if random access iterators are passed, then the
476 * loop count will be known (and therefore a candidate for compiler
477 * optimizations such as unrolling).
479 template <typename _BI1
, typename _BI2
>
481 copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
483 // concept requirements
484 __glibcpp_function_requires(_BidirectionalIteratorConcept
<_BI1
>)
485 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>)
486 __glibcpp_function_requires(_ConvertibleConcept
<
487 typename iterator_traits
<_BI1
>::value_type
,
488 typename iterator_traits
<_BI2
>::value_type
>)
490 typedef typename _Is_normal_iterator
<_BI1
>::_Normal __Normal
;
491 return __copy_backward_input_normal_iterator(__first
, __last
, __result
,
495 //--------------------------------------------------
496 // copy_n (not part of the C++ standard)
498 template<typename _InputIter
, typename _Size
, typename _OutputIter
>
499 pair
<_InputIter
, _OutputIter
>
500 __copy_n(_InputIter __first
, _Size __count
,
501 _OutputIter __result
,
504 for ( ; __count
> 0; --__count
) {
505 *__result
= *__first
;
509 return pair
<_InputIter
, _OutputIter
>(__first
, __result
);
512 template<typename _RAIter
, typename _Size
, typename _OutputIter
>
513 inline pair
<_RAIter
, _OutputIter
>
514 __copy_n(_RAIter __first
, _Size __count
,
515 _OutputIter __result
,
516 random_access_iterator_tag
)
518 _RAIter __last
= __first
+ __count
;
519 return pair
<_RAIter
, _OutputIter
>(__last
, copy(__first
, __last
, __result
));
523 * @brief Copies the range [first,first+count) into [result,result+count).
524 * @param first An input iterator.
525 * @param count The number of elements to copy.
526 * @param result An output iterator.
527 * @return A std::pair composed of first+count and result+count.
529 * This is an SGI extension.
530 * This inline function will boil down to a call to @c memmove whenever
531 * possible. Failing that, if random access iterators are passed, then the
532 * loop count will be known (and therefore a candidate for compiler
533 * optimizations such as unrolling).
534 * @ingroup SGIextensions
536 template<typename _InputIter
, typename _Size
, typename _OutputIter
>
537 inline pair
<_InputIter
, _OutputIter
>
538 copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
)
540 // concept requirements
541 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter
>)
542 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,
543 typename iterator_traits
<_InputIter
>::value_type
>)
545 return __copy_n(__first
, __count
, __result
, __iterator_category(__first
));
548 //--------------------------------------------------
553 * @brief Fills the range [first,last) with copies of value.
554 * @param first A forward iterator.
555 * @param last A forward iterator.
556 * @param value A reference-to-const of arbitrary type.
559 * This function fills a range with copies of the same value. For one-byte
560 * types filling contiguous areas of memory, this becomes an inline call to
563 template<typename _ForwardIter
, typename _Tp
>
565 fill(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __value
)
567 // concept requirements
568 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter
>)
570 for ( ; __first
!= __last
; ++__first
)
575 * @brief Fills the range [first,first+n) with copies of value.
576 * @param first An output iterator.
577 * @param n The count of copies to perform.
578 * @param value A reference-to-const of arbitrary type.
579 * @return The iterator at first+n.
581 * This function fills a range with copies of the same value. For one-byte
582 * types filling contiguous areas of memory, this becomes an inline call to
585 template<typename _OutputIter
, typename _Size
, typename _Tp
>
587 fill_n(_OutputIter __first
, _Size __n
, const _Tp
& __value
)
589 // concept requirements
590 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,_Tp
>)
592 for ( ; __n
> 0; --__n
, ++__first
)
597 // Specialization: for one-byte types we can use memset.
600 fill(unsigned char* __first
, unsigned char* __last
, const unsigned char& __c
)
602 unsigned char __tmp
= __c
;
603 memset(__first
, __tmp
, __last
- __first
);
607 fill(signed char* __first
, signed char* __last
, const signed char& __c
)
609 signed char __tmp
= __c
;
610 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
614 fill(char* __first
, char* __last
, const char& __c
)
617 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
620 template<typename _Size
>
621 inline unsigned char*
622 fill_n(unsigned char* __first
, _Size __n
, const unsigned char& __c
)
624 fill(__first
, __first
+ __n
, __c
);
625 return __first
+ __n
;
628 template<typename _Size
>
630 fill_n(char* __first
, _Size __n
, const signed char& __c
)
632 fill(__first
, __first
+ __n
, __c
);
633 return __first
+ __n
;
636 template<typename _Size
>
638 fill_n(char* __first
, _Size __n
, const char& __c
)
640 fill(__first
, __first
+ __n
, __c
);
641 return __first
+ __n
;
645 //--------------------------------------------------
646 // equal and mismatch
649 * @brief Finds the places in ranges which don't match.
650 * @param first1 An input iterator.
651 * @param last1 An input iterator.
652 * @param first2 An input iterator.
653 * @return A pair of iterators pointing to the first mismatch.
655 * This compares the elements of two ranges using @c == and returns a pair
656 * of iterators. The first iterator points into the first range, the
657 * second iterator points into the second range, and the elements pointed
658 * to by the iterators are not equal.
660 template<typename _InputIter1
, typename _InputIter2
>
661 pair
<_InputIter1
, _InputIter2
>
662 mismatch(_InputIter1 __first1
, _InputIter1 __last1
,
663 _InputIter2 __first2
)
665 // concept requirements
666 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
667 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
668 __glibcpp_function_requires(_EqualityComparableConcept
<
669 typename iterator_traits
<_InputIter1
>::value_type
>)
670 __glibcpp_function_requires(_EqualityComparableConcept
<
671 typename iterator_traits
<_InputIter2
>::value_type
>)
673 while (__first1
!= __last1
&& *__first1
== *__first2
) {
677 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
681 * @brief Finds the places in ranges which don't match.
682 * @param first1 An input iterator.
683 * @param last1 An input iterator.
684 * @param first2 An input iterator.
685 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
686 * @return A pair of iterators pointing to the first mismatch.
688 * This compares the elements of two ranges using the binary_pred
689 * parameter, and returns a pair
690 * of iterators. The first iterator points into the first range, the
691 * second iterator points into the second range, and the elements pointed
692 * to by the iterators are not equal.
694 template<typename _InputIter1
, typename _InputIter2
, typename _BinaryPredicate
>
695 pair
<_InputIter1
, _InputIter2
>
696 mismatch(_InputIter1 __first1
, _InputIter1 __last1
,
697 _InputIter2 __first2
,
698 _BinaryPredicate __binary_pred
)
700 // concept requirements
701 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
702 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
704 while (__first1
!= __last1
&& __binary_pred(*__first1
, *__first2
)) {
708 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
712 * @brief Tests a range for element-wise equality.
713 * @param first1 An input iterator.
714 * @param last1 An input iterator.
715 * @param first2 An input iterator.
716 * @return A boolean true or false.
718 * This compares the elements of two ranges using @c == and returns true or
719 * false depending on whether all of the corresponding elements of the
722 template<typename _InputIter1
, typename _InputIter2
>
724 equal(_InputIter1 __first1
, _InputIter1 __last1
,
725 _InputIter2 __first2
)
727 // concept requirements
728 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
729 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
730 __glibcpp_function_requires(_EqualOpConcept
<
731 typename iterator_traits
<_InputIter1
>::value_type
,
732 typename iterator_traits
<_InputIter2
>::value_type
>)
734 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
735 if (!(*__first1
== *__first2
))
741 * @brief Tests a range for element-wise equality.
742 * @param first1 An input iterator.
743 * @param last1 An input iterator.
744 * @param first2 An input iterator.
745 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
746 * @return A boolean true or false.
748 * This compares the elements of two ranges using the binary_pred
749 * parameter, and returns true or
750 * false depending on whether all of the corresponding elements of the
753 template<typename _InputIter1
, typename _InputIter2
, typename _BinaryPredicate
>
755 equal(_InputIter1 __first1
, _InputIter1 __last1
,
756 _InputIter2 __first2
,
757 _BinaryPredicate __binary_pred
)
759 // concept requirements
760 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
761 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
763 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
764 if (!__binary_pred(*__first1
, *__first2
))
769 //--------------------------------------------------
770 // lexicographical_compare and lexicographical_compare_3way.
771 // (the latter is not part of the C++ standard.)
774 * @brief Performs "dictionary" comparison on ranges.
775 * @param first1 An input iterator.
776 * @param last1 An input iterator.
777 * @param first2 An input iterator.
778 * @param last2 An input iterator.
779 * @return A boolean true or false.
781 * "Returns true if the sequence of elements defined by the range
782 * [first1,last1) is lexicographically less than the sequence of elements
783 * defined by the range [first2,last2). Returns false otherwise."
784 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
785 * then this is an inline call to @c memcmp.
787 template<typename _InputIter1
, typename _InputIter2
>
789 lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
790 _InputIter2 __first2
, _InputIter2 __last2
)
792 // concept requirements
793 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
794 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
795 __glibcpp_function_requires(_LessThanComparableConcept
<
796 typename iterator_traits
<_InputIter1
>::value_type
>)
797 __glibcpp_function_requires(_LessThanComparableConcept
<
798 typename iterator_traits
<_InputIter2
>::value_type
>)
800 for ( ; __first1
!= __last1
&& __first2
!= __last2
801 ; ++__first1
, ++__first2
) {
802 if (*__first1
< *__first2
)
804 if (*__first2
< *__first1
)
807 return __first1
== __last1
&& __first2
!= __last2
;
811 * @brief Performs "dictionary" comparison on ranges.
812 * @param first1 An input iterator.
813 * @param last1 An input iterator.
814 * @param first2 An input iterator.
815 * @param last2 An input iterator.
816 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
817 * @return A boolean true or false.
819 * The same as the four-parameter @c lexigraphical_compare, but uses the
820 * comp parameter instead of @c <.
822 template<typename _InputIter1
, typename _InputIter2
, typename _Compare
>
824 lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
825 _InputIter2 __first2
, _InputIter2 __last2
,
828 // concept requirements
829 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
830 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
832 for ( ; __first1
!= __last1
&& __first2
!= __last2
833 ; ++__first1
, ++__first2
) {
834 if (__comp(*__first1
, *__first2
))
836 if (__comp(*__first2
, *__first1
))
839 return __first1
== __last1
&& __first2
!= __last2
;
843 lexicographical_compare(const unsigned char* __first1
, const unsigned char* __last1
,
844 const unsigned char* __first2
, const unsigned char* __last2
)
846 const size_t __len1
= __last1
- __first1
;
847 const size_t __len2
= __last2
- __first2
;
848 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
849 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
853 lexicographical_compare(const char* __first1
, const char* __last1
,
854 const char* __first2
, const char* __last2
)
856 #if CHAR_MAX == SCHAR_MAX
857 return lexicographical_compare((const signed char*) __first1
,
858 (const signed char*) __last1
,
859 (const signed char*) __first2
,
860 (const signed char*) __last2
);
861 #else /* CHAR_MAX == SCHAR_MAX */
862 return lexicographical_compare((const unsigned char*) __first1
,
863 (const unsigned char*) __last1
,
864 (const unsigned char*) __first2
,
865 (const unsigned char*) __last2
);
866 #endif /* CHAR_MAX == SCHAR_MAX */
869 template<typename _InputIter1
, typename _InputIter2
>
871 __lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
872 _InputIter2 __first2
, _InputIter2 __last2
)
874 while (__first1
!= __last1
&& __first2
!= __last2
) {
875 if (*__first1
< *__first2
)
877 if (*__first2
< *__first1
)
882 if (__first2
== __last2
) {
883 return !(__first1
== __last1
);
891 __lexicographical_compare_3way(const unsigned char* __first1
,
892 const unsigned char* __last1
,
893 const unsigned char* __first2
,
894 const unsigned char* __last2
)
896 const ptrdiff_t __len1
= __last1
- __first1
;
897 const ptrdiff_t __len2
= __last2
- __first2
;
898 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
899 return __result
!= 0 ? __result
900 : (__len1
== __len2
? 0 : (__len1
< __len2
? -1 : 1));
904 __lexicographical_compare_3way(const char* __first1
, const char* __last1
,
905 const char* __first2
, const char* __last2
)
907 #if CHAR_MAX == SCHAR_MAX
908 return __lexicographical_compare_3way(
909 (const signed char*) __first1
,
910 (const signed char*) __last1
,
911 (const signed char*) __first2
,
912 (const signed char*) __last2
);
914 return __lexicographical_compare_3way((const unsigned char*) __first1
,
915 (const unsigned char*) __last1
,
916 (const unsigned char*) __first2
,
917 (const unsigned char*) __last2
);
922 * @brief @c memcmp on steroids.
923 * @param first1 An input iterator.
924 * @param last1 An input iterator.
925 * @param first2 An input iterator.
926 * @param last2 An input iterator.
927 * @return An int, as with @c memcmp.
929 * The return value will be less than zero if the first range is
930 * "lexigraphically less than" the second, greater than zero if the second
931 * range is "lexigraphically less than" the first, and zero otherwise.
932 * This is an SGI extension.
933 * @ingroup SGIextensions
935 template<typename _InputIter1
, typename _InputIter2
>
937 lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
938 _InputIter2 __first2
, _InputIter2 __last2
)
940 // concept requirements
941 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>)
942 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>)
943 __glibcpp_function_requires(_LessThanComparableConcept
<
944 typename iterator_traits
<_InputIter1
>::value_type
>)
945 __glibcpp_function_requires(_LessThanComparableConcept
<
946 typename iterator_traits
<_InputIter2
>::value_type
>)
948 return __lexicographical_compare_3way(__first1
, __last1
, __first2
, __last2
);
953 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */