Отправлено: 28.07.12 20:19. Заголовок: Предложение по изменению стандарта С++, относящееся к алгоритму std::iota

Я внес предложение по совершенствованию стандарта С++ относительно алгоритма std::iota в группе [url=https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/std-proposals]ISO C++ Standard - Future[/url]

В текущем стандарте С++ алгоритм std::iota объявлен в заголовочном файле <numeric> следующим образом:

 template <class ForwardIterator, class T> 
 void iota(ForwardIterator first, ForwardIterator last, T value);

Как видно из объявления, тип возращаемого значения у данного алгоритма void, то есть функция ничего на самом деле не возвращает.
Вообще-то, это крайне не рачительно не возвращать из функции значение, когда предоставляется такая возможность передать пользователю как можно больше информации. Тип void у функций надо указывать лишь тогда, когда действительно ничего полезного через возвращаемое значение вы передать не можете. Здесь же, то есть в случае с алгоритмом std::iota, совершенно другая ситуация.

Но сначала для тех, кто не знаком с этим алгоритмом, который появился в стандарте С++ 2011, будет полезно узнать, что делает этот алгоритм. Этот алгоритм последовательно присваивает элементам произвольной последовательности из диапазона [first, last} значения value, которые при каждом присвоении увеличиваются на единицу.
То есть, если, например, нужно какому-то одномерному массиву присвоить последовательные значения 1, 2, 3,,, и т.д., то проще всего это сделать с помощью этого алгоритма.

 const size_t N = 10; 
 int a[N]; 
  
 std::iota( std::begin( a ), std::end( a ), 1 );

И тогда элемент массива a[0] будет иметь значение 1, a[2] - 2, и т.д. вплоть до элемента a[9], который будет иметь значение 10.

Это очень удобная штука, когда у вас размер массива достаточно большой, что вручную его инициализировать в виде

 int a[N] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

не представляется возможным.

Спрашивается, ну, и причем здесь возвращаемый тип алгоритма void? Чем он мешает?

На этот недостаток алгоритма сразу же наталкиваешься, когда нужно решить менее тривиальную задачу. И такая задача, которая моментально выявила недостаток этого алгоритма, попалась мне на глаза на одном сайте. Формулировка задачи простая. Есть двумерный массив размерность 10 * 10. Элементы этого двумерного массива нужно заполнить последовательно числами, начиная с 1 и до 10 * 10, то есть до 100.

Если использовать алгоритм std::iota в том виде, в каком он сейчас существует, то придется для каждой следующей строки двумерного массива самостоятельно рассчитывать начальное значение. То есть для первой строки массива начально значение задавалось бы в виде value = 1. Затем, когда наступит черед заполнять следующую строку значениями, нужно будет выполнить предложение value += 10; и т.д.

Нельзя ли как-то обойтись без этих промежуточных вычислений и поручить самому алгоритму отслеживать текущее значение?

Это можно сделать, если переопределить алгоритм std::iota таким образом, чтобы он возвращал заключительное значение параметра value. То есть нужно алгоритм std::iota определить следующим образом:

 template <typename ForwardIterator, typename T> 
 inline T iota( ForwardIterator first, ForwardIterator last, T value ) 
 { 
 	for ( ; first != last; ++first, ++value ) *first = value; 
 	return ( value ); 
 }

В этом определении тип возвращаемого значения заменен с void на тип параметра value, то есть T.

Как теперь можно воспользоваться этим алгоритмом, чтобы инициализировать двумерный массив? Вот обобщенная функция, которая эта делает

 template <typename T, size_t N, size_t M> 
 void init_array( T ( &a )[N][M], T init_value ) 
 { 
  
 	std::accumulate( std::begin( a ), std::end( a ), init_value, 
 			         []( T s, T ( &x )[M] ) 
 		             { 
 						 return ( iota( std::begin( x ), std::end( x ), s ) ); 
 		             } ); 
 }

Здесь внутри алгоритма std::accumulate для каждой строки двумерного массива вызывается модифицированный алгоритм iota, который в свою очередь возвращает заключительное значение параметра value, которое служит начальным значением при последующей итерации по строкам массива.

Это очень удобно! Например, для матрицы размером 10 * 10 при следующих вызовах

 const size_t N = 10; 
 int a[N][N]; 
  
 usr::init_array( a, 1 ); 
 usr::init_array( a, - 100 );

можно последовательно два раза инициализировать матрицу в виде

цитата:

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

и

цитата:

-100 -99 -98 -97 -96 -95 -94 -93 -92 -91 -90 -89 -88 -87 -86 -85 -84 -83 -82 -81 -80 -79 -78 -77 -76 -75 -74 -73 -72 -71 -70 -69 -68 -67 -66 -65 -64 -63 -62 -61 -60 -59 -58 -57 -56 -55 -54 -53 -52 -51 -50 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -39 -38 -37 -36 -35 -34 -33 -32 -31 -30 -29 -28 -27 -26 -25 -24 -23 -22 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1

В любом случае замена типа void возвращаемого значения на что-то значимое у этого алгоритма оказывается более полезным и расширяет возможности применения этого алгоритма.

Есть еще один не менее интересный вариант - это замена возвращаемого типа void на конечное значение итератора, то есть last. Тогда этот алгоритм можно было бы использовать в связке с другими алгоритмами, когда конечный итератор после работы этого алгоритма был бы начальным итератором для другого алгоритма.

Например, мы хотим половину элементов одномерного массива заполнить последовательными значениями по возрастанию, начиная с 1, а все остальные эелементы массива заполнить числом N.
Это можно было бы сделать объяединив два алгоритма в одной строке:

std::fill( std::iota( a, a + N / 2, 1 ), a + N, N );

Здесь возвращаемый конечный итератор из диапазона, задланного для алгоритма std::iota, становится начальным итератором диапазона алгоритма std::fill

Лично я пока склоняюсь к первому варианту изменения std::iota, который я и предложил комитету по стандартизации.

 Отправлено: 28.07.12 20:20. Заголовок: Подготовка моего пре..

Подготовка моего предложения по изменению алгоритма std::iota близится к завершению. Ниже представлен синопсис описания алгоритмов, а также простой пример использования нового алгоритма std::iota_n. Если у кого есть какие-то замечания и предложения по представленному материалу, то можете их высказывать здесь. Это поможет подготовить более грамотно написанное предложение по изменению стандарта С++ перед тем, как я его выложу для обсуждение на соответствующем форуме по рассмотрению предложений по изменению стандарта ISO С++.

цитата:

template <class ForwardIterator, class T> T iota(ForwardIterator first, ForwardIterator last, T value); 1 Requires: T shall be convertible to ForwardIterator’s value type. The expression ++value, where value has type T, shall be well formed. 2 Effects: For each element referred to by the iterator i in the range [first,last), assigns *i = value and increments value as if by ++value. 3 Returns: The last incremented or in case the range is empty the original value of the argument value. 4 Complexity: Exactly last - first assignments and increments. 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 and writable to the output iterator. The type Size shall be convertible to an integral type (4.7, 12.3). 2 Effects: if n is positive then for each iterator in the range [first,first + n) assigns value and increments value as if by ++value. Otherwise it does nothing. 3 Returns: The last incremented or in case n is non-positive the original value of the argument value. 4 Complexity: Exactly n or 0 assignments and increments.

Как слледует из синопсиса предлагается изменить возвращаемое значение у алгоритма std::iota и ввести новый алгоритм std::iota_n аналогично паре стандартных алгоритмов std::fill и std::fill_n

Пример использования измененного алгоритма std::iota был продемонстрирован в первом моем сообщении. Ниже приведен простой пример использования нового алгоритма std::iota_n.

#include <iostream> 
 #include <iterator> 
 #include <vector> 
  
 template <class OutputIterator, class Size, class T> 
 inline T iota_n( OutputIterator first, Size n, T value ) 
 { 
 	for ( ; 0 < n ; --n, ++first, ++value ) *first = value; 
 	return ( value ); 
 } 
  
 int main() 
 { 
 	const size_t N = 10; 
 	std::vector<int> v; 
 	v.reserve( N ); 
  
 	iota_n( std::back_inserter( v ), N, 1 ); 
  
 	std::copy( v.begin(), v.end(), 
 		       std::ostream_iterator<int>( std::cout, " " ) ); 
 	std::cout << std::endl; 
  
 	return 0; 
 }

Edit: уже заметил в примере некоторые погрешности и исправил их.

 Отправлено: 28.07.12 20:21. Заголовок: Кстати сказать в сам..

Кстати сказать в самом Стандарте при описании алгоритма std::iota допущена опечатка: в тексте описания алгоритма используется слово val вместо value, как назван параметр. И кроме того я обратил внимание, что вместо

цитата:

Complexity: Exactly last - first increments and assignments

правильнее будет написать

цитата:

Complexity: Exactly last - first assignments and increments.

так как сначала делается присвоение, а уж затем инкримент.

 Отправлено: 28.07.12 20:22. Заголовок: Пришла в голову така..

Пришла в голову такая идея - объявить еще две модификации алгоритма std::iota. Это алгоритмы std::reverse_iota и std::reverse_iota_n.

Эта идея пришла во время попытки инициализировать односвязный список, который в стандартной библиотеке С++ реализован в виде контейнера std::forward_list.

Чтобы, к примеру, инициалищировать вектор последовательностью чисел от 1 до 10, можно использовать алгоритм std::iota_n, рассмотренный мною выше. Вот пример такой инициализации:

include <iostream>   
 #include <iterator>   
 #include <vector> 
     
  template <class OutputIterator, class Size, class T> 
 inline T iota_n( OutputIterator first, Size n, T value )   
 { 
   	for ( ; 0 < n ; --n, ++first, ++value ) *first = value; 
   	return ( value );   
 } 
  
 int main()   
 { 
   	const size_t N = 10; 
   	std::vector<int> v; 
   	v.reserve( N ); 
  
     	iota_n( std::back_inserter( v ), N, 1 ); 
  
     	std::copy( v.begin(), v.end(), 
                                   std::ostream_iterator<int>( std::cout, " " ) ); 
   	std::cout << std::endl; 
  
     	return 0;   
 }

В результате выполнения этого примера элементы контейнера получат последовательно значения от 1 до 10, начиная с первого элемента контейнера. Все достаточно просто.

Но что делать, если нужно таким же образом инициализировать односвязный список std::forward_list?

У этого контейнера нет члена-функции push_back, чтобы можно было использовать адаптер итераторов std::back_inserter. Попробуем выполнить этот же самый пример с использованием std::forward_list, и заменив std::back_inserter на std::front_inserter, так как односвязный список поддерживает только операцию push_front.

include <iostream>   
 #include <iterator>   
 #include <forward_list> 
     
  template <class OutputIterator, class Size, class T> 
 inline T iota_n( OutputIterator first, Size n, T value )   
 { 
   	for ( ; 0 < n ; --n, ++first, ++value ) *first = value; 
   	return ( value );   
 } 
  
 int main()   
 { 
   	const size_t N = 10; 
 	std::forward_list<int> l; 
  
 	iota_n( std::front_inserter( l ), N, 1 ); 
  
 	std::copy( l.begin(), l.end(),  
                                   std::ostream_iterator<int>( std::cout, " " ) ); 
 	std::cout << std::endl; 
  
  
     	return 0;   
 }

В результатом выполнения этой программы будет следующий вывод на консоль:

цитата:

10 9 8 7 6 5 4 3 2 1

То есть вместо последовательности 1 2 3 4 5 6 7 8 9 10 получилась обратная ей последовательность. Это стало следствием того, что операция push_front вставляет новый элемент перед уже существующим, а не после, как это делает операция push_back, и которая отсутствует в контейнере std::forward_list.

Что тогда делать если требуется возрастающая последовательность целочисленных значений для std::forward_list?

Придется писать свой класс, в котором перегруженный оператор ++ будет выполнять противоположное действие, то есть --. Это что-то вроде реверсивного итератора. Но такого стандартного класса нет. Значит каждый программист будет изобретать свой велосипед.

Вместо этого, на мой взгляд, будет значительно удобнее иметь под рукой стандартное средство в виде алгоритмов std::reverse_iota и std::reverse_iota_n. В этих алгоритмах вместо выражения ++value будет использоваться выражение --value.

Вот как будет выглядеть, например, алгоритм std::reverse_iota_n:

template <class OutputIterator, class Size, class T> 
 inline T reverse_iota_n( OutputIterator first, Size n, T value ) 
 { 
 	for ( ; 0 < n ; --n, ++first, --value ) *first = value; 
 	return ( value ); 
 }

Он, практически, полностью идентичен ранее предложенному мною алгоритму std::iota_n за исключением того, что вместо ++value используется --value. Теперь можно без проблем инициализировать контейнер std::forward_list возрастающей последовательностью целочисленных значений

include <iostream>   
 #include <iterator>   
 #include <forward_list> 
     
  template <class OutputIterator, class Size, class T> 
 inline T reverse_iota_n( OutputIterator first, Size n, T value )   
 { 
   	for ( ; 0 < n ; --n, ++first, --value ) *first = value; 
   	return ( value );   
 } 
  
 int main()   
 { 
   	const size_t N = 10; 
 	std::forward_list<int> l; 
  
 	reverse_iota_n( std::front_inserter( l ), N, N ); 
  
 	std::copy( l.begin(), l.end(),  
                                   std::ostream_iterator<int>( std::cout, " " ) ); 
 	std::cout << std::endl; 
  
  
     	return 0;   
 }

и получить требуемый результат:

цитата:

1 2 3 4 5 6 7 8 9 10

Итак, к ранее описанному предложению по изменению стандарта С++ в части алгоритма std::iota добавляются еще два нововведения - это алгоритмы std::reverse_iota и std::reverse_iota_n.

 Отправлено: 05.11.12 17:04. Заголовок: Мое безграмотное :s..

Мое безграмотное (с точки зрения описания его на английском языке) предложение
по изменению алгоритма std::iota включено Комитетом по стандартизации C++ в список
вопросов, которые будут рассмотрены в ближайшее время в Portland.
Ему присвоен номер N3457 и называется оно Algorithm std::iota and its modifications.

Надеюсь, Комитету хватит благоразумия принять мое предложение по изменению стандарта в части,
касающейся алгоритма std::iota, потому что в том виде, в котором он в настоящее вреия определен,
его использование с моей точки зрения несколько ущербно.

Ознакомиться с моим предложением можно по ссылке

 Отправлено: 05.11.12 18:35. Заголовок: Сегодня случайно по ..

Сегодня случайно по этому адресу обнаружил реализацию алгоритма iota_n через алгоритм std::generate_n с помощью лямбда-выражения.

Вот как выглядет эта реализация

 template<class OutputIterator, class Size, class Assignable> 
 void iota_n(OutputIterator first, Size n, Assignable value) 
 { 
         std::generate_n(first, n, [&value]() { 
                 return value++; 
         }); 
 }

Пример использования этой реализации показан там же по адресу ссылки, которую я привел.

Так как в любом случае для выражения семантического назначения этого алгоритма используется имя iota_n , то естественно лучше делать реализацию этого алгоритма напрямую без использования лямбда-выражения и включить этот алгоритм в стандарт C++.
То есть я этот пример рассматриваю как еще один довод в пользу стандартизации указанных мною ранее модификаций алгоритма sttd::iota.

 Отправлено: 06.11.12 15:08. Заголовок: Оказывается, алгорит..

Оказывается, алгоритм iota был реализован в С++ Алексантдром Степановым еще в далеком 1994 году!

Можно ознакомиться с различными модификациями iota, которые изначально были предложены Степановым,
обратившись к этой ссылке

Как видно из представленного заголовочного файла, Степановым были реализованы следующие модификации iota:

 template <class Iterator, class T> 
 void iota(Iterator first, Iterator last, T value, ptrdiff_t step):

 template <class Iterator, class T> 
 void reverseIota(Iterator first, Iterator last, T value):

 template <class Iterator, class T> 
 void reverseIota(Iterator first, Iterator last, T value, ptrdiff_t step):

 template <class Iterator> 
 void randomIota(Iterator first, Iterator last):

 template <class Iterator> 
 void randomIota(Iterator first, Iterator last, ptrdiff_t step):

 template <class Iterator> 
 void doubleIota(Iterator first, Iterator last):

 template <class Iterator> 
 void doubleIota(Iterator first, Iterator last, ptrdiff_t step):

 template <class Iterator> 
 void doubleReverseIota(Iterator first, Iterator last):

 template <class Iterator> 
 void doubleReverseIota(Iterator first, Iterator last, ptrdiff_t step):

Все алгоритмы этого набора имеют тип возвращаемого значения void в отличии от модификаций алгоритма iota,
которые я предлагаю включить в стандарт. Также Степанов использует имя reverseIota вместо предлагаемого мною reverse_iota. На мой взглдя мое наименование соответствующего алгоритма выглядет более согласованно с системой наименований стандартных алгоритмов.

Кроме того набор алгоритмов, производных от iota, у Степанова значительно более разнообразен. Например, у него имеется алгоритм, в котором можно задавать шаг увеличения или уменьшеения инициализирующего значения. Однако на мой взгляд более гибко и вполне достаточно использовать функциональный объект с перегруженными операторами ++ или -- с обычным алгоритмом iota вместо значения шага.

Но в любом случае знакомство с первоначальными версиями алгоритмов iota, реализованными Александром Степановым, которые хоть и не вошли в стандарт С++, будет познавательным и полезным.