При вычислении, ассоциативные контейнеры относятся к группе шаблонов классов в стандартной библиотеки на C ++ Язык программирования , которые реализуют заказанные ассоциативные массивы . [1] Будучи шаблонами , они могут использоваться для хранения произвольных элементов, таких как целые числа или пользовательские классы. Следующие Контейнеры определены в текущем пересмотре C ++ стандарт: set
, map
, multiset
, multimap
. Каждый из этих контейнеров отличается только ограничениями, наложенными на их элементы.
Ассоциативные контейнеры похожи на неупорядоченные ассоциативные контейнеры в стандартной библиотеке C ++ , с той лишь разницей, что неупорядоченные ассоциативные контейнеры, как следует из их названия, не упорядочивают свои элементы.
Дизайн
Характеристики
- Уникальность ключа : в
map
иset
каждый ключ должен быть уникальным.multimap
иmultiset
не имеют этого ограничения. - Состав Элемента : в
map
иmultimap
каждый элемент состоит из ключа и отображенное значения. Вset
иmultiset
каждый элемент является ключевым; нет сопоставленных значений. - Порядок элементов: элементы следуют строгому слабому порядку [1]
Ассоциативные контейнеры предназначены для особенно эффективного доступа к своим элементам по их ключу, в отличие от контейнеров последовательности, которые более эффективны в доступе к элементам по их положению. [1] Ассоциативные контейнеры гарантированно выполняют операции вставки, удаления и проверки того, находится ли в нем элемент, за логарифмическое время - O (log n ). По существу, они обычно реализуются с использованием самобалансирующихся двоичных деревьев поиска и поддерживают двунаправленную итерацию. Итераторы и ссылки не становятся недействительными при операциях вставки и стирания, за исключением итераторов и ссылок на стертые элементы. Определяющей характеристикой ассоциативных контейнеров является то, что элементы вставляются в заранее определенном порядке, например, с сортировкой по возрастанию.
Ассоциативные контейнеры можно сгруппировать в два подмножества: карты и наборы. Карта, которую иногда называют словарем, состоит из пары ключ / значение. Ключ используется для упорядочивания последовательности, а значение каким-то образом связано с этим ключом. Например, карта может содержать ключи, представляющие каждое уникальное слово в тексте, и значения, представляющие, сколько раз это слово встречается в тексте. Набор - это просто восходящий контейнер уникальных элементов.
И map, и set позволяют вставить в контейнер только один экземпляр ключа или элемента. Если требуется несколько экземпляров элементов, используйте multimap или multiset.
И карты, и наборы поддерживают двунаправленные итераторы. Дополнительные сведения об итераторах см. В разделе Итераторы.
Хотя официально hash_map и hash_set не являются частью стандарта STL, они обычно используются для улучшения времени поиска. Эти контейнеры хранят свои элементы в виде хеш-таблицы, где каждая запись таблицы содержит двунаправленный связанный список элементов. Чтобы обеспечить максимально быстрое время поиска, убедитесь, что алгоритм хеширования для ваших элементов возвращает равномерно распределенные хеш-значения.
Представление
Асимптотическая сложность операций , которые могут быть применены к ассоциативным контейнерам следующим образом :
Операция | Сложность |
---|---|
Поиск элемента | O (журнал n) |
Вставка нового элемента | O (журнал n) |
Увеличение / уменьшение итератора | O (log n) (амортизируется O (1), если выполняются только приращения или только уменьшения) |
Удаление одного элемента | O (журнал n) |
Обзор функций
Контейнеры определены в заголовках, названных по именам контейнеров, например set
, определены в заголовке
. Все контейнеры удовлетворяют требования контейнерной концепции означает, что они имеют begin()
, end()
, size()
, max_size()
, empty()
и swap()
методу.
set | map | multiset | multimap | Описание | |
---|---|---|---|---|---|
(конструктор) | (конструктор) | (конструктор) | (конструктор) | Конструирует контейнер из множества источников | |
(деструктор) | (деструктор) | (деструктор) | (деструктор) | Разрушает набор и содержащиеся в нем элементы | |
operator= | operator= | operator= | operator= | Присваивает значения контейнеру | |
get_allocator | get_allocator | get_allocator | get_allocator | Возвращает распределитель, используемый для выделения памяти для элементов. | |
Доступ к элементу | N / A | at | N / A | N / A | Доступ к указанному элементу с проверкой границ. |
N / A | operator[] | N / A | N / A | Доступ к указанному элементу без проверки границ. | |
Итераторы | begin | begin | begin | begin | Возвращает итератор в начало контейнера |
end | end | end | end | Возвращает итератор в конец контейнера | |
rbegin | rbegin | rbegin | rbegin | Возвращает обратный итератор в обратное начало контейнера | |
rend | rend | rend | rend | Возвращает обратный итератор на обратный конец контейнера | |
Вместимость | empty | empty | empty | empty | Проверяет, пустой ли контейнер |
size | size | size | size | Возвращает количество элементов в контейнере. | |
max_size | max_size | max_size | max_size | Возвращает максимально возможное количество элементов в контейнере | |
Модификаторы | clear | clear | clear | clear | Очищает содержимое. |
insert | insert | insert | insert | Вставляет элементы. | |
emplace | emplace | emplace | emplace | Создает элементы на месте ( C ++ 11 ) | |
emplace_hint | emplace_hint | emplace_hint | emplace_hint | Создает элементы на месте с помощью подсказки ( C ++ 11 ) | |
erase | erase | erase | erase | Стирает элементы. | |
swap | swap | swap | swap | Меняет местами содержимое с другим контейнером. | |
Уважать | count | count | count | count | Возвращает количество элементов, соответствующих определенному ключу. |
find | find | find | find | Находит элемент с определенным ключом. | |
equal_range | equal_range | equal_range | equal_range | Возвращает диапазон элементов, соответствующих определенному ключу. | |
lower_bound | lower_bound | lower_bound | lower_bound | Возвращает итератор к первому элементу с ключом не меньше заданного значения. | |
upper_bound | upper_bound | upper_bound | upper_bound | Возвращает итератор к первому элементу с ключом больше определенного значения. | |
Наблюдатели | key_comp | key_comp | key_comp | key_comp | Возвращает ключевую функцию сравнения. |
value_comp | value_comp | value_comp | value_comp | Возвращает функцию сравнения значений. В set и multiset эта функция эквивалентна key_comp , поскольку элементы состоят только из ключа. |
Применение
В следующем коде показано, как использовать map
для подсчета вхождений слов. Он использует слово как ключ, а счетчик как значение.
#include #include <строка>#include <карта>int main () { std :: map < std :: string , int > wordcounts ; std :: string s ; while ( std :: cin >> s && s ! = "конец" ) ++ wordcounts [ s ]; while ( std :: cin >> s && s ! = "конец" ) std :: cout << s << '' << wordcounts [ s ] << '\ n' ; }
При выполнении пользователь сначала набирает серию слов, разделенных пробелами, и слово «конец», чтобы обозначить конец ввода; затем пользователь может вводить слова, чтобы узнать, сколько раз каждое слово встречалось в предыдущей серии.
Приведенный выше пример также демонстрирует, что operator [] вставляет новые объекты (используя конструктор по умолчанию) на карту, если ни один из них не связан с ключом. Таким образом, интегральные типы инициализируются нулем, строки инициализируются пустыми строками и т. Д.
Следующий пример иллюстрирует вставку элементов в карту с помощью функции вставки и поиск ключа с помощью итератора карты и функции поиска:
#include #include <карта>#include <утилита> // make_pairint main () { typedef std :: map < char , int > MapType ; MapType my_map ; // вставляем элементы с помощью функции вставки my_map . вставить ( std :: pair < char , int > ( 'a' , 1 )); my_map . вставить ( std :: pair < char , int > ( 'b' , 2 )); my_map . вставить ( std :: pair < char , int > ( 'c' , 3 )); my_map . вставить ( MapType :: value_type ( 'd' , 4 )); // все стандартные контейнеры предоставляют этот typedef my_map . вставить ( std :: make_pair ( 'e' , 5 )); // также можно использовать служебную функцию make_pair my_map . вставить ({ 'f' , 6 }); // использование списка инициализаторов C ++ 11 // ключи карты сортируются автоматически от меньшего к большему. // Итак, my_map.begin () указывает на наименьшее значение ключа, а не на ключ, который был вставлен первым. MapType :: итератор iter = my_map . begin (); // стираем первый элемент, используя функцию стирания my_map . стереть ( итер ); // выводим размер карты std :: cout << "Размер my_map:" << my_map . size () << '\ n' ; std :: cout << "Введите ключ для поиска:" ; char c ; std :: cin >> c ; // find вернет итератор к соответствующему элементу, если он найден // или до конца карты, если ключ не найден iter = my_map . найти ( c ); if ( iter ! = my_map . end () ) std :: cout << "Значение:" << iter -> second << '\ n' ; else std :: cout << "Ключ отсутствует в my_map" << '\ n' ; // очищаем записи на карте my_map . clear (); }
В приведенном выше примере шесть элементов вводятся с помощью функции вставки, а затем первый элемент удаляется. Затем выводится размер карты. Затем пользователю предлагается ввести ключ для поиска. Используя итератор, функция find ищет элемент с заданным ключом. Если он находит ключ, программа печатает значение элемента. Если он не находит его, возвращается итератор до конца карты, и он выводит, что ключ не может быть найден. Наконец, все элементы в дереве стираются.
Итераторы
Карты могут использовать итераторы, чтобы указывать на определенные элементы в контейнере. Итератор может обращаться как к ключу, так и к отображенному значению элемента: [1]
map < Key , T > :: iterator it ; // объявляет итератор карты it -> first ; // значение ключа it -> second ; // отображаемое значение ( * it ); // "значение элемента", которое имеет тип: pair
Ниже приведен пример цикла по карте для отображения всех ключей и значений с использованием итераторов:
#include #include <строка>#include <карта>int main () { std :: map < std :: string , int > data { { "Оценка Боба" , 10 }, { "Оценка Мартиса" , 15 }, { "Оценка Мехметса" , 34 }, { "Оценка Роккиса " , 22 }, { " Rockys score " , 23 } / * перезаписывает 22, поскольку ключи идентичны * / }; // Перебираем карту и распечатываем все пары ключ / значение. for ( const auto & element : data ) { std :: cout << "Кто (key = first):" << element . первый ; std :: cout << "Score (value = second):" << element . второй << '\ n' ; } возврат 0 ; }
Для компиляции приведенного выше примера на компиляторе GCC необходимо использовать специальный стандартный флаг выбора.
g ++ - std = исходный код c ++ 11 . cpp - o src
Это выведет ключи и значения всей карты, отсортированные по ключам.
Рекомендации
- ^ a b c d Проект спецификации ISO / IEC 14882: 2011 (PDF) . п. 797, § 23.4.4.
Смотрите также
- Контейнер (абстрактный тип данных)
- Стандартная библиотека шаблонов # Контейнеры