libstdc++
stl_numeric.h
Go to the documentation of this file.
1 // Numeric functions implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2014 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  /**
108  * @brief Accumulate values in a range.
109  *
110  * Accumulates the values in the range [first,last) using operator+(). The
111  * initial value is @a init. The values are processed in order.
112  *
113  * @param __first Start of range.
114  * @param __last End of range.
115  * @param __init Starting value to add other values to.
116  * @return The final sum.
117  */
118  template<typename _InputIterator, typename _Tp>
119  inline _Tp
120  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
121  {
122  // concept requirements
123  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
124  __glibcxx_requires_valid_range(__first, __last);
125 
126  for (; __first != __last; ++__first)
127  __init = __init + *__first;
128  return __init;
129  }
130 
131  /**
132  * @brief Accumulate values in a range with operation.
133  *
134  * Accumulates the values in the range [first,last) using the function
135  * object @p __binary_op. The initial value is @p __init. The values are
136  * processed in order.
137  *
138  * @param __first Start of range.
139  * @param __last End of range.
140  * @param __init Starting value to add other values to.
141  * @param __binary_op Function object to accumulate with.
142  * @return The final sum.
143  */
144  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
145  inline _Tp
146  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
147  _BinaryOperation __binary_op)
148  {
149  // concept requirements
150  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
151  __glibcxx_requires_valid_range(__first, __last);
152 
153  for (; __first != __last; ++__first)
154  __init = __binary_op(__init, *__first);
155  return __init;
156  }
157 
158  /**
159  * @brief Compute inner product of two ranges.
160  *
161  * Starting with an initial value of @p __init, multiplies successive
162  * elements from the two ranges and adds each product into the accumulated
163  * value using operator+(). The values in the ranges are processed in
164  * order.
165  *
166  * @param __first1 Start of range 1.
167  * @param __last1 End of range 1.
168  * @param __first2 Start of range 2.
169  * @param __init Starting value to add other values to.
170  * @return The final inner product.
171  */
172  template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
173  inline _Tp
174  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
175  _InputIterator2 __first2, _Tp __init)
176  {
177  // concept requirements
178  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
179  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
180  __glibcxx_requires_valid_range(__first1, __last1);
181 
182  for (; __first1 != __last1; ++__first1, ++__first2)
183  __init = __init + (*__first1 * *__first2);
184  return __init;
185  }
186 
187  /**
188  * @brief Compute inner product of two ranges.
189  *
190  * Starting with an initial value of @p __init, applies @p __binary_op2 to
191  * successive elements from the two ranges and accumulates each result into
192  * the accumulated value using @p __binary_op1. The values in the ranges are
193  * processed in order.
194  *
195  * @param __first1 Start of range 1.
196  * @param __last1 End of range 1.
197  * @param __first2 Start of range 2.
198  * @param __init Starting value to add other values to.
199  * @param __binary_op1 Function object to accumulate with.
200  * @param __binary_op2 Function object to apply to pairs of input values.
201  * @return The final inner product.
202  */
203  template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
204  typename _BinaryOperation1, typename _BinaryOperation2>
205  inline _Tp
206  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
207  _InputIterator2 __first2, _Tp __init,
208  _BinaryOperation1 __binary_op1,
209  _BinaryOperation2 __binary_op2)
210  {
211  // concept requirements
212  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
213  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
214  __glibcxx_requires_valid_range(__first1, __last1);
215 
216  for (; __first1 != __last1; ++__first1, ++__first2)
217  __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
218  return __init;
219  }
220 
221  /**
222  * @brief Return list of partial sums
223  *
224  * Accumulates the values in the range [first,last) using the @c + operator.
225  * As each successive input value is added into the total, that partial sum
226  * is written to @p __result. Therefore, the first value in @p __result is
227  * the first value of the input, the second value in @p __result is the sum
228  * of the first and second input values, and so on.
229  *
230  * @param __first Start of input range.
231  * @param __last End of input range.
232  * @param __result Output sum.
233  * @return Iterator pointing just beyond the values written to __result.
234  */
235  template<typename _InputIterator, typename _OutputIterator>
236  _OutputIterator
237  partial_sum(_InputIterator __first, _InputIterator __last,
238  _OutputIterator __result)
239  {
240  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
241 
242  // concept requirements
243  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
244  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
245  _ValueType>)
246  __glibcxx_requires_valid_range(__first, __last);
247 
248  if (__first == __last)
249  return __result;
250  _ValueType __value = *__first;
251  *__result = __value;
252  while (++__first != __last)
253  {
254  __value = __value + *__first;
255  *++__result = __value;
256  }
257  return ++__result;
258  }
259 
260  /**
261  * @brief Return list of partial sums
262  *
263  * Accumulates the values in the range [first,last) using @p __binary_op.
264  * As each successive input value is added into the total, that partial sum
265  * is written to @p __result. Therefore, the first value in @p __result is
266  * the first value of the input, the second value in @p __result is the sum
267  * of the first and second input values, and so on.
268  *
269  * @param __first Start of input range.
270  * @param __last End of input range.
271  * @param __result Output sum.
272  * @param __binary_op Function object.
273  * @return Iterator pointing just beyond the values written to __result.
274  */
275  template<typename _InputIterator, typename _OutputIterator,
276  typename _BinaryOperation>
277  _OutputIterator
278  partial_sum(_InputIterator __first, _InputIterator __last,
279  _OutputIterator __result, _BinaryOperation __binary_op)
280  {
281  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
282 
283  // concept requirements
284  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
285  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
286  _ValueType>)
287  __glibcxx_requires_valid_range(__first, __last);
288 
289  if (__first == __last)
290  return __result;
291  _ValueType __value = *__first;
292  *__result = __value;
293  while (++__first != __last)
294  {
295  __value = __binary_op(__value, *__first);
296  *++__result = __value;
297  }
298  return ++__result;
299  }
300 
301  /**
302  * @brief Return differences between adjacent values.
303  *
304  * Computes the difference between adjacent values in the range
305  * [first,last) using operator-() and writes the result to @p __result.
306  *
307  * @param __first Start of input range.
308  * @param __last End of input range.
309  * @param __result Output sums.
310  * @return Iterator pointing just beyond the values written to result.
311  *
312  * _GLIBCXX_RESOLVE_LIB_DEFECTS
313  * DR 539. partial_sum and adjacent_difference should mention requirements
314  */
315  template<typename _InputIterator, typename _OutputIterator>
316  _OutputIterator
317  adjacent_difference(_InputIterator __first,
318  _InputIterator __last, _OutputIterator __result)
319  {
320  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
321 
322  // concept requirements
323  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
324  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
325  _ValueType>)
326  __glibcxx_requires_valid_range(__first, __last);
327 
328  if (__first == __last)
329  return __result;
330  _ValueType __value = *__first;
331  *__result = __value;
332  while (++__first != __last)
333  {
334  _ValueType __tmp = *__first;
335  *++__result = __tmp - __value;
336  __value = _GLIBCXX_MOVE(__tmp);
337  }
338  return ++__result;
339  }
340 
341  /**
342  * @brief Return differences between adjacent values.
343  *
344  * Computes the difference between adjacent values in the range
345  * [__first,__last) using the function object @p __binary_op and writes the
346  * result to @p __result.
347  *
348  * @param __first Start of input range.
349  * @param __last End of input range.
350  * @param __result Output sum.
351  * @param __binary_op Function object.
352  * @return Iterator pointing just beyond the values written to result.
353  *
354  * _GLIBCXX_RESOLVE_LIB_DEFECTS
355  * DR 539. partial_sum and adjacent_difference should mention requirements
356  */
357  template<typename _InputIterator, typename _OutputIterator,
358  typename _BinaryOperation>
359  _OutputIterator
360  adjacent_difference(_InputIterator __first, _InputIterator __last,
361  _OutputIterator __result, _BinaryOperation __binary_op)
362  {
363  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
364 
365  // concept requirements
366  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
367  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
368  _ValueType>)
369  __glibcxx_requires_valid_range(__first, __last);
370 
371  if (__first == __last)
372  return __result;
373  _ValueType __value = *__first;
374  *__result = __value;
375  while (++__first != __last)
376  {
377  _ValueType __tmp = *__first;
378  *++__result = __binary_op(__tmp, __value);
379  __value = _GLIBCXX_MOVE(__tmp);
380  }
381  return ++__result;
382  }
383 
384 _GLIBCXX_END_NAMESPACE_ALGO
385 } // namespace std
386 
387 #endif /* _STL_NUMERIC_H */
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
Accumulate values in a range.
Definition: stl_numeric.h:120
ISO C++ entities toplevel namespace is std.
void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
Definition: stl_numeric.h:82
_Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)
Compute inner product of two ranges.
Definition: stl_numeric.h:174
_OutputIterator partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
Return list of partial sums.
Definition: stl_numeric.h:237
_OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
Return differences between adjacent values.
Definition: stl_numeric.h:317