2.5. Введение в ассоциативные контейнеры

Кроме массивов и списков, использующихся для реализации последовательных контейнеров (массивов, векторов, двусторонних очередей и списков), которые обсуждались до сих пор, сбалансированные деревья представляют собой другую классическую структуру данных, предназначенную для их эффективного хранения и извлечения. Сбалансированные деревья составляют основу для другой группы контейнеров, определенной в STL, так называемых {сортированных) ассоциативных контейнеров. Как и ранее, мы в основном сосредоточимся на том, как исполюоватъ эти контейнеры, а не на том, как они реализованы. Всего существует четыре типа этих контейнеров: множества (sets), множества с дубликатами (multisets), словари (maps), словари с дубликатами (multimaps). Перед тем как обсудить их использование, посмотрим, чем они различаются.

Множества

Каждый элемент множества является собственным ключом, и эти ключи уникальны. Поэтому два различных элемента множества не могут совпадать. Например, множество может состоять из следующих элементов:

123 124 800 950

Множества с дубликатами

Множество с дубликатами отличается от просто множества только тем, что способно содержать несколько совпадающих элементов. Например, допустимо существование множества с дубликатами, в котором присутствуют следующие четыре элемента:

123 123 800 950

Словари

Каждый элемент словаря имеет несколько членов, один из которых является ключом. В словаре не может быть двух одинаковых ключей. Приведем пример словаря из четырех элементов, у каждого из которых присутствует целочисленный ключ и буквенные сопутствующие данные:

123 John

124 Mary

800 Alexander 950 Jim

Словари с дубликатами

Словарь с дубликатами отличается от просто словаря тем, что в нем разрешены повторяющиеся ключи. Вот, к примеру, словарь с дубликатами, состоящий из четырех элементов (с целочисленными ключами):

123 John 123 Магу 800 Alexander 950 Jim

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

Заголовки и переносимость

В изначальной версии HP STL было четыре заголовка, связанных с рассматриваемой темой: set.h, multiset.h, map.h и multimap.h. В проекте стандарта С++ остались только два: set и тар. Они используются также для ассоциативных контейнеров с дубликатами.

2.6. Множества и множества с дубликатами

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

Множества

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

set.срр: Два идентичных множества, созданных разными способами,

♦include <iostream> #include <set> using namespace std;

int mainO

{ set<int, less<int> > S, T;

S.insert(10); S.insert (20); S.insert(30); S.insert(10);

T.insert(20); T.insert(30); T.insert(10);

if (S == T) cout Equal sets, containing:\n ;

for (set<int, less<int> >::iterator i = T.beginO; i != T.endO; i++) cout *i ; cout endl; return 0;

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

Equal sets, containing: 10 20 30

И это показывает, что порядок 20, 30, 10, в котором были добавлены элементы Т, несущественен; равным образом множество 5 не изменяет добавление элемента 10 во второй раз. Напомним, что ключи уникальны во множествах, но могут повторяться во множествах с дубликатами.

Обратите внимание на запись, с помощью которой определены 5 и Г:

set<int, less<int> > S, Т;

Предикат

less<int>

требуется для определения значения выражения k < k, где k и являются ключами. Это выглядит странным в текущем примере, когда ключи -целые числа, но стоит напомнить, что множества могут содержать ключи, тип которых определен пользователем. Пробел между двумя закрывающими угловыми скобками в

less<int> >

необходим, чтобы компилятор не обнаружил в этом фрагменте оператор .

Хотя множества и не являются последовательностями, мы можем применять к ним итераторы и функции begin и end, как видно из этой программы. Данные итераторы являются двунаправленными (см. раздел 1.9): для итератора i типа set<int, less<int> >::iterator выражения ++/, -i и i- являются допустимыми, ai + Nni - N - нет.

Множества с дубликатами

Следующая программа демонстрирует, что во множествах с дубликатами могут встречаться одинаковые ключи. Для разнообразия в ней вывод осуществляется с помощью функции сору, как показано ранее в разделе 1.9:

multiset.срр: Два множества с дубликатами, ♦include <iostream> ♦include <set> using namespace std;