inplace merge(а, а+3, а+7); сору(а, а+7,

ostream iterator<int>(cout, )); cout endl; return 0;

Программа выводит отсортированный полный диапазон:

2 3 4 5 5 8 9

Существует также версия алгоритма inplacejnerge, принимающая в качестве дополнительного аргумента предикат, так что мы можем использовать нашу собственную операцию сравнения, как в программе merge!.

7.3.8. Операции над множествами для сортированных контейнеров

bool includes

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2); bool includes

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2. Compare comp); Outputlterator set union

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result); Outputlterator set union

(Inputlteratorl firstl, Inputlteratorl lastl. InputIterator2 first2, InputIterator2 last2, Outputlterator result. Compare comp); Outputlterator set intersect ion

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result); Outputlterator set intersection

(Inputlteratorl firstl, Inputlteratorl lastl. InputIterator2 first2, InputIterator2 last2, Outputlterator result. Compare comp); Outputlterator set difference

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result); Outputlterator set difference

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result, Compare comp);

Outputlterator set syrnmetric di£ference

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result); Outputlterator setsymmetric difference

(Inputlteratorl firstl, Inputlteratorl lastl, InputIterator2 first2, InputIterator2 last2, Outputlterator result. Compare comp);

Мы использовали алгоритмы setjLntersection и setunion для множеств в разделе 4.3. Однако они работают не только с множествами, но и с сортированными последовательными контейнерами. К сортированным структурам применимы следующие операции над множествами: includes, setjunion, set intersection, set difference и set symmetric difference. Каждый из этих алгоритмов существует в двух версиях: одна использует для сравнения оператор <, а другая - передаваемый в качестве аргумента предикат. Следующая программа демонстрирует эти пять алгоритмов в варианте, основанном на операторе меньше :

setopstr.cpp: Операции над множествами

для сортированных контейнеров.

iinclude <iostream>

iinclude <algorithm>

using namespace std;

void show ( const char *s, const int *begin,

const int *end) { cout << s << ;

copy(begin, end, ostream iterator<int>(cout, ));

cout << endl;

int mainO

{ int a[4] = {1, 5, 7, 8}, b[3] = {2, 5, 8},

sum[7], *pSumEnd,

prod[4], *pProdEnd,

dif[3], *pDifEnd,

symdif[7], *pSymDifEnd; pSumEnd = set union(a, a+4, b, b+3, sum); pProdEnd = set intersection(a, a+4, b, b+3, prod); pDifEnd = set difference(a, a+4, b, b+3, dif); pSymDifEnd = set symmetric difference(a, a+4, b, b+3,

symdif); show( a: , a, a+4);

show( b: , b, b+3);

show( sum: , sum, pSumEnd); show( prod: , prod, pProdEnd);

Обратите внимание на отличие поведения операции объединения множеств (setjunion) от операции объединения сортированных контейнеров (merge). Для последней количество повторений элемента в результате будет равно сумме количеств повторений элемента в каждом из исходных контейнеров. - Прим. переводчика.

7 - 858

showCdif: , dif, pDifEnd) ;

show{ symdif: , symdif, pSymDifEnd);

if (includes(a, a+4, b, b+3))

cout a includes b.\n ; else cout a does not include b.\n ; if (includes(sum, pSumEnd, b, b+3))

cout sum includes b.\n ; else cout sum does not include b.\n ; return 0;

Эта программа выводит следующий текст:

а: 15 7 8

Ь: 2 5 8

sum: 12 5 7 8

prod: 5 8

dif: 1 7

symdif: 12 7

a does not include b.

sum includes b.

Переменная sum используется для объединений множеств а и 6, а переменная prod - для их пересечения. Любой элемент, входящий в а и Ь, также входит и в sum; в противоположность этому в pmd вошли только те элементы, которые входят в оба контейнера. Разность dif множеств а и 6 состоит из всех элементов, которые входят в а, но не в Ь. Наконец симметричная разность symdif состоит из всех элементов, принадлежащих только к одному из множеств а или Ь, но не к обоим сразу.

Говорят, что множество S содержит (include) множество Т, если все элементы Г входят также и в 5. В нашем примере а не содержит Ь, потому что элемент 2 множества b не принадлежит а. Объединение (union) двух множеств всегда содержит каждое из этих множеств, поэтому в нашем примере sum содержит Ь.

Мы можем использовать последовательные контейнеры, такие как массивы а и 6 из нашего примера, для представления множеств с дубликатами и также применять к ним алгоритмы типа setjunion и др. Получающееся объединение будет контейнером, который содержит максимум повторений каждого элемента в любом из двух множеств, пересечение