Множества. Использование ассоциативных контейнеров

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

2 3 7 8 9 20 23 25 28 30 33

В ассоциативных контейнерах элементы не выстроены в линейную последовательность.

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

Рассмотрим две основные категории ассоциативных контейнеров в STL: множества и словари.

В множестве (set) хранятся объекты, упорядоченные по некоторому ключу, являющемуся атрибутом самого объекта.

Например, множество может хранить объекты класса Man, упорядоченные в алфавитном порядке по значению ключевого поля name.

Если в множестве хранятся значения одного из встроенных типов,

например, int, то ключом является сам элемент.

Словарь (тар) можно представить себе как своего рода таблицу из двух столбцов, в первом из которых хранятся объекты, содержащие ключи, а во втором — объекты, содержащие значения.

И в множествах, и в словарях все ключи являются уникальными (только одно значение соответствует ключу). Мультимножества (multiset) и мультисловари(multlmap) аналогичны своим родственным контейнерам, но в них одному ключу может соответствовать несколько значений.

Ассоциативные контейнеры имеют много общих методов с последовательными контейнерами. Тем не менее, некоторые методы, а также алгоритмы характерны только для них.

Шаблон множества имеет два параметра: тип ключа и тип функционального объекта, определяющего отношение «меньше»:

template <class Key, class Compare = less<Key> >

class set{ /*... */ };

Таким образом, если объявить некоторое множество set<int> s1 с опущенным вторым параметром шаблона, то по умолчанию для упорядочения членов множества будет использован предикат less<int>.

Точно так же можно опустить второй параметр при объявлении множества set<MyClass>s2, если в классе MyClass определена операция operator<().

Для использования контейнеров типа set необходимо подключить заголовочный файл <set>.

Имеется три способа определить объект типа set:

set<int> setl; // создается пустое множество

int а[5] = { 1, 2, 3, 4, 5 };

set<int> set2(a, а + 5): // инициализация копированием массива

set<int> set3(set2): // инициализация другим множеством

Для вставки элементов в множество можно использовать метод insert (), для удаления — метод erase (). Также к множествам применимы общие для всех контейнеров методы, указанные в табл. 2.

Во всех ассоциативных контейнерах есть метод count (), возвращающий количество объектов с заданным ключом. Так как и в множествах, и в словарях все ключи уникальны, то метод count () возвращает либо 0, если элемент не обнаружен, либо 1.

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

Алгоритм includes выполняет проверку включения одной последовательности в другую.

Результат равен true в том случае, когда каждый элемент последовательности [first2, last2) содержится в последовательности [firstl, lastl).

Алгоритм set_intersection создает отсортированное пересечение множеств, то есть множество, содержащее только те элементы, которые одновременно входят и в первое, и во второе множество.

Алгоритм set_union создает отсортированное объединение множеств, то есть множество, содержащее элементы первого и второго множества без повторяющихся элементов.

В следующей программе показано использование этих алгоритмов:

int main() {

const int N = 5;

string sl[N] = {"Bill", "Jessica", "Ben", "Mary", "Monica"};

string s2[N] = {"Sju", "Monica","John","Bill","Sju"};

typedef set<string> Sets;

Sets A(s1, s1 + N):

Sets B(s2, s2 + N);

print(A); print(B);

Sets prod, sum;

set_intersection(A.begin(), A.end(), B.begin(), B.end(),

inserter(prod, prod.begin());