stl_algobase.h revision 97403
1// Bits and pieces used in algorithms -*- C++ -*- 2 3// Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// 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, 19// USA. 20 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. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 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. 42 * 43 * 44 * Copyright (c) 1996-1998 45 * Silicon Graphics Computer Systems, Inc. 46 * 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. 54 */ 55 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. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_ALGOBASE_H 62#define __GLIBCPP_INTERNAL_ALGOBASE_H 63 64#include <bits/c++config.h> 65#include <cstring> 66#include <climits> 67#include <cstdlib> 68#include <cstddef> 69#include <new> 70#include <iosfwd> 71#include <bits/stl_pair.h> 72#include <bits/type_traits.h> 73#include <bits/stl_iterator_base_types.h> 74#include <bits/stl_iterator_base_funcs.h> 75#include <bits/stl_iterator.h> 76#include <bits/concept_check.h> 77 78namespace std 79{ 80 // swap and iter_swap 81 82 /** 83 * @brief Swaps the contents of two iterators. 84 * @param a An iterator. 85 * @param b Another iterator. 86 * @return Nothing. 87 * 88 * This function swaps the values pointed to by two iterators, not the 89 * iterators themselves. 90 */ 91 template<typename _ForwardIter1, typename _ForwardIter2> 92 inline void 93 iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) 94 { 95 typedef typename iterator_traits<_ForwardIter1>::value_type _ValueType1; 96 typedef typename iterator_traits<_ForwardIter2>::value_type _ValueType2; 97 98 // concept requirements 99 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>) 100 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>) 101 __glibcpp_function_requires(_ConvertibleConcept<_ValueType1, _ValueType2>) 102 __glibcpp_function_requires(_ConvertibleConcept<_ValueType2, _ValueType1>) 103 104 _ValueType1 __tmp = *__a; 105 *__a = *__b; 106 *__b = __tmp; 107 } 108 109 /** 110 * @brief Swaps two values. 111 * @param a A thing of arbitrary type. 112 * @param b Another thing of arbitrary type. 113 * @return Nothing. 114 * 115 * This is the simple classic generic implementation. It will work on 116 * any type which has a copy constructor and an assignment operator. 117 */ 118 template<typename _Tp> 119 inline void 120 swap(_Tp& __a, _Tp& __b) 121 { 122 // concept requirements 123 __glibcpp_function_requires(_SGIAssignableConcept<_Tp>) 124 125 _Tp __tmp = __a; 126 __a = __b; 127 __b = __tmp; 128 } 129 130 //-------------------------------------------------- 131 // min and max 132 133 #undef min 134 #undef max 135 136 /** 137 * @brief This does what you think it does. 138 * @param a A thing of arbitrary type. 139 * @param b Another thing of arbitrary type. 140 * @return The lesser of the parameters. 141 * 142 * This is the simple classic generic implementation. It will work on 143 * temporary expressions, since they are only evaluated once, unlike a 144 * preprocessor macro. 145 */ 146 template<typename _Tp> 147 inline const _Tp& 148 min(const _Tp& __a, const _Tp& __b) 149 { 150 // concept requirements 151 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 152 //return __b < __a ? __b : __a; 153 if (__b < __a) return __b; return __a; 154 } 155 156 /** 157 * @brief This does what you think it does. 158 * @param a A thing of arbitrary type. 159 * @param b Another thing of arbitrary type. 160 * @return The greater of the parameters. 161 * 162 * This is the simple classic generic implementation. It will work on 163 * temporary expressions, since they are only evaluated once, unlike a 164 * preprocessor macro. 165 */ 166 template<typename _Tp> 167 inline const _Tp& 168 max(const _Tp& __a, const _Tp& __b) 169 { 170 // concept requirements 171 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 172 //return __a < __b ? __b : __a; 173 if (__a < __b) return __b; return __a; 174 } 175 176 /** 177 * @brief This does what you think it does. 178 * @param a A thing of arbitrary type. 179 * @param b Another thing of arbitrary type. 180 * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 181 * @return The lesser of the parameters. 182 * 183 * This will work on temporary expressions, since they are only evaluated 184 * once, unlike a preprocessor macro. 185 */ 186 template<typename _Tp, typename _Compare> 187 inline const _Tp& 188 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 189 { 190 //return __comp(__b, __a) ? __b : __a; 191 if (__comp(__b, __a)) return __b; return __a; 192 } 193 194 /** 195 * @brief This does what you think it does. 196 * @param a A thing of arbitrary type. 197 * @param b Another thing of arbitrary type. 198 * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 199 * @return The greater of the parameters. 200 * 201 * This will work on temporary expressions, since they are only evaluated 202 * once, unlike a preprocessor macro. 203 */ 204 template<typename _Tp, typename _Compare> 205 inline const _Tp& 206 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 207 { 208 //return __comp(__a, __b) ? __b : __a; 209 if (__comp(__a, __b)) return __b; return __a; 210 } 211 212 //-------------------------------------------------- 213 // copy 214 215 // All of these auxiliary functions serve two purposes. (1) Replace 216 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 217 // because the input and output ranges are permitted to overlap.) 218 // (2) If we're using random access iterators, then write the loop as 219 // a for loop with an explicit count. 220 221 template<typename _InputIter, typename _OutputIter> 222 inline _OutputIter 223 __copy(_InputIter __first, _InputIter __last, 224 _OutputIter __result, 225 input_iterator_tag) 226 { 227 for ( ; __first != __last; ++__result, ++__first) 228 *__result = *__first; 229 return __result; 230 } 231 232 template<typename _RandomAccessIter, typename _OutputIter> 233 inline _OutputIter 234 __copy(_RandomAccessIter __first, _RandomAccessIter __last, 235 _OutputIter __result, 236 random_access_iterator_tag) 237 { 238 typedef typename iterator_traits<_RandomAccessIter>::difference_type 239 _Distance; 240 for (_Distance __n = __last - __first; __n > 0; --__n) { 241 *__result = *__first; 242 ++__first; 243 ++__result; 244 } 245 return __result; 246 } 247 248 template<typename _Tp> 249 inline _Tp* 250 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) 251 { 252 memmove(__result, __first, sizeof(_Tp) * (__last - __first)); 253 return __result + (__last - __first); 254 } 255 256 template<typename _InputIter, typename _OutputIter> 257 inline _OutputIter 258 __copy_aux2(_InputIter __first, _InputIter __last, 259 _OutputIter __result, __false_type) 260 { return __copy(__first, __last, __result, __iterator_category(__first)); } 261 262 template<typename _InputIter, typename _OutputIter> 263 inline _OutputIter 264 __copy_aux2(_InputIter __first, _InputIter __last, 265 _OutputIter __result, __true_type) 266 { return __copy(__first, __last, __result, __iterator_category(__first)); } 267 268 template<typename _Tp> 269 inline _Tp* 270 __copy_aux2(_Tp* __first, _Tp* __last, 271 _Tp* __result, __true_type) 272 { return __copy_trivial(__first, __last, __result); } 273 274 template<typename _Tp> 275 inline _Tp* 276 __copy_aux2(const _Tp* __first, const _Tp* __last, 277 _Tp* __result, __true_type) 278 { return __copy_trivial(__first, __last, __result); } 279 280 template<typename _InputIter, typename _OutputIter> 281 inline _OutputIter 282 __copy_ni2(_InputIter __first, _InputIter __last, 283 _OutputIter __result, __true_type) 284 { 285 typedef typename iterator_traits<_InputIter>::value_type 286 _ValueType; 287 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator 288 _Trivial; 289 return _OutputIter(__copy_aux2(__first, __last, 290 __result.base(), 291 _Trivial())); 292 } 293 294 template<typename _InputIter, typename _OutputIter> 295 inline _OutputIter 296 __copy_ni2(_InputIter __first, _InputIter __last, 297 _OutputIter __result, __false_type) 298 { 299 typedef typename iterator_traits<_InputIter>::value_type 300 _ValueType; 301 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator 302 _Trivial; 303 return __copy_aux2(__first, __last, 304 __result, 305 _Trivial()); 306 } 307 308 template<typename _InputIter, typename _OutputIter> 309 inline _OutputIter 310 __copy_ni1(_InputIter __first, _InputIter __last, 311 _OutputIter __result, __true_type) 312 { 313 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal; 314 return __copy_ni2(__first.base(), __last.base(), __result, __Normal()); 315 } 316 317 template<typename _InputIter, typename _OutputIter> 318 inline _OutputIter 319 __copy_ni1(_InputIter __first, _InputIter __last, 320 _OutputIter __result, __false_type) 321 { 322 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal; 323 return __copy_ni2(__first, __last, __result, __Normal()); 324 } 325 326 /** 327 * @brief Copies the range [first,last) into result. 328 * @param first An input iterator. 329 * @param last An input iterator. 330 * @param result An output iterator. 331 * @return result + (first - last) 332 * 333 * This inline function will boil down to a call to @c memmove whenever 334 * possible. Failing that, if random access iterators are passed, then the 335 * loop count will be known (and therefore a candidate for compiler 336 * optimizations such as unrolling). If the input range and the output 337 * range overlap, then the copy_backward function should be used instead. 338 */ 339 template<typename _InputIter, typename _OutputIter> 340 inline _OutputIter 341 copy(_InputIter __first, _InputIter __last, _OutputIter __result) 342 { 343 // concept requirements 344 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 345 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 346 typename iterator_traits<_InputIter>::value_type>) 347 348 typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal; 349 return __copy_ni1(__first, __last, __result, __Normal()); 350 } 351 352 //-------------------------------------------------- 353 // copy_backward 354 355 template<typename _BidirectionalIter1, typename _BidirectionalIter2> 356 inline _BidirectionalIter2 357 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last, 358 _BidirectionalIter2 __result, 359 bidirectional_iterator_tag) 360 { 361 while (__first != __last) 362 *--__result = *--__last; 363 return __result; 364 } 365 366 template<typename _RandomAccessIter, typename _BidirectionalIter> 367 inline _BidirectionalIter 368 __copy_backward(_RandomAccessIter __first, _RandomAccessIter __last, 369 _BidirectionalIter __result, 370 random_access_iterator_tag) 371 { 372 typename iterator_traits<_RandomAccessIter>::difference_type __n; 373 for (__n = __last - __first; __n > 0; --__n) 374 *--__result = *--__last; 375 return __result; 376 } 377 378 379 // This dispatch class is a workaround for compilers that do not 380 // have partial ordering of function templates. All we're doing is 381 // creating a specialization so that we can turn a call to copy_backward 382 // into a memmove whenever possible. 383 384 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 385 typename _BoolType> 386 struct __copy_backward_dispatch 387 { 388 static _BidirectionalIter2 389 copy(_BidirectionalIter1 __first, _BidirectionalIter1 __last, 390 _BidirectionalIter2 __result) 391 { 392 return __copy_backward(__first, __last, 393 __result, 394 __iterator_category(__first)); 395 } 396 }; 397 398 template<typename _Tp> 399 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type> 400 { 401 static _Tp* 402 copy(const _Tp* __first, const _Tp* __last, _Tp* __result) 403 { 404 const ptrdiff_t _Num = __last - __first; 405 memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 406 return __result - _Num; 407 } 408 }; 409 410 template<typename _Tp> 411 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type> 412 { 413 static _Tp* 414 copy(const _Tp* __first, const _Tp* __last, _Tp* __result) 415 { 416 return __copy_backward_dispatch<_Tp*, _Tp*, __true_type> 417 ::copy(__first, __last, __result); 418 } 419 }; 420 421 template<typename _BI1, typename _BI2> 422 inline _BI2 423 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) 424 { 425 typedef typename __type_traits<typename iterator_traits<_BI2>::value_type> 426 ::has_trivial_assignment_operator _Trivial; 427 return __copy_backward_dispatch<_BI1, _BI2, _Trivial> 428 ::copy(__first, __last, __result); 429 } 430 431 template <typename _BI1, typename _BI2> 432 inline _BI2 433 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, 434 _BI2 __result, __true_type) 435 { return _BI2(__copy_backward_aux(__first, __last, __result.base())); } 436 437 template <typename _BI1, typename _BI2> 438 inline _BI2 439 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, 440 _BI2 __result, __false_type) 441 { return __copy_backward_aux(__first, __last, __result); } 442 443 template <typename _BI1, typename _BI2> 444 inline _BI2 445 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, 446 _BI2 __result, __true_type) 447 { 448 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; 449 return __copy_backward_output_normal_iterator(__first.base(), __last.base(), 450 __result, __Normal()); 451 } 452 453 template <typename _BI1, typename _BI2> 454 inline _BI2 455 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, 456 _BI2 __result, __false_type) 457 { 458 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; 459 return __copy_backward_output_normal_iterator(__first, __last, __result, 460 __Normal()); 461 } 462 463 /** 464 * @brief Copies the range [first,last) into result. 465 * @param first An input iterator. 466 * @param last An input iterator. 467 * @param result An output iterator. 468 * @return result - (first - last) 469 * 470 * The function has the same effect as copy, but starts at the end of the 471 * range and works its way to the start, returning the start of the result. 472 * This inline function will boil down to a call to @c memmove whenever 473 * possible. Failing that, if random access iterators are passed, then the 474 * loop count will be known (and therefore a candidate for compiler 475 * optimizations such as unrolling). 476 */ 477 template <typename _BI1, typename _BI2> 478 inline _BI2 479 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 480 { 481 // concept requirements 482 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>) 483 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 484 __glibcpp_function_requires(_ConvertibleConcept< 485 typename iterator_traits<_BI1>::value_type, 486 typename iterator_traits<_BI2>::value_type>) 487 488 typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal; 489 return __copy_backward_input_normal_iterator(__first, __last, __result, 490 __Normal()); 491 } 492 493 494 //-------------------------------------------------- 495 // fill and fill_n 496 497 498 /** 499 * @brief Fills the range [first,last) with copies of value. 500 * @param first A forward iterator. 501 * @param last A forward iterator. 502 * @param value A reference-to-const of arbitrary type. 503 * @return Nothing. 504 * 505 * This function fills a range with copies of the same value. For one-byte 506 * types filling contiguous areas of memory, this becomes an inline call to 507 * @c memset. 508 */ 509 template<typename _ForwardIter, typename _Tp> 510 void 511 fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) 512 { 513 // concept requirements 514 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 515 516 for ( ; __first != __last; ++__first) 517 *__first = __value; 518 } 519 520 /** 521 * @brief Fills the range [first,first+n) with copies of value. 522 * @param first An output iterator. 523 * @param n The count of copies to perform. 524 * @param value A reference-to-const of arbitrary type. 525 * @return The iterator at first+n. 526 * 527 * This function fills a range with copies of the same value. For one-byte 528 * types filling contiguous areas of memory, this becomes an inline call to 529 * @c memset. 530 */ 531 template<typename _OutputIter, typename _Size, typename _Tp> 532 _OutputIter 533 fill_n(_OutputIter __first, _Size __n, const _Tp& __value) 534 { 535 // concept requirements 536 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>) 537 538 for ( ; __n > 0; --__n, ++__first) 539 *__first = __value; 540 return __first; 541 } 542 543 // Specialization: for one-byte types we can use memset. 544 545 inline void 546 fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c) 547 { 548 unsigned char __tmp = __c; 549 memset(__first, __tmp, __last - __first); 550 } 551 552 inline void 553 fill(signed char* __first, signed char* __last, const signed char& __c) 554 { 555 signed char __tmp = __c; 556 memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 557 } 558 559 inline void 560 fill(char* __first, char* __last, const char& __c) 561 { 562 char __tmp = __c; 563 memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 564 } 565 566 template<typename _Size> 567 inline unsigned char* 568 fill_n(unsigned char* __first, _Size __n, const unsigned char& __c) 569 { 570 fill(__first, __first + __n, __c); 571 return __first + __n; 572 } 573 574 template<typename _Size> 575 inline signed char* 576 fill_n(char* __first, _Size __n, const signed char& __c) 577 { 578 fill(__first, __first + __n, __c); 579 return __first + __n; 580 } 581 582 template<typename _Size> 583 inline char* 584 fill_n(char* __first, _Size __n, const char& __c) 585 { 586 fill(__first, __first + __n, __c); 587 return __first + __n; 588 } 589 590 591 //-------------------------------------------------- 592 // equal and mismatch 593 594 /** 595 * @brief Finds the places in ranges which don't match. 596 * @param first1 An input iterator. 597 * @param last1 An input iterator. 598 * @param first2 An input iterator. 599 * @return A pair of iterators pointing to the first mismatch. 600 * 601 * This compares the elements of two ranges using @c == and returns a pair 602 * of iterators. The first iterator points into the first range, the 603 * second iterator points into the second range, and the elements pointed 604 * to by the iterators are not equal. 605 */ 606 template<typename _InputIter1, typename _InputIter2> 607 pair<_InputIter1, _InputIter2> 608 mismatch(_InputIter1 __first1, _InputIter1 __last1, 609 _InputIter2 __first2) 610 { 611 // concept requirements 612 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 613 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 614 __glibcpp_function_requires(_EqualityComparableConcept< 615 typename iterator_traits<_InputIter1>::value_type>) 616 __glibcpp_function_requires(_EqualityComparableConcept< 617 typename iterator_traits<_InputIter2>::value_type>) 618 619 while (__first1 != __last1 && *__first1 == *__first2) { 620 ++__first1; 621 ++__first2; 622 } 623 return pair<_InputIter1, _InputIter2>(__first1, __first2); 624 } 625 626 /** 627 * @brief Finds the places in ranges which don't match. 628 * @param first1 An input iterator. 629 * @param last1 An input iterator. 630 * @param first2 An input iterator. 631 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 632 * @return A pair of iterators pointing to the first mismatch. 633 * 634 * This compares the elements of two ranges using the binary_pred 635 * parameter, and returns a pair 636 * of iterators. The first iterator points into the first range, the 637 * second iterator points into the second range, and the elements pointed 638 * to by the iterators are not equal. 639 */ 640 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate> 641 pair<_InputIter1, _InputIter2> 642 mismatch(_InputIter1 __first1, _InputIter1 __last1, 643 _InputIter2 __first2, 644 _BinaryPredicate __binary_pred) 645 { 646 // concept requirements 647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 648 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 649 650 while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) { 651 ++__first1; 652 ++__first2; 653 } 654 return pair<_InputIter1, _InputIter2>(__first1, __first2); 655 } 656 657 /** 658 * @brief Tests a range for element-wise equality. 659 * @param first1 An input iterator. 660 * @param last1 An input iterator. 661 * @param first2 An input iterator. 662 * @return A boolean true or false. 663 * 664 * This compares the elements of two ranges using @c == and returns true or 665 * false depending on whether all of the corresponding elements of the 666 * ranges are equal. 667 */ 668 template<typename _InputIter1, typename _InputIter2> 669 inline bool 670 equal(_InputIter1 __first1, _InputIter1 __last1, 671 _InputIter2 __first2) 672 { 673 // concept requirements 674 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 675 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 676 __glibcpp_function_requires(_EqualOpConcept< 677 typename iterator_traits<_InputIter1>::value_type, 678 typename iterator_traits<_InputIter2>::value_type>) 679 680 for ( ; __first1 != __last1; ++__first1, ++__first2) 681 if (!(*__first1 == *__first2)) 682 return false; 683 return true; 684 } 685 686 /** 687 * @brief Tests a range for element-wise equality. 688 * @param first1 An input iterator. 689 * @param last1 An input iterator. 690 * @param first2 An input iterator. 691 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 692 * @return A boolean true or false. 693 * 694 * This compares the elements of two ranges using the binary_pred 695 * parameter, and returns true or 696 * false depending on whether all of the corresponding elements of the 697 * ranges are equal. 698 */ 699 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate> 700 inline bool 701 equal(_InputIter1 __first1, _InputIter1 __last1, 702 _InputIter2 __first2, 703 _BinaryPredicate __binary_pred) 704 { 705 // concept requirements 706 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 707 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 708 709 for ( ; __first1 != __last1; ++__first1, ++__first2) 710 if (!__binary_pred(*__first1, *__first2)) 711 return false; 712 return true; 713 } 714 715 //-------------------------------------------------- 716 // lexicographical_compare 717 718 /** 719 * @brief Performs "dictionary" comparison on ranges. 720 * @param first1 An input iterator. 721 * @param last1 An input iterator. 722 * @param first2 An input iterator. 723 * @param last2 An input iterator. 724 * @return A boolean true or false. 725 * 726 * "Returns true if the sequence of elements defined by the range 727 * [first1,last1) is lexicographically less than the sequence of elements 728 * defined by the range [first2,last2). Returns false otherwise." 729 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 730 * then this is an inline call to @c memcmp. 731 */ 732 template<typename _InputIter1, typename _InputIter2> 733 bool 734 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 735 _InputIter2 __first2, _InputIter2 __last2) 736 { 737 // concept requirements 738 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 739 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 740 __glibcpp_function_requires(_LessThanComparableConcept< 741 typename iterator_traits<_InputIter1>::value_type>) 742 __glibcpp_function_requires(_LessThanComparableConcept< 743 typename iterator_traits<_InputIter2>::value_type>) 744 745 for ( ; __first1 != __last1 && __first2 != __last2 746 ; ++__first1, ++__first2) { 747 if (*__first1 < *__first2) 748 return true; 749 if (*__first2 < *__first1) 750 return false; 751 } 752 return __first1 == __last1 && __first2 != __last2; 753 } 754 755 /** 756 * @brief Performs "dictionary" comparison on ranges. 757 * @param first1 An input iterator. 758 * @param last1 An input iterator. 759 * @param first2 An input iterator. 760 * @param last2 An input iterator. 761 * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 762 * @return A boolean true or false. 763 * 764 * The same as the four-parameter @c lexigraphical_compare, but uses the 765 * comp parameter instead of @c <. 766 */ 767 template<typename _InputIter1, typename _InputIter2, typename _Compare> 768 bool 769 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 770 _InputIter2 __first2, _InputIter2 __last2, 771 _Compare __comp) 772 { 773 // concept requirements 774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 776 777 for ( ; __first1 != __last1 && __first2 != __last2 778 ; ++__first1, ++__first2) { 779 if (__comp(*__first1, *__first2)) 780 return true; 781 if (__comp(*__first2, *__first1)) 782 return false; 783 } 784 return __first1 == __last1 && __first2 != __last2; 785 } 786 787 inline bool 788 lexicographical_compare(const unsigned char* __first1, const unsigned char* __last1, 789 const unsigned char* __first2, const unsigned char* __last2) 790 { 791 const size_t __len1 = __last1 - __first1; 792 const size_t __len2 = __last2 - __first2; 793 const int __result = memcmp(__first1, __first2, min(__len1, __len2)); 794 return __result != 0 ? __result < 0 : __len1 < __len2; 795 } 796 797 inline bool 798 lexicographical_compare(const char* __first1, const char* __last1, 799 const char* __first2, const char* __last2) 800 { 801#if CHAR_MAX == SCHAR_MAX 802 return lexicographical_compare((const signed char*) __first1, 803 (const signed char*) __last1, 804 (const signed char*) __first2, 805 (const signed char*) __last2); 806#else /* CHAR_MAX == SCHAR_MAX */ 807 return lexicographical_compare((const unsigned char*) __first1, 808 (const unsigned char*) __last1, 809 (const unsigned char*) __first2, 810 (const unsigned char*) __last2); 811#endif /* CHAR_MAX == SCHAR_MAX */ 812 } 813 814} // namespace std 815 816#endif /* __GLIBCPP_INTERNAL_ALGOBASE_H */ 817 818// Local Variables: 819// mode:C++ 820// End: 821