<< Пред. стр. 112 (из 121) След. >>
Список литературы по разделу
OutputIterator
set_difference( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_difference() строит отсортированную последовательность из элементов, имеющихся в первой последовательности [first1,last1), но отсутствующих во второй – [first2,last2). Например, разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_intersection()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_intersection( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_intersection() строит отсортированную последовательность из элементов, встречающихся в обеих последовательностях – [first1,last1) и [first2,last2). Например, пересечение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,2}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_symmetric_difference()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_symmetric_difference() строит отсортированную последовательность из элементов, которые встречаются только в первой последовательности [first1,last1) или только во второй – [first2,last2). Например, симметрическая разность последовательностей {0,1,2,3} и {0,2,4,6} равна {1,3,4,6}. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
Алгоритм set_union()
template< class InputIterator1, class InputIterator2,
class OutputIterator >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result );
template< class InputIterator1, class InputIterator2,
class OutputIterator, class Compare >
OutputIterator
set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp );
set_union() строит отсортированную последовательность из элементов, которые встречаются либо в первой последовательности [first1,last1), либо во второй – [first2,last2), либо в обеих. Например, объединение последовательностей {0,1,2,3} и {0,2,4,6} равно {0,1,2,3,4,6}. Если элемент присутствует в обеих последовательностях, то копируется экземпляр из первой. Возвращаемый итератор указывает на элемент за последним помещенным в выходной контейнер result. В первом варианте предполагается, что обе последовательности были отсортированы с помощью оператора “меньше”, определенного для типа элементов контейнера; во втором для упорядочения используется указанная программистом операция comp.
#include
#include
#include
#include
/* печатается:
элементы множества #1:
Иа-Иа Пух Пятачок Тигра
элементы множества #2:
Бука Пух Слонопотам
элементы set_union():
Бука Иа-Иа Пух Пятачок Слонопотам Тигра
элементы set_intersection():
Пух
элементы set_difference():
Иа-Иа Пятачок Тигра
элементы_symmetric_difference():
Бука Иа-Иа Пятачок Слонопотам Тигра
*/
int main()
{
string str1[] = { "Пух", "Пятачок", "Тигра", "Иа-Иа" };
string str2[] = { "Пух", "Слонопотам", "Бука" };
ostream_iterator< string > ofile( cout, " " );
set,allocator> set1( str1, str1+4 );
set,allocator> set2( str2, str2+3 );
cout << "элементы множества #1:\n\t";
copy( set1.begin(), set1.end(), ofile ); cout << "\n\n";
cout << "элементы множества #2:\n\t";
copy( set2.begin(), set2.end(), ofile ); cout << "\n\n";
set,allocator> res;
set_union( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_union():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_intersection( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_intersection():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_difference():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
res.clear();
set_symmetric_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));
cout << "элементы set_symmetric_difference():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";
}
Алгоритм sort()
template< class RandomAccessIterator >
void
sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
sort() переупорядочивает элементы в диапазоне [first,last) по возрастанию, используя оператор “меньше”, определенный для типа элементов контейнера. Во втором варианте порядок устанавливается операцией сравнения comp. (Для сохранения относительного порядка равных элементов пользуйтесь алгоритмом stable_sort().) Мы не приводим пример, специально иллюстрирующий применение алгоритма sort(), поскольку его можно найти во многих других программах, в частности в binary_search(), equal_range() и inplace_merge().
Алгоритм stable_partition()
template< class BidirectionalIterator, class Predicate >
BidirectionalIterator
stable_partition( BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred );
stable_partition() ведет себя так же, как partition(), но гарантированно сохраняет относительный порядок элементов контейнера. Вот та же программа, что и для алгоритма partition(), но с использованием stable_partition().
#include
#include
#include
/* печатается:
исходная последовательность:
29 23 20 22 17 15 26 51 19 12 35 40
устойчивое разбиение по четным элементам:
20 22 26 12 40 29 23 17 15 51 19
устойчивое разбиение по элементам, меньшим 25:
23 20 22 17 15 19 12 29 26 51 35 40
*/
class even_elem {
public:
bool operator()( int elem ) {
return elem%2 ? false : true;
}
};
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_partition( &ia[0], &ia[12], even_elem() );
cout << "устойчивое разбиение по четным элементам:\n";
copy( ia, ia+11, ofile ); cout << '\n';
stable_partition( vec.begin(), vec.end(),
bind2nd(less(),25) );
cout << "устойчивое разбиение по элементам, меньшим 25:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм stable_sort()
template< class RandomAccessIterator >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last );
template< class RandomAccessIterator, class Compare >
void
stable_sort( RandomAccessIterator first,
RandomAccessIterator last, Compare comp );
stable_sort() ведет себя так же, как sort(), но гарантированно сохраняет относительный порядок равных элементов контейнера. Второй вариант упорядочивает элементы на основе заданной программистом операции сравнения comp.
#include
#include
#include
/* печатается:
исходная последовательность:
29 23 20 22 12 17 15 26 51 19 12 23 35 40
устойчивая сортировка - по умолчанию в порядке возрастания:
12 12 15 17 19 20 22 23 23 26 29 35 40 51
устойчивая сортировка: в порядке убывания:
51 40 35 29 26 23 23 22 20 19 17 15 12 12
*/
int main()
{
int ia[] = { 29,23,20,22,12,17,15,26,51,19,12,23,35,40 };
vector< int, allocator > vec( ia, ia+14 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
stable_sort( &ia[0], &ia[14] );
cout << "устойчивая сортировка - по умолчанию "
<< "в порядке возрастания:\n";
copy( ia, ia+14, ofile ); cout << '\n';
stable_sort( vec.begin(), vec.end(), greater() );
cout << "устойчивая сортировка: в порядке убывания:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap()
template< class Type >
void
swap ( Type &ob1, Type &ob2 );
swap() обменивает значения объектов ob1 и ob2.
#include
#include
#include
/* печатается:
исходная последовательность:
3 4 5 0 1 2
после применения swap() в процедуре пузырьковой сортировки:
0 1 2 3 4 5
*/
int main()
{
int ia[] = { 3, 4, 5, 0, 1, 2 };
vector< int, allocator > vec( ia, ia+6 );
for ( int ix = 0; ix < 6; ++ix )
for ( int iy = ix; iy < 6; ++iy ) {
if ( vec[iy] < vec[ ix ] )
swap( vec[iy], vec[ix] );
}
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( ia, ia+6, ofile ); cout << '\n';
cout << "после применения swap() в процедуре "
<< "пузырьковой сортировки:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
}
Алгоритм swap_ranges()
template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator2
swap_ranges( ForwardIterator1 first1, ForwardIterator1 last,
ForwardIterator2 first2 );
swap_ranges() обменивает элементы из диапазона [first1,last) с элементами другого диапазона, начиная с first2. Эти последовательности могут находиться в одном контейнере или в разных. Поведение программы не определено, если они находятся в одном контейнере и при этом частично перекрываются, а также в случае, когда вторая последовательность короче первой. Алгоритм возвращает итератор, указывающий на элемент за последним переставленным.
#include
#include
#include
/* печатается:
исходная последовательность элементов первого контейнера:
0 1 2 3 4 5 6 7 8 9
исходная последовательность элементов второго контейнера:
5 6 7 8 9
массив после перестановки двух половин:
5 6 7 8 9 0 1 2 3 4
первый контейнер после перестановки двух векторов:
5 6 7 8 9 5 6 7 8 9
второй контейнер после перестановки двух векторов:
0 1 2 3 4
*/
int main()
{
int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int ia2[] = { 5, 6, 7, 8, 9 };
vector< int, allocator > vec( ia, ia+10 );
vector< int, allocator > vec2( ia2, ia2+5 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность элементов первого контейнера:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
cout << "исходная последовательность элементов второго контейнера:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
// перестановка внутри одного контейнера
<< Пред. стр. 112 (из 121) След. >>
Список литературы по разделу