iterator i, j;

int X = 30;

P = S.equal range(x);

i = P.first; j = P.second;

cout *i *j endl; Вывод: 30 40 return 0;

4.3. Объединение и пересечение множеств

в этом разделе мы рассмотрим известные математические операции нахождения пересечения и объединения двух множеств, которые проиллюстрированы на рисунке 4.1.

10 20 30

20 30 40 50

ПересечениеS*Т 20 30

Объединение S + Т 10 20 30 40 50

Рисунок 4.1. Пересечение и объединение двух множеств

Для обозначения операций пересечения и объединения мы будем использовать операторы * и +, хотя в математике обычно используются обозначения Пии. Для двух множеств S и Т пересечение S * Т определяется как множество, состоящее из элементов, входящих одновременно в оба множества 5 и Г, а объединение S + Т - как множество, содержащее все элементы, входящие либо в S, либо в Г, либо в оба этих множества. Следующая программа показывает, как можно определить операторы * и + для множеств:

intuniol.срр: Пересечение и объединение множеств.

iinclude <iostream>

iinclude <set>

iinclude <algorithm>

using namespace std;

typedef set<int, less<int> > settype;

settype operator*(const settype &S, const settype &T) { settype I; Пересечение.

set intersection( S.beginO , S.endO , T.begin0 , T.endO ,

inserter(I, I.begin()));

return I;

settype operator+(const settype &S, const settype &T) { settype U; Объединение set union( S.beginO, S.endO,

T.beginO , T.endO ,

inserter(U, U.begin()));

return U;

void out(const char *s, const settype &S) { cout s;

copy (S .begin 0 , S.endO,

ostream iterator<int>(cout, )) ;

cout endl;

int main()

{ int aS[3] = {10, 20, 30}, аТ[4] = {20, 30, 40, 50}; settype S(aS, aS + 3) , T(аТ, аТ + 4); outCS = , S) ;

outCT = , T) ; outCS * T = , S * T) ; outCS + T = , S + T) ; return 0;

В соответствии с примером на рисунке 4.1 программа выводит результаты:

S = 10 20 30

Т = 20 30 40 50

S * Т = 20 30

S + Т = 10 20 30 40 50

Определение операторов * и + с помощью функции insert вместо алгоритмов set intersection и setjunion является полезным упражнением. Такие варианты этих операторов приведены ниже; если их использовать в рассмотренной выше программе, результат ее работы не изменится:

Две функции, которые мы могли бы использовать, если бы не существовало алгоритмов set union и set intersection:

settype operator*(const settype &S, const settype &T) { settype I; Пересечение settype::iterator

firsts = S.beginO, lasts = S.endO,

firstT = T.beginO, lastT = T.endO,

i = I.begin(); while (firsts != lasts && firstT != lastT) { if (*firstS < *firstT) ++firstS; else

if (*firstT < *firstS) ++firstT; else

{ i = I.insert(i, *firstS++); ++firstT;

return I;

settype operator+(const settype &S, const settype &T) { settype U; Объединение settype::iterator

firsts = S.beginO, lasts = S.endO, firstT = T.beginO, lastT = T.endO, i = U.begin0 ; while (firsts != lasts && firstT != lastT) i = U.insert(i,

(♦firsts < *firstT ? *firstS++ : *firstT++)); while (firsts != lastS) i = U.insert(i, *firstS++); while (firstT != lastT) i = U.insert(i, *firstT++); return U;

Безусловно, предпочтительнее использовать оригинальные, более простые версии этих функций.

Для нахождения пересечения и объединения двух множеств нет необходимости, разумеется, применять операторы * и +, что показывает следующая программа, эквивалентная рассмотренной выше; данная версия более эффективна, так как не требует копирования возвращаемых функциями множеств:

intunio2.срр: Пересечение и объединение множеств.

iinclude <iostream>

iinclude <set>

iinclude <algorithm>

using namespace std;

typedef set<int, less<int> > settype;

void out(const char *s, const settype &S) { cout s;

copy (S.beginO , S.endO,

ostream iterator<int>(cout, ));

cout endl;