Основы программирования на С++ для начинающих

Ассоциативные контейнеры STL. Часть 6

Все предыдущие типы контейнеров (рассмотренные подробно или упоминавшиеся: vector, list, deque) — это последовательные коллекции, в которых элементы последовательно упорядочены один за другим, а отличаются они между собой способом доступа к элементам.

Другую большую категорию контейнеров составляют так называемые ассоциативные контейнеры, которые представляют собой, фактически, таблицы, поиск значений в которых производится по некоторым ключам.

Но прежде чем детализировать ассоциативные контейнеры, обратим внимание на такой шаблонный класс (в составе STL) как pair<>. Это достаточно простая конструкция. Каждый такой объект представляет связную пару полей first и second. При построении таблиц (в STL или в ваших собственных классах) эти поля могут представлять как ключ, так и значение. Но не станем спешить — шаблонный класс pair<> и сам по себе может представлять интерес безотносительно к контейнерам.

Мы можем, например, определить класс представления точек 2D плоскости для решения широкого класса геометрических задач (файл point.h):

point p(*this); означает, что создаётся новая переменная (объект) класса point, и вызывается её копирующий конструктор. Для инициализации берётся значение текущего объекта *this – то на что указывает указатель this. Т.е. новая переменная point p создаётся, как копия текущего объекта. В остальном вам всё должно быть понятно.

Результат:

c++ для начинающих, Standard Template Library, ассоциативные контейнеры STL C++, pair<> c++

Теперь, когда мы видим, что из себя представляет шаблонный класс pair<>, мы можем перейти к обзору того, что представляют собой основные ассоциативные контейнеры STL.

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

Примечание: Можно считать, что в массиве или векторе ключом поиска является индекс, который всегда имеет целочисленное значение. По аналогии, шаблонный тип таблицы (хэш-таблицы) map<>, с которого мы начнём обзор ассоциативных типов, можно рассматривать, как массив или вектор (для простоты понимания ). Он может индексироваться любым (но всегда только одним) произвольным типом ключа, типа: title[ ‘a’ ], или pay[ “Иванов” ].

Одним из наиболее часто используемых ассоциативных контейнеров STL является map<> — таблица, массив пар <ключ, значение>, в котором поиск элемента производится по ключу.

Ключ может иметь любой сложный тип, при условии, что для этого типа существует операция сравнения (меньше-больше), или такая операция реализуется пользователем и указывается при создании таблицы. Для иллюстрации простейшего применения map<> воспользуемся уже рассмотренным раньше примером с базой данных студентов факультета:

Результат:

c++ для начинающих, Standard Template Library, ассоциативные контейнеры STL C++, pair c++, map<> c++

Даже такой поверхностный пример (пока мы не углубились в детали ассоциативных контейнеров) позволяет увидеть и сделать некоторые выводы:

  • Элементы, помещаемые в таблицу, размещены не в порядке их помещения (как было с vector или list), а в отсортированном порядке по значению ключа (ФИО);

  • Вот почему для типа данных ключа должна либо существовать операция сравнения, либо она должна быть создана пользователем;

Для поиска (по ключу) в ассоциативных контейнерах используется не последовательный перебор всех элементов, а в высшей степени эффективные и сложные алгоритмы, отработанные за годы (и даже десятилетия) существования STL . Обычно для реализации map<> используется техника красно-чёрных деревьев … но детали этого не принципиальны. Важным выводом из этого факта должно стать то, что поиск в ассоциативных контейнерах весьма быстр, и он гораздо лучше, чем если бы вы попытались его реализовывать вручную.

5 thoughts on “Ассоциативные контейнеры STL. Часть 6

  1. map, set, multiset, multimap – реализованы НЕ через хеш таблицы, а через красно-черные деревья, по крайней мере так в gcc. Через хэш таблицы реализованы контейнеры с префиксом unordered_. Очень странно что автор с 40-летним стажем и таким внушительным списком достижений об этом не знает.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *