JTC1/SC22/WG21
N3457
Algorithm std::iota and its modifications.
Doc. No.: N3457=12-0147
Date: 2012-10-30
Reply-To: Vladimir Grigoriev (vlad.moscow@mail.ru)
Introduction.
The aim of the proposal is to suggest a changing of algorithm std::iota to make it more flexiable and effective and to enlarge its capabilities by introducing some new its modifications which together with the original algorithm will form a whole family of algorithms derived from std::iota.
The proposal consists of two parts that can be considered independently.
The first part submits a proposition to change the return type of the algorithm from void to the value type.
The second part introduces new modifications of the algorithm that will be useful and form consistent set with other standard algorithms.
Description.
1. Changing the return type of the algorithm.
As the name of header <numeric> implies algorithms declared in this header deal with numeric methods. So numerical values being obtained during executing such an algorithm play important part in these algorithms.
However at present algorithm std::iota declared such a way that the calculated value is lost that limits algorithm's possibilities.
It will be useful to compare algorithm std::iota with algotithm std::fill. They have similar declarations.
template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value);
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
The difference is that during executing algorithm std::fill the value of parameter 'value' is not being changed. It is calculated and will be known before and after the algorithm will be executed.
As for std::iota there is another situation. Firstly, it is unknown what the result value of the parameter 'value' will be, and secondly the value can be important and useful for further its usage in an algorithm chain or as in itself.
Consider the following example. Let assume that we are going to initialize a two-dimensional array with increasing integer numbers. If std::iota would return the result value instead of void we could write
const size_t N = 10;
int a[N][N];
std::accumulate( std::begin( a ), std::end( a ), 1,
[]( int s, int ( &x )[N] )
{
return ( iota( std::begin( x ), std::end( x ), s ) );
} );
After that the array look like
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
In this respect std::iota resembles algorithm std::for_each. The both return the value of its input parameter that can be used further in calculations.
2. Introducing new modifications of std::iota.
If to continue the comparing std::iota with std::fill then the idea to introduce new algorithm std::iota_n inevitably comes to mind. For example that to fill ten elements of a list it could be written
const size_t N = 10;
std::list<int> lst;
std::iota_n( std::back_inserter( lst ), N, 1 );
But the family of algorithms of std::iota would be incomplete without two additional algorithms: std::reverse_iota and std:;reverse_iota_n.
As opposed to std::iota and std::iota_n algorithms std:;reverse_iota and std::reverse_iota_n decrement the value of the parameter 'value'.
Let consider a simple example that demonstrates the both parts of the proposal. Let assume that we need to fill one half of an integer array with increasing values and the other half with decreasing values. It could be done in one line.
const int N = 20;
int a[N];
usr::reverse_iota( a + N / 2, a + N, usr::iota( a, a + N / 2, 0 ) );
Another example. Let consider a filling of std::forward_list. by means of the new modifications of the algorithm std::iota It can be done in two different ways in the direct and reverse order of integer numbers.
const size_t N = 10;
std::forward_list<int> lst1, lst2;
usr::iota_n( std::front_inserter( lst1 ), N, 1 );
usr::reverse_iota_n( std::front_inserter( lst2 ), N, 10 );
Changes to the C++ Standard
Change the declaration of std::iota and add new its modifications to section 26.7.1 Header <numeric> synopsis of the C++ Standard
template <class ForwardIterator, class T>
T iota(ForwardIterator first, ForwardIterator last, T value);
template <class OutputIterator, class Size, class T>
T iota_n(OutputIterator first, Size n, T value);
template <class ForwardIterator, class T>
T reverse_iota(ForwardIterator first, ForwardIterator last, T value);
template <class OutputIterator, class Size, class T>
T reverse_iota_n(OutputIterator first, Size n, T value);
Update section 26.7.6 Iota of the C++ Standard the following way
template <class ForwardIterator, class T>
T iota(ForwardIterator first, ForwardIterator last, T value);
template <class OutputIterator, class Size, class T>
T iota_n(OutputIterator first, Size n, T value);
1 Requires: The expression ++value, where value has type T, shall be well formed. For the first algorithm T shall be convertible to ForwardIterator's value type.
For the second algorithm the expression ++value shall be writable to the output iterator, and the type Size shall be convertible to an integral type (4.7, 12.3).
2. Effects: For each element referred to by the iterator i in the non-empty range [first,last) for the first algorithm, or in the range [first,first + n) if n is positive for the second algorithm, assigns *i = value and increments value as if by ++value. Otherwise they do nothing.
3 Returns: The last incremented or in case the range is empty for the first algorithm or n is non-positive for the second algorithm the original value of the argument value.
4 Complexity: Exactly last - first or exactly n or 0 assignments and increments.
template <class ForwardIterator, class T>
T reverse_iota(ForwardIterator first, ForwardIterator last, T value);
template <class OutputIterator, class Size, class T>
T reverse_iota_n(OutputIterator first, Size n, T value);
1 Requires: The expression --value, where value has type T, shall be well formed. For the first algorithm T shall be convertible to ForwardIterator's value type.
For the second algorithm the expression --value shall be writable to the output iterator, and the type Size shall be convertible to an integral type (4.7, 12.3).
2. Effects: For each element referred to by the iterator i in the non-empty range [first,last) for the first algorithm, or in the range [first,first + n) if n is positive for the second algorithm, assigns *i = value and decrements value as if by --value. Otherwise they do nothing.
3 Returns: The last decremented or in case the range is empty for the first algorithm or n is non-positive for the second algorithm the original value of the argument value.
4 Complexity: Exactly last - first or exactly n or 0 assignments and decrements.