libstdc++
|
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 */