On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 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, который я и предложил комитету по стандартизации.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 6 [только новые]





ссылка на сообщение  Отправлено: 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: уже заметил в примере некоторые погрешности и исправил их.

Спасибо: 0 
ПрофильЦитата Ответить



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


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


 цитата:
Complexity: Exactly last - first increments and assignments



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


 цитата:
Complexity: Exactly last - first assignments and increments.



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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 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.

Спасибо: 0 
ПрофильЦитата Ответить



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


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

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

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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 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.

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 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, реализованными Александром Степановым, которые хоть и не вошли в стандарт С++, будет познавательным и полезным.











Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 2
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет