libstdc++
stl_numeric.h
Go to the documentation of this file.
00001 // Numeric functions implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996,1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_numeric.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{numeric}
00054  */
00055 
00056 #ifndef _STL_NUMERIC_H
00057 #define _STL_NUMERIC_H 1
00058 
00059 #include <bits/concept_check.h>
00060 #include <debug/debug.h>
00061 #include <bits/move.h> // For _GLIBCXX_MOVE
00062 
00063 #if __cplusplus >= 201103L
00064 
00065 namespace std _GLIBCXX_VISIBILITY(default)
00066 {
00067 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00068 
00069   /**
00070    *  @brief  Create a range of sequentially increasing values.
00071    *
00072    *  For each element in the range @p [first,last) assigns @p value and
00073    *  increments @p value as if by @p ++value.
00074    *
00075    *  @param  __first  Start of range.
00076    *  @param  __last  End of range.
00077    *  @param  __value  Starting value.
00078    *  @return  Nothing.
00079    */
00080   template<typename _ForwardIterator, typename _Tp>
00081     void
00082     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
00083     {
00084       // concept requirements
00085       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00086                                   _ForwardIterator>)
00087       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00088             typename iterator_traits<_ForwardIterator>::value_type>)
00089       __glibcxx_requires_valid_range(__first, __last);
00090 
00091       for (; __first != __last; ++__first)
00092         {
00093           *__first = __value;
00094           ++__value;
00095         }
00096     }
00097 
00098 _GLIBCXX_END_NAMESPACE_VERSION
00099 } // namespace std
00100 
00101 #endif
00102 
00103 namespace std _GLIBCXX_VISIBILITY(default)
00104 {
00105 _GLIBCXX_BEGIN_NAMESPACE_ALGO
00106 
00107 #if __cplusplus > 201703L
00108 // _GLIBCXX_RESOLVE_LIB_DEFECTS
00109 // DR 2055. std::move in std::accumulate and other algorithms
00110 # define _GLIBCXX_MOVE_IF_20(_E) std::move(_E)
00111 #else
00112 # define _GLIBCXX_MOVE_IF_20(_E) _E
00113 #endif
00114 
00115   /**
00116    *  @brief  Accumulate values in a range.
00117    *
00118    *  Accumulates the values in the range [first,last) using operator+().  The
00119    *  initial value is @a init.  The values are processed in order.
00120    *
00121    *  @param  __first  Start of range.
00122    *  @param  __last  End of range.
00123    *  @param  __init  Starting value to add other values to.
00124    *  @return  The final sum.
00125    */
00126   template<typename _InputIterator, typename _Tp>
00127     inline _Tp
00128     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
00129     {
00130       // concept requirements
00131       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00132       __glibcxx_requires_valid_range(__first, __last);
00133 
00134       for (; __first != __last; ++__first)
00135         __init = _GLIBCXX_MOVE_IF_20(__init) + *__first;
00136       return __init;
00137     }
00138 
00139   /**
00140    *  @brief  Accumulate values in a range with operation.
00141    *
00142    *  Accumulates the values in the range [first,last) using the function
00143    *  object @p __binary_op.  The initial value is @p __init.  The values are
00144    *  processed in order.
00145    *
00146    *  @param  __first  Start of range.
00147    *  @param  __last  End of range.
00148    *  @param  __init  Starting value to add other values to.
00149    *  @param  __binary_op  Function object to accumulate with.
00150    *  @return  The final sum.
00151    */
00152   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
00153     inline _Tp
00154     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
00155                _BinaryOperation __binary_op)
00156     {
00157       // concept requirements
00158       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00159       __glibcxx_requires_valid_range(__first, __last);
00160 
00161       for (; __first != __last; ++__first)
00162         __init = __binary_op(_GLIBCXX_MOVE_IF_20(__init), *__first);
00163       return __init;
00164     }
00165 
00166   /**
00167    *  @brief  Compute inner product of two ranges.
00168    *
00169    *  Starting with an initial value of @p __init, multiplies successive
00170    *  elements from the two ranges and adds each product into the accumulated
00171    *  value using operator+().  The values in the ranges are processed in
00172    *  order.
00173    *
00174    *  @param  __first1  Start of range 1.
00175    *  @param  __last1  End of range 1.
00176    *  @param  __first2  Start of range 2.
00177    *  @param  __init  Starting value to add other values to.
00178    *  @return  The final inner product.
00179    */
00180   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
00181     inline _Tp
00182     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00183                   _InputIterator2 __first2, _Tp __init)
00184     {
00185       // concept requirements
00186       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00187       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00188       __glibcxx_requires_valid_range(__first1, __last1);
00189 
00190       for (; __first1 != __last1; ++__first1, (void)++__first2)
00191         __init = _GLIBCXX_MOVE_IF_20(__init) + (*__first1 * *__first2);
00192       return __init;
00193     }
00194 
00195   /**
00196    *  @brief  Compute inner product of two ranges.
00197    *
00198    *  Starting with an initial value of @p __init, applies @p __binary_op2 to
00199    *  successive elements from the two ranges and accumulates each result into
00200    *  the accumulated value using @p __binary_op1.  The values in the ranges are
00201    *  processed in order.
00202    *
00203    *  @param  __first1  Start of range 1.
00204    *  @param  __last1  End of range 1.
00205    *  @param  __first2  Start of range 2.
00206    *  @param  __init  Starting value to add other values to.
00207    *  @param  __binary_op1  Function object to accumulate with.
00208    *  @param  __binary_op2  Function object to apply to pairs of input values.
00209    *  @return  The final inner product.
00210    */
00211   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
00212            typename _BinaryOperation1, typename _BinaryOperation2>
00213     inline _Tp
00214     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00215                   _InputIterator2 __first2, _Tp __init,
00216                   _BinaryOperation1 __binary_op1,
00217                   _BinaryOperation2 __binary_op2)
00218     {
00219       // concept requirements
00220       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00221       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00222       __glibcxx_requires_valid_range(__first1, __last1);
00223 
00224       for (; __first1 != __last1; ++__first1, (void)++__first2)
00225         __init = __binary_op1(_GLIBCXX_MOVE_IF_20(__init),
00226                               __binary_op2(*__first1, *__first2));
00227       return __init;
00228     }
00229 
00230   /**
00231    *  @brief  Return list of partial sums
00232    *
00233    *  Accumulates the values in the range [first,last) using the @c + operator.
00234    *  As each successive input value is added into the total, that partial sum
00235    *  is written to @p __result.  Therefore, the first value in @p __result is
00236    *  the first value of the input, the second value in @p __result is the sum
00237    *  of the first and second input values, and so on.
00238    *
00239    *  @param  __first  Start of input range.
00240    *  @param  __last  End of input range.
00241    *  @param  __result  Output sum.
00242    *  @return  Iterator pointing just beyond the values written to __result.
00243    */
00244   template<typename _InputIterator, typename _OutputIterator>
00245     _OutputIterator
00246     partial_sum(_InputIterator __first, _InputIterator __last,
00247                 _OutputIterator __result)
00248     {
00249       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00250 
00251       // concept requirements
00252       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00253       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00254                                                          _ValueType>)
00255       __glibcxx_requires_valid_range(__first, __last);
00256 
00257       if (__first == __last)
00258         return __result;
00259       _ValueType __value = *__first;
00260       *__result = __value;
00261       while (++__first != __last)
00262         {
00263           __value = _GLIBCXX_MOVE_IF_20(__value) + *__first;
00264           *++__result = __value;
00265         }
00266       return ++__result;
00267     }
00268 
00269   /**
00270    *  @brief  Return list of partial sums
00271    *
00272    *  Accumulates the values in the range [first,last) using @p __binary_op.
00273    *  As each successive input value is added into the total, that partial sum
00274    *  is written to @p __result.  Therefore, the first value in @p __result is
00275    *  the first value of the input, the second value in @p __result is the sum
00276    *  of the first and second input values, and so on.
00277    *
00278    *  @param  __first  Start of input range.
00279    *  @param  __last  End of input range.
00280    *  @param  __result  Output sum.
00281    *  @param  __binary_op  Function object.
00282    *  @return  Iterator pointing just beyond the values written to __result.
00283    */
00284   template<typename _InputIterator, typename _OutputIterator,
00285            typename _BinaryOperation>
00286     _OutputIterator
00287     partial_sum(_InputIterator __first, _InputIterator __last,
00288                 _OutputIterator __result, _BinaryOperation __binary_op)
00289     {
00290       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00291 
00292       // concept requirements
00293       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00294       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00295                                                          _ValueType>)
00296       __glibcxx_requires_valid_range(__first, __last);
00297 
00298       if (__first == __last)
00299         return __result;
00300       _ValueType __value = *__first;
00301       *__result = __value;
00302       while (++__first != __last)
00303         {
00304           __value = __binary_op(_GLIBCXX_MOVE_IF_20(__value), *__first);
00305           *++__result = __value;
00306         }
00307       return ++__result;
00308     }
00309 
00310   /**
00311    *  @brief  Return differences between adjacent values.
00312    *
00313    *  Computes the difference between adjacent values in the range
00314    *  [first,last) using operator-() and writes the result to @p __result.
00315    *
00316    *  @param  __first  Start of input range.
00317    *  @param  __last  End of input range.
00318    *  @param  __result  Output sums.
00319    *  @return  Iterator pointing just beyond the values written to result.
00320    *
00321    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
00322    *  DR 539. partial_sum and adjacent_difference should mention requirements
00323    */
00324   template<typename _InputIterator, typename _OutputIterator>
00325     _OutputIterator
00326     adjacent_difference(_InputIterator __first,
00327                         _InputIterator __last, _OutputIterator __result)
00328     {
00329       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00330 
00331       // concept requirements
00332       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00333       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00334                                                          _ValueType>)
00335       __glibcxx_requires_valid_range(__first, __last);
00336 
00337       if (__first == __last)
00338         return __result;
00339       _ValueType __value = *__first;
00340       *__result = __value;
00341       while (++__first != __last)
00342         {
00343           _ValueType __tmp = *__first;
00344           *++__result = __tmp - _GLIBCXX_MOVE_IF_20(__value);
00345           __value = _GLIBCXX_MOVE(__tmp);
00346         }
00347       return ++__result;
00348     }
00349 
00350   /**
00351    *  @brief  Return differences between adjacent values.
00352    *
00353    *  Computes the difference between adjacent values in the range
00354    *  [__first,__last) using the function object @p __binary_op and writes the
00355    *  result to @p __result.
00356    *
00357    *  @param  __first  Start of input range.
00358    *  @param  __last  End of input range.
00359    *  @param  __result  Output sum.
00360    *  @param  __binary_op Function object.
00361    *  @return  Iterator pointing just beyond the values written to result.
00362    *
00363    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
00364    *  DR 539. partial_sum and adjacent_difference should mention requirements
00365    */
00366   template<typename _InputIterator, typename _OutputIterator,
00367            typename _BinaryOperation>
00368     _OutputIterator
00369     adjacent_difference(_InputIterator __first, _InputIterator __last,
00370                         _OutputIterator __result, _BinaryOperation __binary_op)
00371     {
00372       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00373 
00374       // concept requirements
00375       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00376       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00377                                                          _ValueType>)
00378       __glibcxx_requires_valid_range(__first, __last);
00379 
00380       if (__first == __last)
00381         return __result;
00382       _ValueType __value = *__first;
00383       *__result = __value;
00384       while (++__first != __last)
00385         {
00386           _ValueType __tmp = *__first;
00387           *++__result = __binary_op(__tmp, _GLIBCXX_MOVE_IF_20(__value));
00388           __value = _GLIBCXX_MOVE(__tmp);
00389         }
00390       return ++__result;
00391     }
00392 
00393 #undef _GLIBCXX_MOVE_IF_20
00394 
00395 _GLIBCXX_END_NAMESPACE_ALGO
00396 } // namespace std
00397 
00398 #endif /* _STL_NUMERIC_H */