2.5. Введение в ассоциативные контейнеры
Кроме массивов и списков, использующихся для реализации последовательных контейнеров (массивов, векторов, двусторонних очередей и списков), которые обсуждались до сих пор, сбалансированные деревья представляют собой другую классическую структуру данных, предназначенную для их эффективного хранения и извлечения. Сбалансированные деревья составляют основу для другой группы контейнеров, определенной в STL, так называемых (сортированных) ассоциативных контейнеров. Как и ранее, мы в основном сосредоточимся на том, как использовать эти контейнеры, а не на том, как они реализованы. Всего существует четыре типа этих контейнеров: множества (sets), множества с дубликатами (multisets), словари (maps), словари с дубликатами (multimaps). Перед тем как обсудить их использование, посмотрим, чем они различаются.
Множества
Каждый элемент множества является собственным ключом, и эти ключи уникальны. Поэтому два различных элемента множества не могут совпадать. Например, множество может состоять из следующих элементов:
123 124 800 950
Множества с дубликатами
Множество с дубликатами отличается от просто множества только тем, что способно содержать несколько совпадающих элементов. Например, допустимо существование множества с дубликатами, в котором присутствуют следующие четыре элемента:
123 123 800 950
Словари
Каждый элемент словаря имеет несколько членов, один из которых является ключом. В словаре не может быть двух одинаковых ключей. Приведем пример словаря из четырех элементов, у каждого из которых присутствует целочисленный ключ и буквенные сопутствующие данные:
123 John
124 Mary
800 Alexander 950 Jim
Словари с дубликатами
Словарь с дубликатами отличается от просто словаря тем, что в нем разрешены повторяющиеся ключи. Вот, к примеру, словарь с дубликатами, состоящий из четырех элементов (с целочисленными ключами):
123 John
123 Mary
800 Alexander
950 Jim
В отличие от последовательных контейнеров ассоциативные контейнеры хранят свои элементы отсортированными, вне зависимости от того, каким образом они были добавлены.
Заголовки и переносимость
В изначальной версии HP STL было четыре заголовка, связанных с рассматриваемой темой: set.h, multiseth, map.h и multimap.h. В проекте стандарта C++ остались только два: set и тар. Они используются также для ассоциативных контейнеров с дубликатами.
<< назад вперед >>