На одном форуме для начинающих программистов я встретил такую типичную задачу, которая часто задается студентам:
цитата: |
"Написать программу, которая из случайно заполненного массива создаёт два новых массива: в одном из которых будут находиться только элементы исходного массива с четными значения, а в другом – с нечетными значениями." |
|
И я задумался, а можно ли эту задачу выполнить на основе стандартных алгоритмов. Как мне казалось в стандартной библиотеке С++ есть только алгоритмы, которые объединяют различным образом две последовательности, как, например,
std::merge, или алгоритмы из семейства для работы со множествами:
std::set_union,
std::set_intersection и другие.
Это довльно странно, что нет ни одного алгоритма в стандартной библиотеке C++, который выполнял бы противоположную задачу, то есть разбивал заданнную последовательность на две новые последовательности по какому-то критерию.
Поэтому я решил написать такой алгоритм самостоятельно, назвав его
split.
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 ) );
}
Вот пример использования этого нового алгоритма, написанный в среде
MS VC 2010 #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;
}
Вывод результата работы программы на консоль:
цитата: |
-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 |
|
Окрыленный успехом и удивленный, почему до сих пор в стандарте C++ нет такого простого и полезного алгоритма, я написал на форум по обсуждению предложений по стандарту сообщение о целесообразности включить в стандарт C++ подобный алгоритм.
Каково же было мое удивление, когда в ответ мне сказали, что в стандарте C++ 2011 уже имеется такой алгоритм. Называется он
std::partition_copy. И действительно, просмотрев стандарт, я убедился, что такой алгоиртм есть. Но самое интересное, что его реализация
MS VS 2010 полностью совпала с той, которую я предложил!
Итак, кто еще не знает, то спешу известить, что имеется такой простой и полезный алгоритм, как
std::partition_copy, который по своему назначению является дополнением к семейству алгоритмов
std::copy, в частномти он близок к алгоритму
std::copy_if по своей семантике.
Вот тот же самый демонстрационный пример, что и показанный выше, но уже с включением нового алгоритма
std::partition_copy #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;
}
Как можно убедиться, результат работы обоих алгоритмов одинаков:
цитата: |
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 |
|
Как говорится, век живи, век учись!