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

   
На этом шаге мы приведем общие сведения об ассоциативных контйнерах и дадим их классификацию.

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

   
Ассоциативные контейнеры обычно реализуются в виде бинарных деревьев. У каждого элемента (узла) есть один родитель и два
потомка. Все предки слева от узла имеют меньшие значения, а все предки справа - большие значения. Ассоциативные контейнеры
различаются по типу элементов и по тому, как они обходятся с дубликатами.

   
Ниже перечислены стандартные ассоциативные контейнеры, определенные в STL. Для обращения к их элементам
применяются итераторы.

  • Множества - коллекции, в которых элементы сортируются в соответствии с их значениями. Каждый элемент
    присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
  • Мультимножества - то же, что и множества, но с возможностью хранения дубликатов. Это означает, что
    мультимножество может содержать несколько элементов с одинаковыми значениями.
  • Отображения - коллекции, состоящие из пар "ключ/значение". У каждого элемента имеется ключ, определяющий
    порядок сортировки, и значение. Каждый ключ присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
    Отображение также может использоваться как ассоциативный массив, то есть массив с произвольным типом индекса.
  • Мулътиотображения - то же, что и отображения, но с возможностью дублирования ключей. Это означает, что
    мультиотображение может содержать несколько элементов с одинаковыми ключами. Мультиотображение также может использоваться
    в качестве словаря.

   
У всех шаблонов классов ассоциативных контейнеров имеется необязательный аргумент для передачи критерия сортировки. По
умолчанию в качестве критерия сортировки используется оператор <. Критерий сортировки также применяется при проверке на
равенство; два элемента равны, если каждый из них не больше другого.

   
Множество можно считать особой разновидностью отображения, в котором значение идентично ключу. Все разновидности
ассоциативных контейнеров обычно реализуются на базе бинарных деревьев.

   
На следующем шаге мы рассмотрим контейнерные адаптеры.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий