Примеры использования ассоциативных контейнеров

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

#include "stdafx.h"

#include <iostream>

#include <set>

 

int main()

{

// Тип коллекции

typedef std::set<int> IntSet;

IntSet coll; // Контейнер дпя целых чисел

                   // Вставка элементов со значениями от 1 до 6

/*-значение 1 вставляется дважды    */

coll.insert(3);

coll.insert(1);

coll.insert(5);

coll.insert(4);

coll.insert(1);

coll.insert(6);

coll.insert(2);

/* Вывод содержимого множества

* - перебор всех элементов. */

IntSet::const_iterator pos;

for (pos = coll.begin(); pos!= coll.end(); ++pos) std::cout<<*pos <<' ';

std::cout << std::endl;

}

Как обычно, следующая директива подгружает все необходимые определения типов и операций с множествами: #include <set>

Тип контейнера используется в нескольких местах программы, поэтому для удобства мы определяем для него сокращенное название: typedef std::set<int> IntSet;

Команда определяет тип IntSet как множество элементов типа int. Этот тип использует стандартный критерий сортировки, при котором элементы сортируются оператором < (то есть упорядочиваются по возрастанию). Чтобы отсортировать элементы по убыванию или использовать совершенно иной критерий сортировки, передайте его в качестве второго параметра шаблона.

Все ассоциативные контейнеры поддерживают функцию insert(), которая вставляет новый элемент:

coll.insert(3);

coll.insert(1);

…

Позиция нового элемента определяется автоматически в соответствии с критерием сортировки. Функции последовательных контейнеров push_back() или push_front() не поддерживаются ассоциативными контейнерами. В данном случае эти функции не имеют смысла, поскольку позиция нового элемента определяется автоматически.

Состояние контейнера после вставки элементов в произвольном порядке иллюстрирует рис. 9.5. В результате сортировки элементы объединяются во внутреннюю древовидную структуру контейнера таким образом, что «левый» потомок любого элемента всегда меньше (в отношении используемого критерия сортировки) этого элемента, а «правый» потомок всегда больше. Присутствие дубликатов (элементов с одинаковыми значениями) в множествах не допускается, поэтому значение 1 встречается в контейнере только один раз.

 

 

Рис. 9.5. Множество из шести элементов

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

IntSet::const_iterator pos;

for (pos = coll.begin(); pos!= coll.end(); ++pos) std::cout << *pos <<' ';

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

 

Рис. 9.6. Перебор элементов множества с помощью итератора pos

Результат работы программы выглядит так: 1 2 3 4 5 6

Чтобы вместо обычного множества использовалось мультимножество, достаточно изменить тип контейнера (заголовочный файл остается тем же):

typedef std::multiset<int> IntSet;

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

1 1 2 3 4 5 6