int main О

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

Т(аТ, аТ + 4), prod, sum; outCS = , S) ; outCT = , T) ;

set intersection(S.begin(), S.endO,

T.beginO, T.endO, inserter (prod, prod, begin ())) ; outCS * T = , prod) ; set union(S.begin(), S.end(),

T.beginO, T.end() .inserter (sum, sum. begin ())) ; out( S + T = , sum); return 0;

Алгоритмы setjntersection и setunion не ограничены в использовании контейнерами типа множеств, а могут быть применены и к другим сортированным структурам, как показано далее в разделе 7.3.8.

4.4. Отличия множеств с дубликатами от просто множеств

Мы уже обсуждали множества и множества с дубликатами в разделе 2.6, и не мешает снова обратиться к тексту программы multiset.cpp, приведенному в том разделе. Напомним, что каждый элемент множества уникален, в то время как множества с дубликатами могут содержать несколько экземпляров одинаковых элементов. Из-за этого одна из функций insert для множеств с дубликатами определена проще, чем для множеств. Как видно из раздела 4.2, для множеств существует функция insert, объявленная как

pair<iterator, bool> insert(const value type& x); set

Вспомним, что эта функция возвращает пару, состоящую из итератора и значения типа bool, которое равно false, когда операция добавления завершается неудачей из-за того, что значение х уже присутствует в множестве. Напротив, добавление элемента в множество с дубликатами всегда проходит успешно, так что нет необходимости возвращать признак типа bool. Поэтому соответствующая функция для множества с дубликатами возвращает просто итератор в соответствии со следующим объявлением:

iterator insert(const value type& x); multiset

Bee остальные функции для множеств с дубликатами объявлены точно так же, как и функции для множеств, если не считать отличием замену имени класса set в объявлении на multiset. Функция find для множеств с дубликатами в случае успеха возвращает итератор, ссылающийся на первый из элементов с искомым значением, как видно из программы:

msfind.срр: Поиск в множестве с дубликатами, iinclude <iostream> iinclude <set>

using namespace std;

typedef multiset<int, less<int> > multisettype; typedef multisettype::iterator Iterator;

void out(Iterator first, Iterator last) { for (Iterator i = first; i != last; ++i) cout *i ; cout endl;

int main()

{ int a[5] = {10, 20, 20, 20, 30}; multisettype M(a, a+5); out(M.begin() , M.endO ) ;

cout Subrange starting at element 20:\n ; out(M.find(20) , M.endO ) ; return 0;

Программа выводит

10 20 20 20 30

Subrange starting at element 20: 20 20 20 30

Из этого видно, что возвращаемый функцией find итератор указывает на первый найденный элемент. Если бы вызов M.find(20) завершился неудачей из-за отсутствия в множестве с дубликатами М элемента со значением 20, этот вызов возвратил бы значение M.endQ.

4.5. Словари

У словарей существуют три конструктора, объявленные следующим образом:

тар(const Compares comp = Compare()); 1

map(const value type* first, const value type* last,

const Compares comp = CompareO); 2

map(const map<Key, T, Compare>& x); 3

Программа ниже показывает, как используется каждый из этих конструкторов:

mapcstr.cpp: Конструкторы словаря iinclude <iostream> iinclude <map> using namespace std;

typedef map<int, double, less<int> > maptype; typedef pair<int, double> Pair;

int mainO

pair<int, double> { Pair(20, 1.5), Pair(800, 0.3) Pair(3, 0.2)

maptype MA; maptype MB(a, a maptype MC(MB);

a[3] =

+ 3)

cout MC[800] return 0;

endl;

1 (начинаем с пустого словаря)

111 (инициализируем массивом)

3 (используем MB для

инициализации)

МС[800] = МВ[800] = 0.3

Инициализация словаря MB записывается проще, чем инициализация массива пар а, который служит для нее основой. С помощью конструктора копирования (помеченного комментарием 3 в начале этого раздела) мы определяем словарь МС как копию словаря MB.

Для словаря очень полезен оператор доступа по индексу []. Мы можем использовать его не только для извлечения данных из словаря, как в предыдущей программе для словаря МС, но и для добавления новых данных.

Например, вместо использования массива а в предыдущей программе мы могли бы добавить данные в MB более простым способом, как в следующей программе:

mapsubs.cpp: Использование индекса для словаря, iinclude <iostream> iinclude <map> using namespace std;

typedef map<int, double, less<int> > maptype;

int mainO { maptype MB; MB[20] = 1.5; MB[800] = 0.3; MB[3] = 0.2; cout MB[800] return 0;

endl; 0.3

Доступ no индексу является отображением ключей (20, 800 и 3) на связанные с ними значения (1.5, 0.3 и 0.2), как показано на рисунке 4.2.