Форум » C/C++ » iterator_pair - предложение по включению в стандарт C++ нового адаптера итераторов. » Ответить
iterator_pair - предложение по включению в стандарт C++ нового адаптера итераторов.
Сыроежка: Идея этого предложения по включению в стандарт C++ нового адаптера итераторов под названием iterator_pair пришла мне в голову, когда я втсретил на одном из форумов для начинающих программистов описание следующего задания. Даны два массива A и B одинакового размера. Нужно сформировать новый массив C с таким же размером, каждый элемент которого равен максимальному из элементов массивов A и B с тем же индексом. Очевидно, что от начинающего программиста требовалось продемонстрировать умение пользоваться циклами. Тем не менее это задание легко решается с использованием стандартного алгоритма std::transform. Вот код такого решения. [pre2] #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; } [/pre2] Ничего особенного в этом коде нет за исключением разве лишь того, что вместо стандартного функционального объекта используется функция. Но здесь у меня возник вопрос: а что если нужно максимальные элементы двух массивов A и B переписать в один массив, а минимальные в другой? Или же в первом исходном массиве расположить минимальные элементы двух массивов, а во втором исходном массиве - максимальные элементы двух массивов? Что тогда делать? Неужели придется перебирать элементы этих массивов два раза? Естественно, это не эффективно. Да и в случае, когда надо изменить массивы "на месте", то есть как это описано во второй задаче выше, это просто невозможно, Я могу предполагать, что достичь поставленной цели можно, используя какой-нибудь другой алгоритмы, возможно, std::inner_product. Я сам не пробовал это делать, но, думаю, это вполне осуществимо. Проблема заключается в том, что подобное решение будет выглядеть очень вычурно и трудно-читаемо. И мне пришла, как мне представляется, замечательная идея: в вышеприведенном коде использовать пару выходных итераторов! Фактически, вызов алгоритма std::transform не изменится за исключением того, что выходным итератором будет, как я уже назвал его, iterator_pare. Вот как будет выглядеть код, если ставится задача переписать минимальные элементы исходных двух массивов в один массив, а максимальные элементы - в другой массив. [pre2] #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; } [/pre2] Что изменилось по сравнению с первым примером кода? Аргумент std::begin( c ) заменился на аргумент std::make_iterator_pair( std::begin( c ), std::begin( d ) ), а функция std::max<int> на std::minmax<int>. Более того с помощью этого итератора iterator_pair можно выполнить и вторую задачу, то есть в первый исходный массив поместить минимальные элементы двух массивов, а во второй исходный массив поместить максимальные элементы двух массивов. [pre2] #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; } [/pre2] Когда я это сделал, написав начальную версию этого итератора, то получил сдедующий вывод на консоль 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++.
Ответов - 4
Сыроежка: Попутно при тестировании итератора iterator_pair я обнаружил серьезный дефект стандарта C++. Понять этот дефект можно на простом примере. пусть заданы два выходных итератора [pre2] std::ostream_iterator<int> it1( std::cout, "\n" ); std::ostream_iterator<std::string> it2( std::cout, "\n" ); [/pre2] Они могут быть использованы со следующими типами объектов [pre2] it1 = 123; it2 = "abc"; [/pre2] Но их нельзя использовать с теми типами объектов, для которых они не предназначены. То есть нельзя написать, например, [pre2] it1 = "abc"; it2 = 123; [/pre2] Компилятор выдаст сообщение об ошибке, что ни первый, ни второй итератор не имеют соответствующих перегруженных операторов присваивания для типов объектов, стоящих в правой части выражения. Что это означает? Это означает, что каждый выходной итератор может работать лишь с объектами определенного типа. Тип объекта, с которым может иметь дело выходной итератор, является неотъемлемой и важной характеристикой итератора. И хотя в примере с итераторами, показанном выше, оба итератора являются специализацией одного и того же шаблонного класса, тип значения, с которым они могут иметь дело, у каждого итератора свой. Другой пример. Пусть есть некоторая шаблонная функция, которая имеет шаблонный параметр в виде выходного итератора. [pre2] template <class OutputIterator> void f( OutputIterator it ) { // some code } [/pre2] И допустим в теле функции мы хотим объявить переменную, которая будет иметь тип, соответствующий тому типу, с которым может иметь дело выходной итератор. Как объявить такую переменную? Как узнать ее тип? Увы, выходные итераторы в стандарте C++ определяются таким образом, что их характеристика typename std::iterator_traits<OutputIterator>::value_type задается как void! Это означает, что нет никакой возможности выяснить, с каким типом объектов может работать итератор. С другой стороны, если мы возьмем какой-нибудь выходной итератор, описанный в стандарте C++, то мы увидим, что на самом деле выходные итераторы неявно определяют value_type при своей реализации, только скрывают это от внешнего мира. Например, вот как определяется в стандарте C++ выходной итератор std::ostream_iterator: [pre2] 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); [/pre2] Из этого объявления итератора видно, что тип значения, с которым имеет дело итератор, это шаблонный параметр T. Однако для внешнего мира итератор объявляет, что его тип значения (value_type) - это void! [pre2] class ostream_iterator: public iterator<output_iterator_tag, void, void, void, void> { [/pre2] Значит для внешнего мира нет никакой возможности определить, с каким реальным типом объектов имеет дело итератор. Аналогичная ситуация и с итератором std::back_insert_iterator: [pre2] 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); [/pre2] Этот итератор неявно объявляет тип значения как typename Container::value_type, тем не менее для внешнего мира его тип значения равен void: [pre2] class back_insert_iterator : public iterator<output_iterator_tag,void,void,void,void> { [/pre2] Как это отразилось на новом итераторе iterator_pair, предложенным мною? Рассмотрим следующий пример использования итератора iterator_pair [pre2] #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; } [/pre2] Этот код успешно компилируется и работает. Итератор iterator_pair имеет доступ к value_type итераторов v1.begin() и v2.begin(), так как эти итераторы не являются только выходными, а потому предоставляют внешнему миру конкретный тип объектов, с которыми они имеют дело. В данном случае. это типы int и std::string. Но если изменить код следующим образом [pre2] #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; } [/pre2] то код не будет компилироваться, так как выходной итератор, возвращаемый функцией std::back_inserter, не сообщает реальный тип value_type, а вместо него предоставляет тип void. В результате этого итератор iterator_pair не может определить реальный тип значения, с которым он должен работать и передать на вход операторам присваивания обернутых им двух итераторов. Это серьезный дефект стандарта C++. Каждый выходной итератор имеет конкретное значения для характеристики value_type, с которой он может иметь дело, и эту информацию он должен предоставлять внешнему миру.
Сыроежка: Необходимо сделать одно замечание относительно примеров кода в предыдущих сообщениях. Сейчас, то есть с появлением нового стандарта C++, и, соответственно, с включением в стандарт специального типа std::initializer_list, нельзя в алгоритмах просто указать имя функции std::max<int> или std::minmax<int>. Компилятор сообщит об ошибке, так как возникает неоднозначность: либо задается функция, имеющая два параметра, производных от шаблонного параметра T, либо функция, которая имеет в качестве параметра std::initializer_list<T>. Чтобы обойти эту проблему, можно, например, объявить соответствующий указатель на функцию , и его использовать в алгоритме. [pre2] const int & ( *fp )( const int &, const int & ) = std::max<int>; [/pre2] Другой простой способ избежать неоднозначности вызова функции - это явно указать ее вызов через лямбда-выражение: [pre2] std::transform( std::begin( a ), std::end( a ), std::begin( b ), std::begin( c ), []( int x, int y ) { return ( std::max<int>( x, y ) ); } ); [/pre2]
Сыроежка: Все, что было сказано в этой теме, я описал в своей статье iterator_pair - A Simple and Useful Iterator Adapter., которая недавно была опубликована в журнале ACCU Overload N126 (April, 2015). Вы можете обратиться к статье, представленной в pdf формате по следующему адресу либо через сайт isocpp.org по следующему адресу С полным текстом примеров программ, используемых в статье, вы можете ознакомиться на этом форуме в следующем разделе Надеюсь, что статья будет для вас интересной. В ней также указывается на серьезные дефекты стандартных алгоритмов std::partial_sum и std::adjacent_difference.
kol:
полная версия страницы