На этом шаге мы приведем общие сведения об ассоциативных контйнерах и дадим их классификацию.
Ассоциативные контейнеры автоматически сортируют свои элементы по некоторому критерию. Критерий представляется в виде функции, которая сравнивает либо значения, либо специальные ключи, определяемые для этих значений. По умолчанию элементы или ключи контейнеров сравниваются при помощи оператора <. Впрочем, программист может передать в контейнер собственную функцию сравнения и определить новый порядок сортировки.
Ассоциативные контейнеры обычно реализуются в виде бинарных деревьев. У каждого элемента (узла) есть один родитель и два потомка. Все предки слева от узла имеют меньшие значения, а все предки справа - большие значения. Ассоциативные контейнеры различаются по типу элементов и по тому, как они обходятся с дубликатами.
Ниже перечислены стандартные ассоциативные контейнеры, определенные в STL. Для обращения к их элементам применяются итераторы.
- Множества - коллекции, в которых элементы сортируются в соответствии с их значениями. Каждый элемент присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
- Мультимножества - то же, что и множества, но с возможностью хранения дубликатов. Это означает, что мультимножество может содержать несколько элементов с одинаковыми значениями.
- Отображения - коллекции, состоящие из пар "ключ/значение". У каждого элемента имеется ключ, определяющий порядок сортировки, и значение. Каждый ключ присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются. Отображение также может использоваться как ассоциативный массив, то есть массив с произвольным типом индекса.
- Мулътиотображения - то же, что и отображения, но с возможностью дублирования ключей. Это означает, что мультиотображение может содержать несколько элементов с одинаковыми ключами. Мультиотображение также может использоваться в качестве словаря.
У всех шаблонов классов ассоциативных контейнеров имеется необязательный аргумент для передачи критерия сортировки. По умолчанию в качестве критерия сортировки используется оператор <. Критерий сортировки также применяется при проверке на равенство; два элемента равны, если каждый из них не больше другого.
Множество можно считать особой разновидностью отображения, в котором значение идентично ключу. Все разновидности ассоциативных контейнеров обычно реализуются на базе бинарных деревьев.
На следующем шаге мы рассмотрим контейнерные адаптеры.
