Форум » C/C++ » Предложение по изменению стандарта С++, относящееся к алгоритму std::iota » Ответить

Предложение по изменению стандарта С++, относящееся к алгоритму 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> следующим образом: [pre2] template <class ForwardIterator, class T> void iota(ForwardIterator first, ForwardIterator last, T value);[/pre2] Как видно из объявления, тип возращаемого значения у данного алгоритма void, то есть функция ничего на самом деле не возвращает. Вообще-то, это крайне не рачительно не возвращать из функции значение, когда предоставляется такая возможность передать пользователю как можно больше информации. Тип void у функций надо указывать лишь тогда, когда действительно ничего полезного через возвращаемое значение вы передать не можете. Здесь же, то есть в случае с алгоритмом std::iota, совершенно другая ситуация. Но сначала для тех, кто не знаком с этим алгоритмом, который появился в стандарте С++ 2011, будет полезно узнать, что делает этот алгоритм. Этот алгоритм последовательно присваивает элементам произвольной последовательности из диапазона [first, last} значения value, которые при каждом присвоении увеличиваются на единицу. То есть, если, например, нужно какому-то одномерному массиву присвоить последовательные значения 1, 2, 3,,, и т.д., то проще всего это сделать с помощью этого алгоритма. [pre2] const size_t N = 10; int a[N]; std::iota( std::begin( a ), std::end( a ), 1 );[/pre2] И тогда элемент массива a[0] будет иметь значение 1, a[2] - 2, и т.д. вплоть до элемента a[9], который будет иметь значение 10. Это очень удобная штука, когда у вас размер массива достаточно большой, что вручную его инициализировать в виде [pre2] int a[N] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };[/pre2] не представляется возможным. Спрашивается, ну, и причем здесь возвращаемый тип алгоритма void? Чем он мешает? На этот недостаток алгоритма сразу же наталкиваешься, когда нужно решить менее тривиальную задачу. И такая задача, которая моментально выявила недостаток этого алгоритма, попалась мне на глаза на одном сайте. Формулировка задачи простая. Есть двумерный массив размерность 10 * 10. Элементы этого двумерного массива нужно заполнить последовательно числами, начиная с 1 и до 10 * 10, то есть до 100. Если использовать алгоритм std::iota в том виде, в каком он сейчас существует, то придется для каждой следующей строки двумерного массива самостоятельно рассчитывать начальное значение. То есть для первой строки массива начально значение задавалось бы в виде value = 1. Затем, когда наступит черед заполнять следующую строку значениями, нужно будет выполнить предложение value += 10; и т.д. Нельзя ли как-то обойтись без этих промежуточных вычислений и поручить самому алгоритму отслеживать текущее значение? Это можно сделать, если переопределить алгоритм std::iota таким образом, чтобы он возвращал заключительное значение параметра value. То есть нужно алгоритм std::iota определить следующим образом: [pre2] template <typename ForwardIterator, typename T> inline T iota( ForwardIterator first, ForwardIterator last, T value ) { for ( ; first != last; ++first, ++value ) *first = value; return ( value ); }[/pre2] В этом определении тип возвращаемого значения заменен с void на тип параметра value, то есть T. Как теперь можно воспользоваться этим алгоритмом, чтобы инициализировать двумерный массив? Вот обобщенная функция, которая эта делает [pre2] 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 ) ); } ); }[/pre2] Здесь внутри алгоритма std::accumulate для каждой строки двумерного массива вызывается модифицированный алгоритм iota, который в свою очередь возвращает заключительное значение параметра value, которое служит начальным значением при последующей итерации по строкам массива. Это очень удобно! Например, для матрицы размером 10 * 10 при следующих вызовах [pre2] const size_t N = 10; int a[N][N]; usr::init_array( a, 1 ); usr::init_array( a, - 100 );[/pre2] можно последовательно два раза инициализировать матрицу в виде [quote]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[/quote] и [quote]-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[/quote] В любом случае замена типа void возвращаемого значения на что-то значимое у этого алгоритма оказывается более полезным и расширяет возможности применения этого алгоритма. Есть еще один не менее интересный вариант - это замена возвращаемого типа void на конечное значение итератора, то есть last. Тогда этот алгоритм можно было бы использовать в связке с другими алгоритмами, когда конечный итератор после работы этого алгоритма был бы начальным итератором для другого алгоритма. Например, мы хотим половину элементов одномерного массива заполнить последовательными значениями по возрастанию, начиная с 1, а все остальные эелементы массива заполнить числом N. Это можно было бы сделать объяединив два алгоритма в одной строке: [pre2]std::fill( std::iota( a, a + N / 2, 1 ), a + N, N );[/pre2] Здесь возвращаемый конечный итератор из диапазона, задланного для алгоритма std::iota, становится начальным итератором диапазона алгоритма std::fill Лично я пока склоняюсь к первому варианту изменения std::iota, который я и предложил комитету по стандартизации.

Ответов - 6

Сыроежка: Подготовка моего предложения по изменению алгоритма 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. [pre2]#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; }[/pre2] Edit: уже заметил в примере некоторые погрешности и исправил их.

Сыроежка: Кстати сказать в самом Стандарте при описании алгоритма std::iota допущена опечатка: в тексте описания алгоритма используется слово val вместо value, как назван параметр. И кроме того я обратил внимание, что вместо Complexity: Exactly last - first increments and assignments правильнее будет написать Complexity: Exactly last - first assignments and increments. так как сначала делается присвоение, а уж затем инкримент.

Сыроежка: Пришла в голову такая идея - объявить еще две модификации алгоритма std::iota. Это алгоритмы std::reverse_iota и std::reverse_iota_n. Эта идея пришла во время попытки инициализировать односвязный список, который в стандартной библиотеке С++ реализован в виде контейнера std::forward_list. Чтобы, к примеру, инициалищировать вектор последовательностью чисел от 1 до 10, можно использовать алгоритм std::iota_n, рассмотренный мною выше. Вот пример такой инициализации: [pre2]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; }[/pre2] В результате выполнения этого примера элементы контейнера получат последовательно значения от 1 до 10, начиная с первого элемента контейнера. Все достаточно просто. Но что делать, если нужно таким же образом инициализировать односвязный список std::forward_list? У этого контейнера нет члена-функции push_back, чтобы можно было использовать адаптер итераторов std::back_inserter. Попробуем выполнить этот же самый пример с использованием std::forward_list, и заменив std::back_inserter на std::front_inserter, так как односвязный список поддерживает только операцию push_front. [pre2]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; }[/pre2] В результатом выполнения этой программы будет следующий вывод на консоль: 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: [pre2]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 ); }[/pre2] Он, практически, полностью идентичен ранее предложенному мною алгоритму std::iota_n за исключением того, что вместо ++value используется --value. Теперь можно без проблем инициализировать контейнер std::forward_list возрастающей последовательностью целочисленных значений [pre2]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; }[/pre2] и получить требуемый результат: 1 2 3 4 5 6 7 8 9 10 Итак, к ранее описанному предложению по изменению стандарта С++ в части алгоритма std::iota добавляются еще два нововведения - это алгоритмы std::reverse_iota и std::reverse_iota_n.


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

Сыроежка: Сегодня случайно по этому адресу обнаружил реализацию алгоритма iota_n через алгоритм std::generate_n с помощью лямбда-выражения. Вот как выглядет эта реализация [pre2] template<class OutputIterator, class Size, class Assignable> void iota_n(OutputIterator first, Size n, Assignable value) { std::generate_n(first, n, [&value]() { return value++; }); }[/pre2] Пример использования этой реализации показан там же по адресу ссылки, которую я привел. Так как в любом случае для выражения семантического назначения этого алгоритма используется имя iota_n , то естественно лучше делать реализацию этого алгоритма напрямую без использования лямбда-выражения и включить этот алгоритм в стандарт C++. То есть я этот пример рассматриваю как еще один довод в пользу стандартизации указанных мною ранее модификаций алгоритма sttd::iota.

Сыроежка: Оказывается, алгоритм iota был реализован в С++ Алексантдром Степановым еще в далеком 1994 году! Можно ознакомиться с различными модификациями iota, которые изначально были предложены Степановым, обратившись к этой ссылке Как видно из представленного заголовочного файла, Степановым были реализованы следующие модификации iota: [pre2] template <class Iterator, class T> void iota(Iterator first, Iterator last, T value, ptrdiff_t step):[/pre2] [pre2] template <class Iterator, class T> void reverseIota(Iterator first, Iterator last, T value):[/pre2] [pre2] template <class Iterator, class T> void reverseIota(Iterator first, Iterator last, T value, ptrdiff_t step):[/pre2] [pre2] template <class Iterator> void randomIota(Iterator first, Iterator last):[/pre2] [pre2] template <class Iterator> void randomIota(Iterator first, Iterator last, ptrdiff_t step):[/pre2] [pre2] template <class Iterator> void doubleIota(Iterator first, Iterator last):[/pre2] [pre2] template <class Iterator> void doubleIota(Iterator first, Iterator last, ptrdiff_t step):[/pre2] [pre2] template <class Iterator> void doubleReverseIota(Iterator first, Iterator last):[/pre2] [pre2] template <class Iterator> void doubleReverseIota(Iterator first, Iterator last, ptrdiff_t step):[/pre2] Все алгоритмы этого набора имеют тип возвращаемого значения void в отличии от модификаций алгоритма iota, которые я предлагаю включить в стандарт. Также Степанов использует имя reverseIota вместо предлагаемого мною reverse_iota. На мой взглдя мое наименование соответствующего алгоритма выглядет более согласованно с системой наименований стандартных алгоритмов. Кроме того набор алгоритмов, производных от iota, у Степанова значительно более разнообразен. Например, у него имеется алгоритм, в котором можно задавать шаг увеличения или уменьшеения инициализирующего значения. Однако на мой взгляд более гибко и вполне достаточно использовать функциональный объект с перегруженными операторами ++ или -- с обычным алгоритмом iota вместо значения шага. Но в любом случае знакомство с первоначальными версиями алгоритмов iota, реализованными Александром Степановым, которые хоть и не вошли в стандарт С++, будет познавательным и полезным.



полная версия страницы