Язык программирования C++. Пятое издание - Стенли Липпман

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

Итераторы упорядоченных контейнеров обеспечивают доступ к элементам по ключу. Элементы с тем же ключом хранятся рядом друг с другом и в упорядоченных, и в неупорядоченных контейнерах.

Термины

Ассоциативный контейнер (associative container). Тип, содержащий коллекцию объектов и обеспечивающий эффективный поиск по ключу.

Ассоциативный массив (associative array). Массив, элементы которого проиндексированы по ключу, а не по позиции. Таким образом, массив сопоставляет (ассоциирует) ключ со значением.

Контейнер map (карта). Ассоциативный контейнер, аналогичный ассоциативному массиву. Подобно типу vector, тип map является шаблоном класса. Но при создании карты необходимо указать два типа: тип ключа и тип связанного с ним значения. В контейнере map ключи уникальны, они не повторяются. Каждый ключ связан с определенным значением. Обращение к значению итератора карты возвращает объект типа pair, который содержит константный ключ и связанное (ассоциированное) с ним значение.

Контейнер multimap. Ассоциативный контейнер, подобный контейнеру map, но способный содержать одинаковые ключи.

Контейнер multiset. Ассоциативный контейнер, который содержит только ключи. В отличие от набора, способен содержать одинаковые ключи.

Контейнер set (набор). Ассоциативный контейнер, который содержит только ключи. Ключи в контейнере set не могут совпадать.

Контейнер unordered_map. Контейнер, элементы которого являются парами ключ-значение. Допустим только один элемент на ключ.

Контейнер unordered_multimap. Контейнер, элементы которого являются парами ключ-значение. Допустимо несколько элементов на ключ.

Контейнер unordered_multiset. Контейнер, хранящий ключи. Допустимо несколько элементов на ключ.

Контейнер unordered_set. Контейнер, хранящий ключи. Допустим только один элемент на ключ.

Неупорядоченный контейнер (unordered container). Ассоциативные контейнеры, использующие хеширование, а не сравнение ключей для хранения и доступа к элементам. Эффективность этих контейнеров зависит от качества хеш-функции.

Оператор *. Оператор обращения к значению, примененный к итератору контейнера map, set, multimap или multiset, возвращает объект типа value_type. Обратите внимание на то, что типом value_type контейнера map и multimap является пара (pair).

Оператор []. Оператор индексирования, примененный к контейнеру map, получает индекс, типом которого должен быть key_type (или тип, допускающий преобразование в него). Возвращает значение типа mapped_type.

Строгое сравнение (strict weak ordering). Отношения между ключами ассоциативного контейнера. При строгом сравнении можно сравнить два любых значения и выяснить, которое из них меньше. Если ни одно из значений не меньше другого, они считаются равными.

Тип key_type. Тип, определенный в шаблоне ассоциативного контейнера, которому соответствует тип ключей, используемых для сохранения и возвращения значения. У контейнера map тип key_type используется для индексации. У контейнера set типы key_type и value_type совпадают.

Тип mapped_type. Тип, определенный в шаблонах ассоциативных контейнеров map и multimap, которому соответствует тип хранимых значений.

Тип pair (пара). Тип, объект которого содержит две открытые переменные-члена по имени first (первый) и second (второй). Тип pair является шаблоном, при создании класса которого указывают два типа: тип первого и тип второго элемента.

Тип value_type. Тип элемента, хранимого в контейнере. У контейнеров set и multiset типы value_type и key_type совпадают. У контейнеров map и multimap этот тип представляет собой пару, первый элемент которой (first) имеет тип const key_type, а второй (second) — тип mapped_type.

Хеш (hash). Специальный библиотечный шаблон, который используют неупорядоченные контейнеры для управления позицией элементов.

Хеш-функция (hash function). Функция, сопоставляющая значения заданного типа с целочисленными значениями (size_t). Равные значения должны сопоставляться с равными целыми числами; неравные значения должны сопоставляться с неравными целым числами, если это возможно.

Глава 12

Динамическая память

Написанные до сих пор программы использовали объекты, имевшие четко определенную продолжительность существования. Глобальные объекты создаются при запуске программы и освобождаются по завершении выполнения программы. Локальные автоматические объекты создаются при входе в блок, где они определены, и удаляются при выходе из него. Статические локальные объекты создаются перед их первым использованием и удаляются по завершении программы.

В дополнение к автоматическим и статическим объектам язык С++ позволяет создавать объекты динамически. Продолжительность существования объектов, созданных динамически, не зависит от того, где они созданы; они существуют, пока не будут освобождены явно.

Процесс освобождения динамических объектов оказывается удивительно богатым источником ошибок. Чтобы сделать использование динамических объектов безопасней, библиотека определяет два типа интеллектуальных указателей, управляющих динамическим созданием объектов. Интеллектуальные указатели гарантируют, что объекты, на которые они указывают, будут автоматически освобождены в соответствующий момент.

До сих пор наши программы использовали только статические объекты или объекты, располагаемые в стеке. Статическая память используется для локальных статических переменных (см. раздел 6.1.1), для статических переменных-членов классов (см. раздел 7.6), а также для переменных, определенных вне функций. Стек используется для нестатических объектов, определенных в функциях. Объекты, расположенные в статической памяти или в стеке, автоматически создаются и удаляются компилятором. Объекты из стека существуют, только пока выполняется блок, в котором они определены; статические объекты создаются прежде, чем они будут использованы, и удаляются по завершении программы.

Кроме статической памяти и стека, у каждой программы есть также пул памяти, которую она может использовать. Это динамическая память (free store) или распределяемая память (heap). Программы используют распределяемую память для объектов, называемых динамически созданными объектами (dynamically allocated object), место для которых программа резервирует во время выполнения. Программа сама контролирует продолжительность существования динамических объектов; наш код должен явно освобождать такие объекты, когда они больше не нужны.

Хотя динамическая память иногда необходима, ее корректное освобождение зачастую довольно сложно.

12.1. Динамическая память и интеллектуальные указатели

Для управления динамической памятью в языке С++ используются два оператора: оператор new, который резервирует (а при необходимости и инициализирует) объект в динамической памяти и возвращает указатель на него; и оператор delete, который получает указатель на динамический объект и удаляет его, освобождая зарезервированную память.

Работа с динамической памятью проблематична, поскольку на удивление сложно гарантировать освобождение памяти в нужный момент. Если забыть освобождать память, то появится утечка памяти, если освободить область памяти слишком рано, пока еще есть указатели на нее, то получится указатель на не существующую более область памяти.

Чтобы сделать использование динамической памяти проще (и безопасный), новая библиотека предоставляет два типа интеллектуальных указателей (smart pointer) для управления динамическими объектами. Интеллектуальный указатель действует, как обычный указатель, но с важным дополнением: автоматически удаляет объект, на который он указывает. Новая библиотека определяет два вида интеллектуальных указателей, отличающихся способом управления своими базовыми указателями: указатель shared_ptr позволяет нескольким указателям указывать на тот же объект, а указатель unique_ptr — нет. Библиотека определяет также сопутствующий класс weak_ptr, являющийся второстепенной ссылкой на объект, управляемый указателем shared_ptr. Все три класса определены в заголовке memory.