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

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



ссылка на сообщение  Отправлено: 29.09.13 00:50. Заголовок: iterator_pair - предложение по включению в стандарт C++ нового адаптера итераторов.


Идея этого предложения по включению в стандарт C++ нового адаптера итераторов под названием iterator_pair пришла мне в голову, когда я втсретил на одном из форумов для начинающих программистов описание следующего задания.

Даны два массива A и B одинакового размера. Нужно сформировать новый массив C с таким же размером, каждый элемент которого равен максимальному из элементов массивов A и B с тем же индексом.

Очевидно, что от начинающего программиста требовалось продемонстрировать умение пользоваться циклами.

Тем не менее это задание легко решается с использованием стандартного алгоритма std::transform.

Вот код такого решения.

 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>

int main()
{
const size_t N = 20;
int a[N], b[N], c[N];

std::srand( ( unsigned int )std::time( 0 ) );

std::for_each( std::begin( a ), std::end( a ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : a ) std::cout << x << ' ';
std::cout << std::endl;

std::for_each( std::begin( b ), std::end( b ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : b ) std::cout << x << ' ';
std::cout << std::endl;

std::transform( std::begin( a ), std::end( a ),
std::begin( b ), std::begin( c ),
std::max<int> );

for ( int x : c ) std::cout << x << ' ';
std::cout << std::endl;
}


Ничего особенного в этом коде нет за исключением разве лишь того, что вместо стандартного функционального объекта используется функция.

Но здесь у меня возник вопрос: а что если нужно максимальные элементы двух массивов A и B переписать в один массив, а минимальные в другой? Или же в первом исходном массиве расположить минимальные элементы двух массивов, а во втором исходном массиве - максимальные элементы двух массивов?

Что тогда делать? Неужели придется перебирать элементы этих массивов два раза? Естественно, это не эффективно. Да и в случае, когда надо изменить массивы "на месте", то есть как это описано во второй задаче выше, это просто невозможно,

Я могу предполагать, что достичь поставленной цели можно, используя какой-нибудь другой алгоритмы, возможно, std::inner_product. Я сам не пробовал это делать, но, думаю, это вполне осуществимо. Проблема заключается в том, что подобное решение будет выглядеть очень вычурно и трудно-читаемо.

И мне пришла, как мне представляется, замечательная идея: в вышеприведенном коде использовать пару выходных итераторов! Фактически, вызов алгоритма std::transform не изменится за исключением того, что выходным итератором будет, как я уже назвал его,
iterator_pare.

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

 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>

int main()
{
const size_t N = 20;
int a[N], b[N], c[N], d[N];

std::srand( ( unsigned int )std::time( 0 ) );

std::for_each( std::begin( a ), std::end( a ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : a ) std::cout << x << ' ';
std::cout << std::endl;

std::for_each( std::begin( b ), std::end( b ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : b ) std::cout << x << ' ';
std::cout << std::endl;

std::transform( std::begin( a ), std::end( a ),
std::begin( b ), std::make_iterator_pair( std::begin( c ), std::begin( d ) ),
std::minmax<int> );

for ( int x : c ) std::cout << x << ' ';
std::cout << std::endl;

for ( int x : d ) std::cout << x << ' ';
std::cout << std::endl;
}



Что изменилось по сравнению с первым примером кода?
Аргумент std::begin( c ) заменился на аргумент std::make_iterator_pair( std::begin( c ), std::begin( d ) ), а функция std::max<int> на std::minmax<int>.

Более того с помощью этого итератора iterator_pair можно выполнить и вторую задачу, то есть в первый исходный массив поместить минимальные элементы двух массивов, а во второй исходный массив поместить максимальные элементы двух массивов.

 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstdlib>
#include <ctime>

int main()
{
const size_t N = 20;
int a[N], b[N];

std::srand( ( unsigned int )std::time( 0 ) );

std::for_each( std::begin( a ), std::end( a ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : a ) std::cout << x << ' ';
std::cout << std::endl;

std::for_each( std::begin( b ), std::end( b ),
[] ( int &x ) { x = std::rand() % ( N / 2 ); } );

for ( int x : b ) std::cout << x << ' ';
std::cout << std::endl;

std::transform( std::begin( a ), std::end( a ),
std::begin( b ), std::make_iterator_pair( std::begin( a ), std::begin( b ) ),
std::minmax<int> );

for ( int x : a ) std::cout << x << ' ';
std::cout << std::endl;

for ( int x : b ) std::cout << x << ' ';
std::cout << std::endl;
}


Когда я это сделал, написав начальную версию этого итератора, то получил сдедующий вывод на консоль

8 0 4 6 8 3 6 7 6 5 2 2 3 1 3 5 9 2 0 8
7 9 1 3 8 4 8 0 8 0 3 4 0 8 8 9 2 8 1 2

7 0 1 3 8 3 6 0 6 0 2 2 0 1 3 5 2 2 0 2
8 9 4 6 8 4 8 7 8 5 3 4 3 8 8 9 9 8 1 8
Для продолжения нажмите любую клавишу . . .

Как видите, код получился достаточно изящным и понятным

Когда получается такое простое и в то же время изящное решение, то это означает, что шаг сделан в правильном направлении.

Осталось подготовить текст соответствующего предложения по включению адаптера итераторов iterator_pair в стандарт языка C++.


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





ссылка на сообщение  Отправлено: 29.09.13 16:29. Заголовок: Попутно при тестиров..


Попутно при тестировании итератора iterator_pair я обнаружил серьезный дефект стандарта C++. Понять этот дефект можно на простом примере. пусть заданы два выходных итератора

 
std::ostream_iterator<int> it1( std::cout, "\n" );
std::ostream_iterator<std::string> it2( std::cout, "\n" );


Они могут быть использованы со следующими типами объектов

 
it1 = 123;
it2 = "abc";


Но их нельзя использовать с теми типами объектов, для которых они не предназначены. То есть нельзя написать, например,

 
it1 = "abc";
it2 = 123;


Компилятор выдаст сообщение об ошибке, что ни первый, ни второй итератор не имеют соответствующих перегруженных операторов присваивания для типов объектов, стоящих в правой части выражения.

Что это означает?

Это означает, что каждый выходной итератор может работать лишь с объектами определенного типа. Тип объекта, с которым может иметь дело выходной итератор, является неотъемлемой и важной характеристикой итератора. И хотя в примере с итераторами, показанном выше, оба итератора являются специализацией одного и того же шаблонного класса, тип значения, с которым они могут иметь дело, у каждого итератора свой.

Другой пример.

Пусть есть некоторая шаблонная функция, которая имеет шаблонный параметр в виде выходного итератора.

 
template <class OutputIterator>
void f( OutputIterator it )
{
// some code
}


И допустим в теле функции мы хотим объявить переменную, которая будет иметь тип, соответствующий тому типу, с которым может иметь дело выходной итератор. Как объявить такую переменную? Как узнать ее тип?

Увы, выходные итераторы в стандарте C++ определяются таким образом, что их характеристика
typename std::iterator_traits<OutputIterator>::value_type задается как void! Это означает, что нет никакой возможности выяснить, с каким типом объектов может работать итератор.

С другой стороны, если мы возьмем какой-нибудь выходной итератор, описанный в стандарте C++, то мы увидим, что на самом деле выходные итераторы неявно определяют value_type при своей реализации, только скрывают это от внешнего мира.

Например, вот как определяется в стандарте C++ выходной итератор std::ostream_iterator:

 
template <class T, class charT = char, class traits = char_traits<charT> >
class ostream_iterator:
public iterator<output_iterator_tag, void, void, void, void> {
// пропущены не имеющие для данного вопроса объявления
ostream_iterator<T,charT,traits>& operator=(const T& value);



Из этого объявления итератора видно, что тип значения, с которым имеет дело итератор, это шаблонный параметр T. Однако для внешнего мира итератор объявляет, что его тип значения (value_type) - это void!

 
class ostream_iterator:
public iterator<output_iterator_tag, void, void, void, void> {


Значит для внешнего мира нет никакой возможности определить, с каким реальным типом объектов имеет дело итератор.

Аналогичная ситуация и с итератором std::back_insert_iterator:

 
template <class Container>
class back_insert_iterator :
public iterator<output_iterator_tag,void,void,void,void> {
// ...
back_insert_iterator<Container>&
operator=(const typename Container::value_type& value);


Этот итератор неявно объявляет тип значения как typename Container::value_type, тем не менее для внешнего мира его тип значения равен void:

 
class back_insert_iterator :
public iterator<output_iterator_tag,void,void,void,void> {


Как это отразилось на новом итераторе iterator_pair, предложенным мною?

Рассмотрим следующий пример использования итератора iterator_pair

 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>

int main()
{
std::map<int, std::string> m;

std::string s = "Hello new iterator \"std::iterator_pair\"!";
std::istringstream is( s );

int i = 0;
std::transform( std::istream_iterator<std::string>( is ),
std::istream_iterator<std::string>(),
std::inserter( m, m.begin() ),
[&i]( const std::string &s ) { return ( std::make_pair( i++, s ) ); } );

std::vector<int> v1( m.size() );
std::vector<std::string> v2( m.size() );


std::copy( m.begin(), m.end(),
usr::make_iterator_pair( v1.begin(), v2.begin() ) );

for ( int x : v1 ) std::cout << x << ' ';
std::cout << std::endl;

for ( const std::string &s : v2 ) std::cout << s << ' ';
std::cout << std::endl;
}


Этот код успешно компилируется и работает. Итератор iterator_pair имеет доступ к value_type итераторов v1.begin() и v2.begin(), так как эти итераторы не являются только выходными, а потому предоставляют внешнему миру конкретный тип объектов, с которыми они имеют дело. В данном случае. это типы int и std::string.

Но если изменить код следующим образом

 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>

int main()
{
std::map<int, std::string> m;

std::string s = "Hello new iterator \"std::iterator_pair\"!";
std::istringstream is( s );

int i = 0;
std::transform( std::istream_iterator<std::string>( is ),
std::istream_iterator<std::string>(),
std::inserter( m, m.begin() ),
[&i]( const std::string &s ) { return ( std::make_pair( i++, s ) ); } );

std::vector<int> v1;
std::vector<std::string> v2;


v1.reserve( m.size() );
v2.reserve( m.size() );

std::copy( m.begin(), m.end(),
usr::make_iterator_pair( std::back_inserter( v1 ), std::back_inserter( v2 ) ) );

for ( int x : v1 ) std::cout << x << ' ';
std::cout << std::endl;

for ( const std::string &s : v2 ) std::cout << s << ' ';
std::cout << std::endl;
}


то код не будет компилироваться, так как выходной итератор, возвращаемый функцией std::back_inserter, не сообщает реальный тип value_type, а вместо него предоставляет тип void.

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

Это серьезный дефект стандарта C++. Каждый выходной итератор имеет конкретное значения для характеристики value_type, с которой он может иметь дело, и эту информацию он должен предоставлять внешнему миру.

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



ссылка на сообщение  Отправлено: 30.09.13 00:13. Заголовок: Необходимо сделать о..


Необходимо сделать одно замечание относительно примеров кода в предыдущих сообщениях. Сейчас, то есть с появлением нового стандарта C++, и, соответственно, с включением в стандарт специального типа std::initializer_list, нельзя в алгоритмах просто указать имя функции std::max<int> или std::minmax<int>. Компилятор сообщит об ошибке, так как возникает неоднозначность: либо задается функция, имеющая два параметра, производных от шаблонного параметра T, либо функция, которая имеет в качестве параметра std::initializer_list<T>.

Чтобы обойти эту проблему, можно, например, объявить соответствующий указатель на функцию , и его использовать в алгоритме.

 
const int & ( *fp )( const int &, const int & ) = std::max<int>;


Другой простой способ избежать неоднозначности вызова функции - это явно указать ее вызов через лямбда-выражение:

 
std::transform( std::begin( a ), std::end( a ),
std::begin( b ), std::begin( c ),
[]( int x, int y ) { return ( std::max<int>( x, y ) ); } );


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



ссылка на сообщение  Отправлено: 24.04.15 21:38. Заголовок: Все, что было сказан..


Все, что было сказано в этой теме, я описал в своей статье iterator_pair - A Simple and Useful Iterator Adapter., которая недавно была опубликована в журнале ACCU Overload N126 (April, 2015).

Вы можете обратиться к статье, представленной в pdf формате по следующему адресу
либо через сайт isocpp.org по следующему адресу

С полным текстом примеров программ, используемых в статье, вы можете ознакомиться на этом форуме в следующем разделе

Надеюсь, что статья будет для вас интересной. В ней также указывается на серьезные дефекты стандартных алгоритмов std::partial_sum и std::adjacent_difference.

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



ссылка на сообщение  Отправлено: 01.04.16 16:39. Заголовок: :sm36: ..




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

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