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




c++ для начинающих, Standard Template Library, ассоциативные контейнеры STL C++, pair c++, map<> c++Все предыдущие типы контейнеров (рассмотренные подробно или упоминавшиеся: 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<> используется техника красно-чёрных деревьев … но детали этого не принципиальны. Важным выводом из этого факта должно стать то, что поиск в ассоциативных контейнерах весьма быстр, и он гораздо лучше, чем если бы вы попытались его реализовывать вручную.

Рассылка новых уроков по программированию:

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

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

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

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