Ассоциативные контейнеры - Associative containers

В вычислениях ассоциативные контейнеры обратитесь к группе шаблонов классов в стандартная библиотека из Язык программирования C ++ это орудие заказано ассоциативные массивы.^[1] Существование шаблоны, их можно использовать для хранения произвольных элементов, таких как целые числа или пользовательские классы. Следующие контейнеры определены в текущей версии стандарта C ++: набор, карта, мультимножество, Multimap. Каждый из этих контейнеров отличается только ограничениями, наложенными на их элементы.

Ассоциативные контейнеры похожи на неупорядоченные ассоциативные контейнеры в Стандартная библиотека C ++, с той лишь разницей, что неупорядоченные ассоциативные контейнеры, как следует из их названия, не порядок их элементы.

Дизайн

Характеристики

Уникальность ключа: в карта и набор каждый ключ должен быть уникальным. Multimap и мультимножество нет этого ограничения.
Элементный состав: в карта и Multimap каждый элемент состоит из ключа и сопоставленного значения. В набор и мультимножество каждый элемент является ключевым; нет сопоставленных значений.
Порядок элементов: элементы следуют за строгий слабый порядок^[1]

Ассоциативные контейнеры предназначены для особенно эффективного доступа к своим элементам по их ключу, в отличие от контейнеров последовательности, которые более эффективны в доступе к элементам по их положению.^[1] Ассоциативные контейнеры гарантированно выполнят операции вставки, удаления и проверки того, находится ли в нем элемент, за логарифмическое время - O (log п). Таким образом, они обычно реализуются с использованием самобалансирующиеся бинарные деревья поиска и поддерживают двунаправленную итерацию. Итераторы и Рекомендации не аннулируются операциями вставки и стирания, за исключением итераторов и ссылок на стертые элементы. Определяющей характеристикой ассоциативных контейнеров является то, что элементы вставляются в заранее определенном порядке, например, в порядке возрастания.

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

Как map, так и set позволяют вставить в контейнер только один экземпляр ключа или элемента. Если требуется несколько экземпляров элементов, используйте multimap или multiset.

И карты, и наборы поддерживают двунаправленные итераторы. Дополнительные сведения об итераторах см. В разделе Итераторы.

Хотя официально hash_map и hash_set не являются частью стандарта STL, они обычно используются для сокращения времени поиска. Эти контейнеры хранят свои элементы в виде хеш-таблицы, где каждая запись таблицы содержит двунаправленный связанный список элементов. Чтобы обеспечить максимально быстрое время поиска, убедитесь, что алгоритм хеширования для ваших элементов возвращает равномерно распределенные хеш-значения.

Спектакль

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

Операция	Сложность
Поиск элемента	O (журнал n)
Вставка нового элемента	O (журнал n)
Увеличение / уменьшение итератора	O (log n) (амортизируется O (1), если выполняется только увеличение или только уменьшение)
Удаление одного элемента	O (журнал n)

Обзор функций

Контейнеры определены в заголовках, названных по именам контейнеров, например набор определено в заголовке <set>. Все контейнеры соответствуют требованиям Контейнер концепция, что означает, что у них есть начинать(), конец(), размер(), max_size (), пустой(), и замена() методы.

	`набор`	`карта`	`мультимножество`	`Multimap`	Описание
	(конструктор)	(конструктор)	(конструктор)	(конструктор)	Конструирует контейнер из множества источников
	(деструктор)	(деструктор)	(деструктор)	(деструктор)	Разрушает набор и содержащиеся в нем элементы
	`оператор =`	`оператор =`	`оператор =`	`оператор =`	Присваивает значения контейнеру
	`get_allocator`	`get_allocator`	`get_allocator`	`get_allocator`	Возвращает распределитель, используемый для выделения памяти для элементов.
Доступ к элементу	Нет данных	`в`	Нет данных	Нет данных	Доступ к указанному элементу с проверкой границ.
Доступ к элементу	Нет данных	`оператор []`	Нет данных	Нет данных	Доступ к указанному элементу без проверки границ.
Итераторы	`начинать`	`начинать`	`начинать`	`начинать`	Возвращает итератор в начало контейнера
	`конец`	`конец`	`конец`	`конец`	Возвращает итератор в конец контейнера
	`rbegin`	`rbegin`	`rbegin`	`rbegin`	Возвращает обратный итератор в обратное начало контейнера
	`раздирать`	`раздирать`	`раздирать`	`раздирать`	Возвращает обратный итератор на обратный конец контейнера
Емкость	`пустой`	`пустой`	`пустой`	`пустой`	Проверяет, пустой ли контейнер
	`размер`	`размер`	`размер`	`размер`	Возвращает количество элементов в контейнере.
	`max_size`	`max_size`	`max_size`	`max_size`	Возвращает максимально возможное количество элементов в контейнере
Модификаторы	`Чисто`	`Чисто`	`Чисто`	`Чисто`	Очищает содержимое.
	`вставлять`	`вставлять`	`вставлять`	`вставлять`	Вставляет элементы.
	`поставить`	`поставить`	`поставить`	`поставить`	Создает элементы на месте (C ++ 11 )
	`emplace_hint`	`emplace_hint`	`emplace_hint`	`emplace_hint`	Создает элементы на месте, используя подсказку (C ++ 11 )
	`стереть`	`стереть`	`стереть`	`стереть`	Стирает элементы.
	`замена`	`замена`	`замена`	`замена`	Меняет местами содержимое с другим контейнером.
Искать	`считать`	`считать`	`считать`	`считать`	Возвращает количество элементов, соответствующих определенному ключу.
	`найти`	`найти`	`найти`	`найти`	Находит элемент с определенным ключом.
	`равный_ диапазон`	`равный_ диапазон`	`равный_ диапазон`	`равный_ диапазон`	Возвращает диапазон элементов, соответствующих определенному ключу.
	`нижняя граница`	`нижняя граница`	`нижняя граница`	`нижняя граница`	Возвращает итератор к первому элементу с ключом не меньше заданного значения.
	`верхняя граница`	`верхняя граница`	`верхняя граница`	`верхняя граница`	Возвращает итератор к первому элементу с ключом больше определенного значения.
Наблюдатели	`key_comp`	`key_comp`	`key_comp`	`key_comp`	Возвращает ключевую функцию сравнения.
Наблюдатели	`value_comp`	`value_comp`	`value_comp`	`value_comp`	Возвращает функцию сравнения значений. В `набор` и `мультимножество` эта функция эквивалентно `key_comp`, поскольку элементы состоят только из ключа.

использование

Следующий код демонстрирует, как использовать карта <строка, интервал> для подсчета вхождений слов. Он использует слово как ключ, а счетчик как значение.

#включают <iostream>#включают <string>#включают <map>int главный(){    стандартное::карта<стандартное::нить, int> Wordcounts;    стандартное::нить s;    пока (стандартное::cin >> s && s != "конец")        ++Wordcounts[s];    пока (стандартное::cin >> s && s != "конец")        стандартное::cout << s << ' ' << Wordcounts[s] << ' n';}

При выполнении пользователь сначала набирает серию слов, разделенных пробелами, и слово «конец», чтобы обозначить конец ввода; затем пользователь может вводить слова, чтобы узнать, сколько раз каждое слово встречалось в предыдущей серии.

Приведенный выше пример также демонстрирует, что оператор [] вставляет новые объекты (используя конструктор по умолчанию) на карту, если ни один из них не связан с ключом. Таким образом, интегральные типы инициализируются нулем, строки инициализируются пустыми строками и т. Д.

Следующий пример иллюстрирует вставку элементов в карту с помощью функции вставки и поиск ключа с помощью итератора карты и функции поиска:

#включают <iostream>#включают <map>#включают <utility> // make_pairint главный(){    typedef стандартное::карта<char, int> Тип карты;    Тип карты my_map;    // вставляем элементы с помощью функции вставки    my_map.вставлять(стандартное::пара<char, int>('а', 1));    my_map.вставлять(стандартное::пара<char, int>('b', 2));    my_map.вставлять(стандартное::пара<char, int>('c', 3));    my_map.вставлять(Тип карты::тип ценности('d', 4)); // все стандартные контейнеры предоставляют это typedef    my_map.вставлять(стандартное::make_pair('е', 5));      // также можно использовать служебную функцию make_pair    my_map.вставлять({'f', 6});                    // использование списка инициализаторов C ++ 11        // ключи карты сортируются автоматически от меньшего к большему.     // Итак, my_map.begin () указывает на наименьшее значение ключа, а не на ключ, который был вставлен первым.    Тип карты::итератор iter = my_map.начинать();    // стираем первый элемент с помощью функции стирания    my_map.стереть(iter);    // выводим размер карты    стандартное::cout << "Размер my_map:" << my_map.размер() << ' n';    стандартное::cout << "Введите ключ для поиска:";    char c;    стандартное::cin >> c;    // find вернет итератор соответствующему элементу, если он найден    // или до конца карты, если ключ не найден    iter = my_map.найти(c);    если (iter != my_map.конец() )         стандартное::cout << "Значение:" << iter->второй << ' n';    еще        стандартное::cout << «Ключ отсутствует в my_map» << ' n';    // очищаем записи на карте    my_map.Чисто();}

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

Итераторы

Карты могут использовать итераторы, чтобы указывать на определенные элементы в контейнере. Итератор может получить доступ как к ключу, так и к отображенному значению элемента:^[1]

карта<Ключ,Т>::итератор Это; // объявляет итератор картыЭто->первый;               // значение ключа Это->второй;              // отображаемое значение(*Это);                   // "значение элемента", которое имеет тип: pair

Ниже приведен пример цикла по карте для отображения всех ключей и значений с использованием итераторов:

#включают <iostream>#включают <string>#включают <map>int главный(){    стандартное::карта <стандартное::нить, int> данные{     { "Бобс счет", 10 },     { "Мартис счет", 15 },     { «Мехметс счет», 34 },     { "Рокис счет", 22 },     { "Рокис счет", 23 } / * перезаписывает 22, поскольку ключи идентичны * /    };        // Перебираем карту и распечатываем все пары ключ / значение.    за (const авто& элемент : данные)    {        стандартное::cout << «Кто (ключ = первый):» << элемент.первый;        стандартное::cout << «Оценка (значение = секунда):» << элемент.второй << ' n';    }    возвращаться 0;}

Для компиляции приведенного выше примера на компиляторе GCC необходимо использовать специальный стандартный флаг выбора.

грамм++ -стандартное=c++11 источник.cpp -о src

Это выведет ключи и значения всей карты, отсортированные по ключам.

Смотрите также

[std-1] а ^б ^c ^d ISO / IEC 14882: 2011 проект спецификации (PDF). п. 797, § 23.4.4.

[1]