Новый алгоритм в C++ 2011 std::partition

Форум » C/C++ » Новый алгоритм в C++ 2011 std::partition_copy » Ответить

Новый алгоритм в C++ 2011 std::partition_copy

Сыроежка: На одном форуме для начинающих программистов я встретил такую типичную задачу, которая часто задается студентам: [quote]"Написать программу, которая из случайно заполненного массива создаёт два новых массива: в одном из которых будут находиться только элементы исходного массива с четными значения, а в другом – с нечетными значениями."[/quote] И я задумался, а можно ли эту задачу выполнить на основе стандартных алгоритмов. Как мне казалось в стандартной библиотеке С++ есть только алгоритмы, которые объединяют различным образом две последовательности, как, например, std::merge, или алгоритмы из семейства для работы со множествами: std::set_union, std::set_intersection и другие. Это довльно странно, что нет ни одного алгоритма в стандартной библиотеке C++, который выполнял бы противоположную задачу, то есть разбивал заданнную последовательность на две новые последовательности по какому-то критерию. Поэтому я решил написать такой алгоритм самостоятельно, назвав его split. [pre2] template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate> std::pair<OutputIterator1, OutputIterator2> split( InputIterator first, InputIterator last, OutputIterator1 out1, OutputIterator2 out2, UnaryPredicate unary_predicate ) { for ( ; first != last; ++first ) { if ( unary_predicate( *first ) ) *out1++ = *first; else *out2++ = *first; } return ( std::make_pair( out1, out2 ) ); }[/pre2] Вот пример использования этого нового алгоритма, написанный в среде MS VC 2010 [pre2]#include "stdafx.h" #include <iostream> #include <algorithm> #include <iterator> #include <cstdlib> #include <ctime> template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate> std::pair<OutputIterator1, OutputIterator2> split( InputIterator first, InputIterator last, OutputIterator1 out1, OutputIterator2 out2, UnaryPredicate unary_predicate ) { for ( ; first != last; ++first ) { if ( unary_predicate( *first ) ) *out1++ = *first; else *out2++ = *first; } return ( std::make_pair( out1, out2 ) ); } int _tmain(int argc, _TCHAR* argv[]) { std::srand( std::time( 0 ) ); const int N = 20; int a[N]; std::generate( std::begin( a ), std::end( a ), []{ return ( std::rand() % 51 - 30 ); } ); std::copy( std::begin( a ), std::end( a ), std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; int b[N], c[N]; auto p = split( std::begin( a ), std::end( a ), std::begin( b ), std::begin( c ), []( int x ) { return ( x % 2 ); } ); std::copy( std::begin( b ), p.first, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; std::copy( std::begin( c ), p.second, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; return 0; }[/pre2] Вывод результата работы программы на консоль: [quote]-6 -26 13 16 5 19 -19 17 -21 8 -13 -10 -19 -5 -19 -10 -22 -30 -6 -13 13 5 19 -19 17 -21 -13 -19 -5 -19 -13 -6 -26 16 8 -10 -10 -22 -30 -6 [/quote] Окрыленный успехом и удивленный, почему до сих пор в стандарте C++ нет такого простого и полезного алгоритма, я написал на форум по обсуждению предложений по стандарту сообщение о целесообразности включить в стандарт C++ подобный алгоритм. Каково же было мое удивление, когда в ответ мне сказали, что в стандарте C++ 2011 уже имеется такой алгоритм. Называется он std::partition_copy. И действительно, просмотрев стандарт, я убедился, что такой алгоиртм есть. Но самое интересное, что его реализация MS VS 2010 полностью совпала с той, которую я предложил! Итак, кто еще не знает, то спешу известить, что имеется такой простой и полезный алгоритм, как std::partition_copy, который по своему назначению является дополнением к семейству алгоритмов std::copy, в частномти он близок к алгоритму std::copy_if по своей семантике. Вот тот же самый демонстрационный пример, что и показанный выше, но уже с включением нового алгоритма std::partition_copy [pre2]#include "stdafx.h" #include <iostream> #include <algorithm> #include <iterator> #include <cstdlib> #include <ctime> template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate> std::pair<OutputIterator1, OutputIterator2> split( InputIterator first, InputIterator last, OutputIterator1 out1, OutputIterator2 out2, UnaryPredicate unary_predicate ) { for ( ; first != last; ++first ) { if ( unary_predicate( *first ) ) *out1++ = *first; else *out2++ = *first; } return ( std::make_pair( out1, out2 ) ); } int _tmain(int argc, _TCHAR* argv[]) { std::srand( std::time( 0 ) ); const int N = 20; int a[N]; std::generate( std::begin( a ), std::end( a ), []{ return ( std::rand() % 51 - 30 ); } ); std::copy( std::begin( a ), std::end( a ), std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; int b[N], c[N]; auto p = split( std::begin( a ), std::end( a ), std::begin( b ), std::begin( c ), []( int x ) { return ( x % 2 ); } ); std::copy( std::begin( b ), p.first, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; std::copy( std::begin( c ), p.second, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; p = std::partition_copy( std::begin( a ), std::end( a ), std::begin( b ), std::begin( c ), []( int x ) { return ( x % 2 ); } ); std::copy( std::begin( b ), p.first, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; std::copy( std::begin( c ), p.second, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; return 0; }[/pre2] Как можно убедиться, результат работы обоих алгоритмов одинаков: [quote]10 8 1 -10 -18 9 -6 -26 -2 -7 -16 -7 -24 -22 -29 -9 6 12 -13 -20 1 9 -7 -7 -29 -9 -13 10 8 -10 -18 -6 -26 -2 -16 -24 -22 6 12 -20 1 9 -7 -7 -29 -9 -13 10 8 -10 -18 -6 -26 -2 -16 -24 -22 6 12 -20[/quote] Как говорится, век живи, век учись!

Ответов - 2

Сыроежка: Тем не менее моя первоначальная радость от существования станлартного алгоритма std::partition_copy в новом стандарте C++ была преждевременной. Этот алгоритм обладает ограниченными возможностями. В подтверждение этого рассмотрим простую задачу: разбить исходную последовательность целых чисел на две другие последовательности, одна из которых будет содержать только положительные значения элементов исходной последовательности, а другая - только отрицательные значения элементов исходной последовательности. Оказывается эту простую задачу нельзя решить с помощью стандартного алгоритма std::partition_copy, так как непонятно, как избавиться от элементов исходной последовательности, которые равны нулю. Если кто знает такой трюк, то сообщите. Лично я не знаю, как в общем случае задать условие, чтобы альтернативное ему условие не было бы полным его отрицанием. Поэтому даже для такой простой задачи программисту придется писать собственный алгоритм, что, естественно, нежелательно. Проблеиа легко решается, если этот стандартный алгоритм дополнить его модификаций. Ниже приведена реализация такой модификации алгоритма std::partition_copy [pre2]template <class InputIterator, class OutputIterator1, class OutputIterator2, class UnaryPredicate1, class UnaryPredicate2> std::pair<OutputIterator1, OutputIterator2> partition_copy( InputIterator first, InputIterator last, OutputIterator1 out1, OutputIterator2 out2, UnaryPredicate1 unary_predicate1, UnaryPredicate2 unary_predicate2 ) { for ( ; first != last; ++first ) { if ( unary_predicate1( *first ) ) *out1++ = *first; if ( unary_predicate2( *first ) ) *out2++ = *first; } return ( std::make_pair( out1, out2 ) ); }[/pre2] Обратите внимание, что в теле функции вместо предложения [pre2] else if ( unary_predicate2( *first ) ) *out2++ = *first;[/pre2] используется предложение [pre2] if ( unary_predicate2( *first ) ) *out2++ = *first;[/pre2] Это делает алгоритм более гибким и мощным, так как позволяет один элемент исходной последовательности записать одновременно в две результирующие последовательности. С помощью этой новой модификации алгоритма std::partition_copy описанная в начале этого сообщения задача решается очень просто. Ниже приведен примерный фрагмент кода, демонстрирующий использование этого нового алгоритма [pre2]std::srand( std::time( 0 ) ); const int N = 20; int a[N]; std::generate( std::begin( a ), std::end( a ), []{ return ( std::rand() % 51 - 30 ); } ); std::copy( std::begin( a ), std::end( a ), std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; int b[N], c[N]; auto p = partition_copy( std::begin( a ), std::end( a ), std::begin( b ), std::begin( c ), std::bind2nd( std::greater<int>(), 0 ), std::bind2nd( std::less<int>(), 0 ) ); std::copy( std::begin( b ), p.first, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl; std::copy( std::begin( c ), p.second, std::ostream_iterator<int>( std::cout, " " ) ); std::cout << std::endl;[/pre2] Предложение о включении этого нового алгоритма в стандарт C++ я выложил на форуме по обсуждению будущих изменений стандарта.

Сыроежка: Как я узнал, мое предложение по новой модификации алгоритма std::partition_copy включено в список предложений по изменению стандарта и ему присвоен номер N3795.

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