stl_algobase.h revision 132720
197403Sobrien// Bits and pieces used in algorithms -*- C++ -*- 297403Sobrien 3132720Skan// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996-1998 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file stl_algobase.h 5797403Sobrien * This is an internal header file, included by other library headers. 5897403Sobrien * You should not attempt to use it directly. 5997403Sobrien */ 6097403Sobrien 61132720Skan#ifndef _ALGOBASE_H 62132720Skan#define _ALGOBASE_H 1 6397403Sobrien 6497403Sobrien#include <bits/c++config.h> 6597403Sobrien#include <cstring> 6697403Sobrien#include <climits> 6797403Sobrien#include <cstdlib> 6897403Sobrien#include <cstddef> 6997403Sobrien#include <new> 7097403Sobrien#include <iosfwd> 7197403Sobrien#include <bits/stl_pair.h> 7297403Sobrien#include <bits/type_traits.h> 7397403Sobrien#include <bits/stl_iterator_base_types.h> 7497403Sobrien#include <bits/stl_iterator_base_funcs.h> 7597403Sobrien#include <bits/stl_iterator.h> 7697403Sobrien#include <bits/concept_check.h> 77132720Skan#include <debug/debug.h> 7897403Sobrien 7997403Sobriennamespace std 8097403Sobrien{ 8197403Sobrien /** 8297403Sobrien * @brief Swaps the contents of two iterators. 8397403Sobrien * @param a An iterator. 8497403Sobrien * @param b Another iterator. 8597403Sobrien * @return Nothing. 8697403Sobrien * 8797403Sobrien * This function swaps the values pointed to by two iterators, not the 8897403Sobrien * iterators themselves. 8997403Sobrien */ 90132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 9197403Sobrien inline void 92132720Skan iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 9397403Sobrien { 94132720Skan typedef typename iterator_traits<_ForwardIterator1>::value_type 95132720Skan _ValueType1; 96132720Skan typedef typename iterator_traits<_ForwardIterator2>::value_type 97132720Skan _ValueType2; 9897403Sobrien 9997403Sobrien // concept requirements 100132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 101132720Skan _ForwardIterator1>) 102132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 103132720Skan _ForwardIterator2>) 104132720Skan __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 105132720Skan _ValueType2>) 106132720Skan __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 107132720Skan _ValueType1>) 10897403Sobrien 109132720Skan const _ValueType1 __tmp = *__a; 11097403Sobrien *__a = *__b; 11197403Sobrien *__b = __tmp; 11297403Sobrien } 11397403Sobrien 11497403Sobrien /** 11597403Sobrien * @brief Swaps two values. 11697403Sobrien * @param a A thing of arbitrary type. 11797403Sobrien * @param b Another thing of arbitrary type. 11897403Sobrien * @return Nothing. 11997403Sobrien * 12097403Sobrien * This is the simple classic generic implementation. It will work on 12197403Sobrien * any type which has a copy constructor and an assignment operator. 12297403Sobrien */ 12397403Sobrien template<typename _Tp> 12497403Sobrien inline void 12597403Sobrien swap(_Tp& __a, _Tp& __b) 12697403Sobrien { 12797403Sobrien // concept requirements 128132720Skan __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) 129132720Skan 130132720Skan const _Tp __tmp = __a; 13197403Sobrien __a = __b; 13297403Sobrien __b = __tmp; 13397403Sobrien } 13497403Sobrien 13597403Sobrien #undef min 13697403Sobrien #undef max 13797403Sobrien 13897403Sobrien /** 13997403Sobrien * @brief This does what you think it does. 14097403Sobrien * @param a A thing of arbitrary type. 14197403Sobrien * @param b Another thing of arbitrary type. 14297403Sobrien * @return The lesser of the parameters. 14397403Sobrien * 14497403Sobrien * This is the simple classic generic implementation. It will work on 14597403Sobrien * temporary expressions, since they are only evaluated once, unlike a 14697403Sobrien * preprocessor macro. 14797403Sobrien */ 14897403Sobrien template<typename _Tp> 14997403Sobrien inline const _Tp& 15097403Sobrien min(const _Tp& __a, const _Tp& __b) 15197403Sobrien { 15297403Sobrien // concept requirements 153132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 15497403Sobrien //return __b < __a ? __b : __a; 155132720Skan if (__b < __a) 156132720Skan return __b; 157132720Skan return __a; 15897403Sobrien } 15997403Sobrien 16097403Sobrien /** 16197403Sobrien * @brief This does what you think it does. 16297403Sobrien * @param a A thing of arbitrary type. 16397403Sobrien * @param b Another thing of arbitrary type. 16497403Sobrien * @return The greater of the parameters. 16597403Sobrien * 16697403Sobrien * This is the simple classic generic implementation. It will work on 16797403Sobrien * temporary expressions, since they are only evaluated once, unlike a 16897403Sobrien * preprocessor macro. 16997403Sobrien */ 17097403Sobrien template<typename _Tp> 17197403Sobrien inline const _Tp& 172132720Skan max(const _Tp& __a, const _Tp& __b) 17397403Sobrien { 17497403Sobrien // concept requirements 175132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 17697403Sobrien //return __a < __b ? __b : __a; 177132720Skan if (__a < __b) 178132720Skan return __b; 179132720Skan return __a; 18097403Sobrien } 18197403Sobrien 18297403Sobrien /** 18397403Sobrien * @brief This does what you think it does. 18497403Sobrien * @param a A thing of arbitrary type. 18597403Sobrien * @param b Another thing of arbitrary type. 18697403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 18797403Sobrien * @return The lesser of the parameters. 18897403Sobrien * 18997403Sobrien * This will work on temporary expressions, since they are only evaluated 19097403Sobrien * once, unlike a preprocessor macro. 19197403Sobrien */ 19297403Sobrien template<typename _Tp, typename _Compare> 19397403Sobrien inline const _Tp& 19497403Sobrien min(const _Tp& __a, const _Tp& __b, _Compare __comp) 19597403Sobrien { 19697403Sobrien //return __comp(__b, __a) ? __b : __a; 197132720Skan if (__comp(__b, __a)) 198132720Skan return __b; 199132720Skan return __a; 20097403Sobrien } 20197403Sobrien 20297403Sobrien /** 20397403Sobrien * @brief This does what you think it does. 20497403Sobrien * @param a A thing of arbitrary type. 20597403Sobrien * @param b Another thing of arbitrary type. 20697403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 20797403Sobrien * @return The greater of the parameters. 20897403Sobrien * 20997403Sobrien * This will work on temporary expressions, since they are only evaluated 21097403Sobrien * once, unlike a preprocessor macro. 21197403Sobrien */ 21297403Sobrien template<typename _Tp, typename _Compare> 21397403Sobrien inline const _Tp& 21497403Sobrien max(const _Tp& __a, const _Tp& __b, _Compare __comp) 21597403Sobrien { 21697403Sobrien //return __comp(__a, __b) ? __b : __a; 217132720Skan if (__comp(__a, __b)) 218132720Skan return __b; 219132720Skan return __a; 22097403Sobrien } 22197403Sobrien 22297403Sobrien // All of these auxiliary functions serve two purposes. (1) Replace 22397403Sobrien // calls to copy with memmove whenever possible. (Memmove, not memcpy, 22497403Sobrien // because the input and output ranges are permitted to overlap.) 22597403Sobrien // (2) If we're using random access iterators, then write the loop as 22697403Sobrien // a for loop with an explicit count. 22797403Sobrien 228132720Skan template<typename _InputIterator, typename _OutputIterator> 229132720Skan inline _OutputIterator 230132720Skan __copy(_InputIterator __first, _InputIterator __last, 231132720Skan _OutputIterator __result, input_iterator_tag) 23297403Sobrien { 233132720Skan for (; __first != __last; ++__result, ++__first) 23497403Sobrien *__result = *__first; 23597403Sobrien return __result; 23697403Sobrien } 23797403Sobrien 238132720Skan template<typename _RandomAccessIterator, typename _OutputIterator> 239132720Skan inline _OutputIterator 240132720Skan __copy(_RandomAccessIterator __first, _RandomAccessIterator __last, 241132720Skan _OutputIterator __result, random_access_iterator_tag) 24297403Sobrien { 243132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 24497403Sobrien _Distance; 245132720Skan for (_Distance __n = __last - __first; __n > 0; --__n) 246132720Skan { 247132720Skan *__result = *__first; 248132720Skan ++__first; 249132720Skan ++__result; 250132720Skan } 25197403Sobrien return __result; 25297403Sobrien } 25397403Sobrien 25497403Sobrien template<typename _Tp> 25597403Sobrien inline _Tp* 25697403Sobrien __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) 25797403Sobrien { 258132720Skan std::memmove(__result, __first, sizeof(_Tp) * (__last - __first)); 25997403Sobrien return __result + (__last - __first); 26097403Sobrien } 26197403Sobrien 262132720Skan template<typename _InputIterator, typename _OutputIterator> 263132720Skan inline _OutputIterator 264132720Skan __copy_aux2(_InputIterator __first, _InputIterator __last, 265132720Skan _OutputIterator __result, __false_type) 266132720Skan { return std::__copy(__first, __last, __result, 267132720Skan std::__iterator_category(__first)); } 26897403Sobrien 269132720Skan template<typename _InputIterator, typename _OutputIterator> 270132720Skan inline _OutputIterator 271132720Skan __copy_aux2(_InputIterator __first, _InputIterator __last, 272132720Skan _OutputIterator __result, __true_type) 273132720Skan { return std::__copy(__first, __last, __result, 274132720Skan std::__iterator_category(__first)); } 27597403Sobrien 27697403Sobrien template<typename _Tp> 27797403Sobrien inline _Tp* 278132720Skan __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result, __true_type) 279132720Skan { return std::__copy_trivial(__first, __last, __result); } 28097403Sobrien 28197403Sobrien template<typename _Tp> 28297403Sobrien inline _Tp* 283132720Skan __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result, 284132720Skan __true_type) 285132720Skan { return std::__copy_trivial(__first, __last, __result); } 28697403Sobrien 287132720Skan template<typename _InputIterator, typename _OutputIterator> 288132720Skan inline _OutputIterator 289132720Skan __copy_ni2(_InputIterator __first, _InputIterator __last, 290132720Skan _OutputIterator __result, __true_type) 29197403Sobrien { 292132720Skan typedef typename iterator_traits<_InputIterator>::value_type 293132720Skan _ValueType; 294132720Skan typedef typename __type_traits< 295132720Skan _ValueType>::has_trivial_assignment_operator _Trivial; 296132720Skan return _OutputIterator(std::__copy_aux2(__first, __last, __result.base(), 297132720Skan _Trivial())); 29897403Sobrien } 29997403Sobrien 300132720Skan template<typename _InputIterator, typename _OutputIterator> 301132720Skan inline _OutputIterator 302132720Skan __copy_ni2(_InputIterator __first, _InputIterator __last, 303132720Skan _OutputIterator __result, __false_type) 30497403Sobrien { 305132720Skan typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 306132720Skan typedef typename __type_traits< 307132720Skan _ValueType>::has_trivial_assignment_operator _Trivial; 308132720Skan return std::__copy_aux2(__first, __last, __result, _Trivial()); 30997403Sobrien } 31097403Sobrien 311132720Skan template<typename _InputIterator, typename _OutputIterator> 312132720Skan inline _OutputIterator 313132720Skan __copy_ni1(_InputIterator __first, _InputIterator __last, 314132720Skan _OutputIterator __result, __true_type) 31597403Sobrien { 316132720Skan typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; 317132720Skan return std::__copy_ni2(__first.base(), __last.base(), 318132720Skan __result, __Normal()); 31997403Sobrien } 32097403Sobrien 321132720Skan template<typename _InputIterator, typename _OutputIterator> 322132720Skan inline _OutputIterator 323132720Skan __copy_ni1(_InputIterator __first, _InputIterator __last, 324132720Skan _OutputIterator __result, __false_type) 32597403Sobrien { 326132720Skan typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; 327132720Skan return std::__copy_ni2(__first, __last, __result, __Normal()); 32897403Sobrien } 32997403Sobrien 33097403Sobrien /** 33197403Sobrien * @brief Copies the range [first,last) into result. 33297403Sobrien * @param first An input iterator. 33397403Sobrien * @param last An input iterator. 33497403Sobrien * @param result An output iterator. 33597403Sobrien * @return result + (first - last) 33697403Sobrien * 33797403Sobrien * This inline function will boil down to a call to @c memmove whenever 33897403Sobrien * possible. Failing that, if random access iterators are passed, then the 33997403Sobrien * loop count will be known (and therefore a candidate for compiler 340132720Skan * optimizations such as unrolling). Result may not be contained within 341132720Skan * [first,last); the copy_backward function should be used instead. 342132720Skan * 343132720Skan * Note that the end of the output range is permitted to be contained 344132720Skan * within [first,last). 34597403Sobrien */ 346132720Skan template<typename _InputIterator, typename _OutputIterator> 347132720Skan inline _OutputIterator 348132720Skan copy(_InputIterator __first, _InputIterator __last, 349132720Skan _OutputIterator __result) 35097403Sobrien { 35197403Sobrien // concept requirements 352132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 353132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 354132720Skan typename iterator_traits<_InputIterator>::value_type>) 355132720Skan __glibcxx_requires_valid_range(__first, __last); 35697403Sobrien 357132720Skan typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal; 358132720Skan return std::__copy_ni1(__first, __last, __result, __Normal()); 35997403Sobrien } 36097403Sobrien 361132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> 362132720Skan inline _BidirectionalIterator2 363132720Skan __copy_backward(_BidirectionalIterator1 __first, 364132720Skan _BidirectionalIterator1 __last, 365132720Skan _BidirectionalIterator2 __result, 36697403Sobrien bidirectional_iterator_tag) 36797403Sobrien { 36897403Sobrien while (__first != __last) 36997403Sobrien *--__result = *--__last; 37097403Sobrien return __result; 37197403Sobrien } 37297403Sobrien 373132720Skan template<typename _RandomAccessIterator, typename _BidirectionalIterator> 374132720Skan inline _BidirectionalIterator 375132720Skan __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last, 376132720Skan _BidirectionalIterator __result, random_access_iterator_tag) 37797403Sobrien { 378132720Skan typename iterator_traits<_RandomAccessIterator>::difference_type __n; 37997403Sobrien for (__n = __last - __first; __n > 0; --__n) 38097403Sobrien *--__result = *--__last; 38197403Sobrien return __result; 38297403Sobrien } 38397403Sobrien 38497403Sobrien 385132720Skan // This dispatch class is a workaround for compilers that do not 38697403Sobrien // have partial ordering of function templates. All we're doing is 38797403Sobrien // creating a specialization so that we can turn a call to copy_backward 38897403Sobrien // into a memmove whenever possible. 389132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 39097403Sobrien typename _BoolType> 39197403Sobrien struct __copy_backward_dispatch 39297403Sobrien { 393132720Skan static _BidirectionalIterator2 394132720Skan copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, 395132720Skan _BidirectionalIterator2 __result) 396132720Skan { return std::__copy_backward(__first, __last, __result, 397132720Skan std::__iterator_category(__first)); } 39897403Sobrien }; 39997403Sobrien 40097403Sobrien template<typename _Tp> 40197403Sobrien struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type> 40297403Sobrien { 40397403Sobrien static _Tp* 40497403Sobrien copy(const _Tp* __first, const _Tp* __last, _Tp* __result) 40597403Sobrien { 40697403Sobrien const ptrdiff_t _Num = __last - __first; 407132720Skan std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 40897403Sobrien return __result - _Num; 40997403Sobrien } 41097403Sobrien }; 41197403Sobrien 41297403Sobrien template<typename _Tp> 41397403Sobrien struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type> 41497403Sobrien { 41597403Sobrien static _Tp* 41697403Sobrien copy(const _Tp* __first, const _Tp* __last, _Tp* __result) 41797403Sobrien { 418132720Skan return std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type> 41997403Sobrien ::copy(__first, __last, __result); 42097403Sobrien } 42197403Sobrien }; 42297403Sobrien 42397403Sobrien template<typename _BI1, typename _BI2> 42497403Sobrien inline _BI2 42597403Sobrien __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) 42697403Sobrien { 42797403Sobrien typedef typename __type_traits<typename iterator_traits<_BI2>::value_type> 42897403Sobrien ::has_trivial_assignment_operator _Trivial; 429132720Skan return 430132720Skan std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first, 431132720Skan __last, 432132720Skan __result); 43397403Sobrien } 43497403Sobrien 43597403Sobrien template <typename _BI1, typename _BI2> 43697403Sobrien inline _BI2 43797403Sobrien __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, 43897403Sobrien _BI2 __result, __true_type) 439132720Skan { return _BI2(std::__copy_backward_aux(__first, __last, __result.base())); } 44097403Sobrien 44197403Sobrien template <typename _BI1, typename _BI2> 44297403Sobrien inline _BI2 44397403Sobrien __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, 44497403Sobrien _BI2 __result, __false_type) 445132720Skan { return std::__copy_backward_aux(__first, __last, __result); } 44697403Sobrien 44797403Sobrien template <typename _BI1, typename _BI2> 44897403Sobrien inline _BI2 44997403Sobrien __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, 45097403Sobrien _BI2 __result, __true_type) 45197403Sobrien { 45297403Sobrien typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; 453132720Skan return std::__copy_backward_output_normal_iterator(__first.base(), 454132720Skan __last.base(), 455132720Skan __result, __Normal()); 45697403Sobrien } 45797403Sobrien 45897403Sobrien template <typename _BI1, typename _BI2> 45997403Sobrien inline _BI2 46097403Sobrien __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, 46197403Sobrien _BI2 __result, __false_type) 46297403Sobrien { 46397403Sobrien typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; 464132720Skan return std::__copy_backward_output_normal_iterator(__first, __last, 465132720Skan __result, __Normal()); 46697403Sobrien } 46797403Sobrien 46897403Sobrien /** 46997403Sobrien * @brief Copies the range [first,last) into result. 470132720Skan * @param first A bidirectional iterator. 471132720Skan * @param last A bidirectional iterator. 472132720Skan * @param result A bidirectional iterator. 47397403Sobrien * @return result - (first - last) 47497403Sobrien * 47597403Sobrien * The function has the same effect as copy, but starts at the end of the 47697403Sobrien * range and works its way to the start, returning the start of the result. 47797403Sobrien * This inline function will boil down to a call to @c memmove whenever 47897403Sobrien * possible. Failing that, if random access iterators are passed, then the 47997403Sobrien * loop count will be known (and therefore a candidate for compiler 48097403Sobrien * optimizations such as unrolling). 481132720Skan * 482132720Skan * Result may not be in the range [first,last). Use copy instead. Note 483132720Skan * that the start of the output range may overlap [first,last). 48497403Sobrien */ 48597403Sobrien template <typename _BI1, typename _BI2> 48697403Sobrien inline _BI2 48797403Sobrien copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 48897403Sobrien { 48997403Sobrien // concept requirements 490132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 491132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 492132720Skan __glibcxx_function_requires(_ConvertibleConcept< 49397403Sobrien typename iterator_traits<_BI1>::value_type, 49497403Sobrien typename iterator_traits<_BI2>::value_type>) 495132720Skan __glibcxx_requires_valid_range(__first, __last); 49697403Sobrien 49797403Sobrien typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal; 498132720Skan return std::__copy_backward_input_normal_iterator(__first, __last, 499132720Skan __result, __Normal()); 50097403Sobrien } 50197403Sobrien 50297403Sobrien 50397403Sobrien /** 50497403Sobrien * @brief Fills the range [first,last) with copies of value. 50597403Sobrien * @param first A forward iterator. 50697403Sobrien * @param last A forward iterator. 50797403Sobrien * @param value A reference-to-const of arbitrary type. 50897403Sobrien * @return Nothing. 50997403Sobrien * 51097403Sobrien * This function fills a range with copies of the same value. For one-byte 51197403Sobrien * types filling contiguous areas of memory, this becomes an inline call to 51297403Sobrien * @c memset. 51397403Sobrien */ 514132720Skan template<typename _ForwardIterator, typename _Tp> 51597403Sobrien void 516132720Skan fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 51797403Sobrien { 51897403Sobrien // concept requirements 519132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 520132720Skan _ForwardIterator>) 521132720Skan __glibcxx_requires_valid_range(__first, __last); 52297403Sobrien 52397403Sobrien for ( ; __first != __last; ++__first) 52497403Sobrien *__first = __value; 52597403Sobrien } 52697403Sobrien 52797403Sobrien /** 52897403Sobrien * @brief Fills the range [first,first+n) with copies of value. 52997403Sobrien * @param first An output iterator. 53097403Sobrien * @param n The count of copies to perform. 53197403Sobrien * @param value A reference-to-const of arbitrary type. 53297403Sobrien * @return The iterator at first+n. 53397403Sobrien * 53497403Sobrien * This function fills a range with copies of the same value. For one-byte 53597403Sobrien * types filling contiguous areas of memory, this becomes an inline call to 53697403Sobrien * @c memset. 53797403Sobrien */ 538132720Skan template<typename _OutputIterator, typename _Size, typename _Tp> 539132720Skan _OutputIterator 540132720Skan fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) 54197403Sobrien { 54297403Sobrien // concept requirements 543132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>) 54497403Sobrien 54597403Sobrien for ( ; __n > 0; --__n, ++__first) 54697403Sobrien *__first = __value; 54797403Sobrien return __first; 54897403Sobrien } 54997403Sobrien 55097403Sobrien // Specialization: for one-byte types we can use memset. 55197403Sobrien inline void 55297403Sobrien fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c) 55397403Sobrien { 554132720Skan __glibcxx_requires_valid_range(__first, __last); 555132720Skan const unsigned char __tmp = __c; 556132720Skan std::memset(__first, __tmp, __last - __first); 55797403Sobrien } 55897403Sobrien 55997403Sobrien inline void 56097403Sobrien fill(signed char* __first, signed char* __last, const signed char& __c) 56197403Sobrien { 562132720Skan __glibcxx_requires_valid_range(__first, __last); 563132720Skan const signed char __tmp = __c; 564132720Skan std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 56597403Sobrien } 56697403Sobrien 56797403Sobrien inline void 56897403Sobrien fill(char* __first, char* __last, const char& __c) 56997403Sobrien { 570132720Skan __glibcxx_requires_valid_range(__first, __last); 571132720Skan const char __tmp = __c; 572132720Skan std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); 57397403Sobrien } 57497403Sobrien 57597403Sobrien template<typename _Size> 57697403Sobrien inline unsigned char* 57797403Sobrien fill_n(unsigned char* __first, _Size __n, const unsigned char& __c) 57897403Sobrien { 579132720Skan std::fill(__first, __first + __n, __c); 58097403Sobrien return __first + __n; 58197403Sobrien } 58297403Sobrien 58397403Sobrien template<typename _Size> 58497403Sobrien inline signed char* 58597403Sobrien fill_n(char* __first, _Size __n, const signed char& __c) 58697403Sobrien { 587132720Skan std::fill(__first, __first + __n, __c); 58897403Sobrien return __first + __n; 58997403Sobrien } 59097403Sobrien 59197403Sobrien template<typename _Size> 59297403Sobrien inline char* 59397403Sobrien fill_n(char* __first, _Size __n, const char& __c) 59497403Sobrien { 595132720Skan std::fill(__first, __first + __n, __c); 59697403Sobrien return __first + __n; 59797403Sobrien } 59897403Sobrien 59997403Sobrien 60097403Sobrien /** 60197403Sobrien * @brief Finds the places in ranges which don't match. 60297403Sobrien * @param first1 An input iterator. 60397403Sobrien * @param last1 An input iterator. 60497403Sobrien * @param first2 An input iterator. 60597403Sobrien * @return A pair of iterators pointing to the first mismatch. 60697403Sobrien * 60797403Sobrien * This compares the elements of two ranges using @c == and returns a pair 60897403Sobrien * of iterators. The first iterator points into the first range, the 60997403Sobrien * second iterator points into the second range, and the elements pointed 61097403Sobrien * to by the iterators are not equal. 61197403Sobrien */ 612132720Skan template<typename _InputIterator1, typename _InputIterator2> 613132720Skan pair<_InputIterator1, _InputIterator2> 614132720Skan mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 615132720Skan _InputIterator2 __first2) 61697403Sobrien { 61797403Sobrien // concept requirements 618132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 619132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 620132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 621132720Skan typename iterator_traits<_InputIterator1>::value_type>) 622132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 623132720Skan typename iterator_traits<_InputIterator2>::value_type>) 624132720Skan __glibcxx_requires_valid_range(__first1, __last1); 62597403Sobrien 626132720Skan while (__first1 != __last1 && *__first1 == *__first2) 627132720Skan { 628132720Skan ++__first1; 629132720Skan ++__first2; 630132720Skan } 631132720Skan return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 63297403Sobrien } 63397403Sobrien 63497403Sobrien /** 63597403Sobrien * @brief Finds the places in ranges which don't match. 63697403Sobrien * @param first1 An input iterator. 63797403Sobrien * @param last1 An input iterator. 63897403Sobrien * @param first2 An input iterator. 63997403Sobrien * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 64097403Sobrien * @return A pair of iterators pointing to the first mismatch. 64197403Sobrien * 64297403Sobrien * This compares the elements of two ranges using the binary_pred 64397403Sobrien * parameter, and returns a pair 64497403Sobrien * of iterators. The first iterator points into the first range, the 64597403Sobrien * second iterator points into the second range, and the elements pointed 64697403Sobrien * to by the iterators are not equal. 64797403Sobrien */ 648132720Skan template<typename _InputIterator1, typename _InputIterator2, 649132720Skan typename _BinaryPredicate> 650132720Skan pair<_InputIterator1, _InputIterator2> 651132720Skan mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 652132720Skan _InputIterator2 __first2, _BinaryPredicate __binary_pred) 65397403Sobrien { 65497403Sobrien // concept requirements 655132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 656132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 657132720Skan __glibcxx_requires_valid_range(__first1, __last1); 65897403Sobrien 659132720Skan while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) 660132720Skan { 661132720Skan ++__first1; 662132720Skan ++__first2; 663132720Skan } 664132720Skan return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 66597403Sobrien } 66697403Sobrien 66797403Sobrien /** 66897403Sobrien * @brief Tests a range for element-wise equality. 66997403Sobrien * @param first1 An input iterator. 67097403Sobrien * @param last1 An input iterator. 67197403Sobrien * @param first2 An input iterator. 67297403Sobrien * @return A boolean true or false. 67397403Sobrien * 67497403Sobrien * This compares the elements of two ranges using @c == and returns true or 67597403Sobrien * false depending on whether all of the corresponding elements of the 67697403Sobrien * ranges are equal. 67797403Sobrien */ 678132720Skan template<typename _InputIterator1, typename _InputIterator2> 67997403Sobrien inline bool 680132720Skan equal(_InputIterator1 __first1, _InputIterator1 __last1, 681132720Skan _InputIterator2 __first2) 68297403Sobrien { 68397403Sobrien // concept requirements 684132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 685132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 686132720Skan __glibcxx_function_requires(_EqualOpConcept< 687132720Skan typename iterator_traits<_InputIterator1>::value_type, 688132720Skan typename iterator_traits<_InputIterator2>::value_type>) 689132720Skan __glibcxx_requires_valid_range(__first1, __last1); 69097403Sobrien 69197403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2) 69297403Sobrien if (!(*__first1 == *__first2)) 69397403Sobrien return false; 69497403Sobrien return true; 69597403Sobrien } 69697403Sobrien 69797403Sobrien /** 69897403Sobrien * @brief Tests a range for element-wise equality. 69997403Sobrien * @param first1 An input iterator. 70097403Sobrien * @param last1 An input iterator. 70197403Sobrien * @param first2 An input iterator. 70297403Sobrien * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. 70397403Sobrien * @return A boolean true or false. 70497403Sobrien * 70597403Sobrien * This compares the elements of two ranges using the binary_pred 70697403Sobrien * parameter, and returns true or 70797403Sobrien * false depending on whether all of the corresponding elements of the 70897403Sobrien * ranges are equal. 70997403Sobrien */ 710132720Skan template<typename _InputIterator1, typename _InputIterator2, 711132720Skan typename _BinaryPredicate> 71297403Sobrien inline bool 713132720Skan equal(_InputIterator1 __first1, _InputIterator1 __last1, 714132720Skan _InputIterator2 __first2, 71597403Sobrien _BinaryPredicate __binary_pred) 71697403Sobrien { 71797403Sobrien // concept requirements 718132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 719132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 720132720Skan __glibcxx_requires_valid_range(__first1, __last1); 72197403Sobrien 72297403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2) 72397403Sobrien if (!__binary_pred(*__first1, *__first2)) 72497403Sobrien return false; 72597403Sobrien return true; 72697403Sobrien } 72797403Sobrien 72897403Sobrien /** 72997403Sobrien * @brief Performs "dictionary" comparison on ranges. 73097403Sobrien * @param first1 An input iterator. 73197403Sobrien * @param last1 An input iterator. 73297403Sobrien * @param first2 An input iterator. 73397403Sobrien * @param last2 An input iterator. 73497403Sobrien * @return A boolean true or false. 73597403Sobrien * 73697403Sobrien * "Returns true if the sequence of elements defined by the range 73797403Sobrien * [first1,last1) is lexicographically less than the sequence of elements 73897403Sobrien * defined by the range [first2,last2). Returns false otherwise." 73997403Sobrien * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 74097403Sobrien * then this is an inline call to @c memcmp. 74197403Sobrien */ 742132720Skan template<typename _InputIterator1, typename _InputIterator2> 74397403Sobrien bool 744132720Skan lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 745132720Skan _InputIterator2 __first2, _InputIterator2 __last2) 74697403Sobrien { 74797403Sobrien // concept requirements 748132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 749132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 750132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 751132720Skan typename iterator_traits<_InputIterator1>::value_type>) 752132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 753132720Skan typename iterator_traits<_InputIterator2>::value_type>) 754132720Skan __glibcxx_requires_valid_range(__first1, __last1); 755132720Skan __glibcxx_requires_valid_range(__first2, __last2); 75697403Sobrien 757132720Skan for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 758132720Skan { 759132720Skan if (*__first1 < *__first2) 760132720Skan return true; 761132720Skan if (*__first2 < *__first1) 762132720Skan return false; 763132720Skan } 76497403Sobrien return __first1 == __last1 && __first2 != __last2; 76597403Sobrien } 76697403Sobrien 76797403Sobrien /** 76897403Sobrien * @brief Performs "dictionary" comparison on ranges. 76997403Sobrien * @param first1 An input iterator. 77097403Sobrien * @param last1 An input iterator. 77197403Sobrien * @param first2 An input iterator. 77297403Sobrien * @param last2 An input iterator. 77397403Sobrien * @param comp A @link s20_3_3_comparisons comparison functor@endlink. 77497403Sobrien * @return A boolean true or false. 77597403Sobrien * 77697403Sobrien * The same as the four-parameter @c lexigraphical_compare, but uses the 77797403Sobrien * comp parameter instead of @c <. 77897403Sobrien */ 779132720Skan template<typename _InputIterator1, typename _InputIterator2, 780132720Skan typename _Compare> 78197403Sobrien bool 782132720Skan lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, 783132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 78497403Sobrien _Compare __comp) 78597403Sobrien { 78697403Sobrien // concept requirements 787132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 788132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 789132720Skan __glibcxx_requires_valid_range(__first1, __last1); 790132720Skan __glibcxx_requires_valid_range(__first2, __last2); 79197403Sobrien 79297403Sobrien for ( ; __first1 != __last1 && __first2 != __last2 793132720Skan ; ++__first1, ++__first2) 794132720Skan { 795132720Skan if (__comp(*__first1, *__first2)) 796132720Skan return true; 797132720Skan if (__comp(*__first2, *__first1)) 798132720Skan return false; 799132720Skan } 80097403Sobrien return __first1 == __last1 && __first2 != __last2; 80197403Sobrien } 80297403Sobrien 803132720Skan inline bool 804132720Skan lexicographical_compare(const unsigned char* __first1, 805132720Skan const unsigned char* __last1, 806132720Skan const unsigned char* __first2, 807132720Skan const unsigned char* __last2) 80897403Sobrien { 809132720Skan __glibcxx_requires_valid_range(__first1, __last1); 810132720Skan __glibcxx_requires_valid_range(__first2, __last2); 811132720Skan 81297403Sobrien const size_t __len1 = __last1 - __first1; 81397403Sobrien const size_t __len2 = __last2 - __first2; 814132720Skan const int __result = std::memcmp(__first1, __first2, 815132720Skan std::min(__len1, __len2)); 81697403Sobrien return __result != 0 ? __result < 0 : __len1 < __len2; 81797403Sobrien } 81897403Sobrien 81997403Sobrien inline bool 82097403Sobrien lexicographical_compare(const char* __first1, const char* __last1, 82197403Sobrien const char* __first2, const char* __last2) 82297403Sobrien { 823132720Skan __glibcxx_requires_valid_range(__first1, __last1); 824132720Skan __glibcxx_requires_valid_range(__first2, __last2); 825132720Skan 82697403Sobrien#if CHAR_MAX == SCHAR_MAX 827132720Skan return std::lexicographical_compare((const signed char*) __first1, 828132720Skan (const signed char*) __last1, 829132720Skan (const signed char*) __first2, 830132720Skan (const signed char*) __last2); 83197403Sobrien#else /* CHAR_MAX == SCHAR_MAX */ 832132720Skan return std::lexicographical_compare((const unsigned char*) __first1, 833132720Skan (const unsigned char*) __last1, 834132720Skan (const unsigned char*) __first2, 835132720Skan (const unsigned char*) __last2); 83697403Sobrien#endif /* CHAR_MAX == SCHAR_MAX */ 83797403Sobrien } 83897403Sobrien 83997403Sobrien} // namespace std 84097403Sobrien 841132720Skan#endif 842