libstdc++
stl_numeric.h
Go to the documentation of this file.
1 // Numeric functions implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2019 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996,1997
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_numeric.h
52  * This is an internal header file, included by other library headers.
53  * Do not attempt to use it directly. @headername{numeric}
54  */
55 
56 #ifndef _STL_NUMERIC_H
57 #define _STL_NUMERIC_H 1
58 
59 #include <bits/concept_check.h>
60 #include <debug/debug.h>
61 #include <bits/move.h> // For _GLIBCXX_MOVE
62 
63 #if __cplusplus >= 201103L
64 
65 namespace std _GLIBCXX_VISIBILITY(default)
66 {
67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
68 
69  /**
70  * @brief Create a range of sequentially increasing values.
71  *
72  * For each element in the range @p [first,last) assigns @p value and
73  * increments @p value as if by @p ++value.
74  *
75  * @param __first Start of range.
76  * @param __last End of range.
77  * @param __value Starting value.
78  * @return Nothing.
79  */
80  template<typename _ForwardIterator, typename _Tp>
81  void
82  iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
83  {
84  // concept requirements
85  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
86  _ForwardIterator>)
87  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
88  typename iterator_traits<_ForwardIterator>::value_type>)
89  __glibcxx_requires_valid_range(__first, __last);
90 
91  for (; __first != __last; ++__first)
92  {
93  *__first = __value;
94  ++__value;
95  }
96  }
97 
98 _GLIBCXX_END_NAMESPACE_VERSION
99 } // namespace std
100 
101 #endif
102 
103 namespace std _GLIBCXX_VISIBILITY(default)
104 {
105 _GLIBCXX_BEGIN_NAMESPACE_ALGO
106 
107 #if __cplusplus > 201703L
108 // _GLIBCXX_RESOLVE_LIB_DEFECTS
109 // DR 2055. std::move in std::accumulate and other algorithms
110 # define _GLIBCXX_MOVE_IF_20(_E) std::move(_E)
111 #else
112 # define _GLIBCXX_MOVE_IF_20(_E) _E
113 #endif
114 
115  /**
116  * @brief Accumulate values in a range.
117  *
118  * Accumulates the values in the range [first,last) using operator+(). The
119  * initial value is @a init. The values are processed in order.
120  *
121  * @param __first Start of range.
122  * @param __last End of range.
123  * @param __init Starting value to add other values to.
124  * @return The final sum.
125  */
126  template<typename _InputIterator, typename _Tp>
127  inline _Tp
128  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
129  {
130  // concept requirements
131  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
132  __glibcxx_requires_valid_range(__first, __last);
133 
134  for (; __first != __last; ++__first)
135  __init = _GLIBCXX_MOVE_IF_20(__init) + *__first;
136  return __init;
137  }
138 
139  /**
140  * @brief Accumulate values in a range with operation.
141  *
142  * Accumulates the values in the range [first,last) using the function
143  * object @p __binary_op. The initial value is @p __init. The values are
144  * processed in order.
145  *
146  * @param __first Start of range.
147  * @param __last End of range.
148  * @param __init Starting value to add other values to.
149  * @param __binary_op Function object to accumulate with.
150  * @return The final sum.
151  */
152  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
153  inline _Tp
154  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
155  _BinaryOperation __binary_op)
156  {
157  // concept requirements
158  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
159  __glibcxx_requires_valid_range(__first, __last);
160 
161  for (; __first != __last; ++__first)
162  __init = __binary_op(_GLIBCXX_MOVE_IF_20(__init), *__first);
163  return __init;
164  }
165 
166  /**
167  * @brief Compute inner product of two ranges.
168  *
169  * Starting with an initial value of @p __init, multiplies successive
170  * elements from the two ranges and adds each product into the accumulated
171  * value using operator+(). The values in the ranges are processed in
172  * order.
173  *
174  * @param __first1 Start of range 1.
175  * @param __last1 End of range 1.
176  * @param __first2 Start of range 2.
177  * @param __init Starting value to add other values to.
178  * @return The final inner product.
179  */
180  template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
181  inline _Tp
182  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
183  _InputIterator2 __first2, _Tp __init)
184  {
185  // concept requirements
186  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
187  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
188  __glibcxx_requires_valid_range(__first1, __last1);
189 
190  for (; __first1 != __last1; ++__first1, (void)++__first2)
191  __init = _GLIBCXX_MOVE_IF_20(__init) + (*__first1 * *__first2);
192  return __init;
193  }
194 
195  /**
196  * @brief Compute inner product of two ranges.
197  *
198  * Starting with an initial value of @p __init, applies @p __binary_op2 to
199  * successive elements from the two ranges and accumulates each result into
200  * the accumulated value using @p __binary_op1. The values in the ranges are
201  * processed in order.
202  *
203  * @param __first1 Start of range 1.
204  * @param __last1 End of range 1.
205  * @param __first2 Start of range 2.
206  * @param __init Starting value to add other values to.
207  * @param __binary_op1 Function object to accumulate with.
208  * @param __binary_op2 Function object to apply to pairs of input values.
209  * @return The final inner product.
210  */
211  template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
212  typename _BinaryOperation1, typename _BinaryOperation2>
213  inline _Tp
214  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
215  _InputIterator2 __first2, _Tp __init,
216  _BinaryOperation1 __binary_op1,
217  _BinaryOperation2 __binary_op2)
218  {
219  // concept requirements
220  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
221  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
222  __glibcxx_requires_valid_range(__first1, __last1);
223 
224  for (; __first1 != __last1; ++__first1, (void)++__first2)
225  __init = __binary_op1(_GLIBCXX_MOVE_IF_20(__init),
226  __binary_op2(*__first1, *__first2));
227  return __init;
228  }
229 
230  /**
231  * @brief Return list of partial sums
232  *
233  * Accumulates the values in the range [first,last) using the @c + operator.
234  * As each successive input value is added into the total, that partial sum
235  * is written to @p __result. Therefore, the first value in @p __result is
236  * the first value of the input, the second value in @p __result is the sum
237  * of the first and second input values, and so on.
238  *
239  * @param __first Start of input range.
240  * @param __last End of input range.
241  * @param __result Output sum.
242  * @return Iterator pointing just beyond the values written to __result.
243  */
244  template<typename _InputIterator, typename _OutputIterator>
245  _OutputIterator
246  partial_sum(_InputIterator __first, _InputIterator __last,
247  _OutputIterator __result)
248  {
249  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
250 
251  // concept requirements
252  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
253  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
254  _ValueType>)
255  __glibcxx_requires_valid_range(__first, __last);
256 
257  if (__first == __last)
258  return __result;
259  _ValueType __value = *__first;
260  *__result = __value;
261  while (++__first != __last)
262  {
263  __value = _GLIBCXX_MOVE_IF_20(__value) + *__first;
264  *++__result = __value;
265  }
266  return ++__result;
267  }
268 
269  /**
270  * @brief Return list of partial sums
271  *
272  * Accumulates the values in the range [first,last) using @p __binary_op.
273  * As each successive input value is added into the total, that partial sum
274  * is written to @p __result. Therefore, the first value in @p __result is
275  * the first value of the input, the second value in @p __result is the sum
276  * of the first and second input values, and so on.
277  *
278  * @param __first Start of input range.
279  * @param __last End of input range.
280  * @param __result Output sum.
281  * @param __binary_op Function object.
282  * @return Iterator pointing just beyond the values written to __result.
283  */
284  template<typename _InputIterator, typename _OutputIterator,
285  typename _BinaryOperation>
286  _OutputIterator
287  partial_sum(_InputIterator __first, _InputIterator __last,
288  _OutputIterator __result, _BinaryOperation __binary_op)
289  {
290  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
291 
292  // concept requirements
293  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
294  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
295  _ValueType>)
296  __glibcxx_requires_valid_range(__first, __last);
297 
298  if (__first == __last)
299  return __result;
300  _ValueType __value = *__first;
301  *__result = __value;
302  while (++__first != __last)
303  {
304  __value = __binary_op(_GLIBCXX_MOVE_IF_20(__value), *__first);
305  *++__result = __value;
306  }
307  return ++__result;
308  }
309 
310  /**
311  * @brief Return differences between adjacent values.
312  *
313  * Computes the difference between adjacent values in the range
314  * [first,last) using operator-() and writes the result to @p __result.
315  *
316  * @param __first Start of input range.
317  * @param __last End of input range.
318  * @param __result Output sums.
319  * @return Iterator pointing just beyond the values written to result.
320  *
321  * _GLIBCXX_RESOLVE_LIB_DEFECTS
322  * DR 539. partial_sum and adjacent_difference should mention requirements
323  */
324  template<typename _InputIterator, typename _OutputIterator>
325  _OutputIterator
326  adjacent_difference(_InputIterator __first,
327  _InputIterator __last, _OutputIterator __result)
328  {
329  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
330 
331  // concept requirements
332  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
333  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
334  _ValueType>)
335  __glibcxx_requires_valid_range(__first, __last);
336 
337  if (__first == __last)
338  return __result;
339  _ValueType __value = *__first;
340  *__result = __value;
341  while (++__first != __last)
342  {
343  _ValueType __tmp = *__first;
344  *++__result = __tmp - _GLIBCXX_MOVE_IF_20(__value);
345  __value = _GLIBCXX_MOVE(__tmp);
346  }
347  return ++__result;
348  }
349 
350  /**
351  * @brief Return differences between adjacent values.
352  *
353  * Computes the difference between adjacent values in the range
354  * [__first,__last) using the function object @p __binary_op and writes the
355  * result to @p __result.
356  *
357  * @param __first Start of input range.
358  * @param __last End of input range.
359  * @param __result Output sum.
360  * @param __binary_op Function object.
361  * @return Iterator pointing just beyond the values written to result.
362  *
363  * _GLIBCXX_RESOLVE_LIB_DEFECTS
364  * DR 539. partial_sum and adjacent_difference should mention requirements
365  */
366  template<typename _InputIterator, typename _OutputIterator,
367  typename _BinaryOperation>
368  _OutputIterator
369  adjacent_difference(_InputIterator __first, _InputIterator __last,
370  _OutputIterator __result, _BinaryOperation __binary_op)
371  {
372  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
373 
374  // concept requirements
375  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
376  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
377  _ValueType>)
378  __glibcxx_requires_valid_range(__first, __last);
379 
380  if (__first == __last)
381  return __result;
382  _ValueType __value = *__first;
383  *__result = __value;
384  while (++__first != __last)
385  {
386  _ValueType __tmp = *__first;
387  *++__result = __binary_op(__tmp, _GLIBCXX_MOVE_IF_20(__value));
388  __value = _GLIBCXX_MOVE(__tmp);
389  }
390  return ++__result;
391  }
392 
393 #undef _GLIBCXX_MOVE_IF_20
394 
395 _GLIBCXX_END_NAMESPACE_ALGO
396 } // namespace std
397 
398 #endif /* _STL_NUMERIC_H */
_OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
Return differences between adjacent values.
Definition: stl_numeric.h:326
_Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)
Compute inner product of two ranges.
Definition: stl_numeric.h:182
void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
Definition: stl_numeric.h:82
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
Accumulate values in a range.
Definition: stl_numeric.h:128
_OutputIterator partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
Return list of partial sums.
Definition: stl_numeric.h:246