C++ за 21 день седьмое издание

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


Ассоциативные контейнеры (associative container), хранящие данные в отсортирован­ ном виде, сродни словарю. В результате вставка иногда осущ ествляется медленнее, но когда дело доходит до поиска, преимущества оказываются существенными. Библиотека STL предоставляет следующие ассоциативные контейнеры.

0. 
   s t d : : s e t . Хранит уникальные значения отсортированными по вставке в контейнере с
   

логарифмической сложностью1(logarithmic complexity).

0. 
   s t d : : u n o r d e r e d _ s e t . Хранит уникальные значения отсортированными по вставке в контейнере с близкой к постоянной сложностью (near constant complexity). Доступен с версии C++11.
   
1. 
   s t d : :map. Хранит пары “клю ч-значение” отсортированными по их индивидуальным ключам в контейнере с логарифмической сложностью.
   
2. 
   s t d : : u n o rd e re d _ m a p . Хранит пары “клю ч-значение” отсортированными по их ин­ дивидуальным ключам в контейнере с близкой к постоянной сложностью. Доступен с версии C++11.
   
3. 
   s t d : :m u l t i s e t . Сродни контейнеру s e t . Дополнительно обеспечивает возможность хранить по несколько элементов с одинаковыми значениями; т.е. значение не обязатель­ но должно быть уникальным.
   

0. 
   s t d : : u n o r d e r e d _ m u l tis e t . Сродни контейнеру u n o r d e r e d _ s e t . Дополнительно обеспечивает возможность хранить по несколько элементов с одинаковыми значения­ ми, т.е. значение не обязательно должно быть уникальным.
   
1. 
   s t d : :m u ltim a p . Сродни контейнеру тар . Дополнительно обеспечивает возможность хранить пары “ключ-значение” с не уникальными ключами.
   
2. 
   s t d : :u n o r d e r e d _ m u ltim a p . Сродни контейнеру u n o rd e re d _ m a p . Дополнительно обеспечивает возможность хранить пары “клю ч-значение” с не уникальными ключа­ ми. Доступен с версии С++11.
   

Критерии сортировки контейнеров STL могут быть настроены программно при помо­ щи функций предиката.

СОВЕТ

Некоторые реализации библиотеки STL предоставляют также такие ассоциатив­ ные контейнеры, как hash_set, hash_multiset, hash_map и hash_mul-timap. Они подобны контейнерам unordered_*, которые поддерживаются по стандарту. В некоторых сценариях варианты hash_* и unordered_* могут оказаться лучше при поиске элемента, поскольку они предоставляют операции с постоянным временем выполнения (независимые от количества элементов

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

0. 
   ЗАНЯТИЕ 15. Введение в стандартную библиотеку шаблонов
   

0. 
   контейнере). Как правило, эти контейнеры предоставляют также открытые ме­ тоды, идентичные таковым в их стандартных аналогах, а следовательно, столь же удобные.
   

Использование стандартных вариантов приводит к созданию кода, который проще переносить на другие платформы и компилировать, а следовательно, они предпочтительней. Возможно также, что логарифмическое сокращение произ­ водительности стандартных контейнеров может не затронуть значительно ваше приложение.