Глава 6 Управление данными с помощью контейнеров

Глава 6

Управление данными с помощью контейнеров

6.0. Введение

Эта глава описывает структуры данных стандартной библиотеки, используемые для хранения данных. Часто они также называются контейнерами (containers), так как они содержат («contain») хранящиеся в них объекты. Также эта глава описывает другой тип контейнеров, который не является частью стандартной библиотеки, хотя и поставляется с большинством ее реализаций — хеш-контейнер.

Часть библиотеки, которая содержит контейнеры, часто называется Standard Template Library, или STL (стандартная библиотека шаблонов), именно так она называлась до ее включения в стандарт С++. STL включает не только контейнеры, обсуждаемые в этой главе, но и итераторы и алгоритмы, которые являются еще двумя строительными блоками STL, делающими STL гибкой библиотекой общего назначения. Так как эта глава в основном посвящена стандартным контейнерам, а не STL во всем ее многообразии, я буду называть контейнеры «стандартными контейнерами», а не «контейнерами STL», как это делается во многих книгах по С++. Хотя я по мере необходимости описываю итераторы и алгоритмы, более подробно они обсуждаются в главе 7.

Стандарт C++ использует для описания набора контейнеров точную терминологию. «Контейнер» в стандартной библиотеке C++ — это структура данных, имеющая четкий интерфейс, описанный в стандарте. Например, любой класс стандартной библиотеки С++, который называет себя контейнером, должен поддерживать метод begin, который не имеет параметров и возвращает iterator, указывающий на первый элемент в этом контейнере. Имеется большое количество обязательных конструкторов и функций-членов, определяющих, что такое контейнер в терминах С++. Также имеются необязательные методы, реализуемые только некоторыми контейнерами обычно теми, которые могут их эффективно реализовать.

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

Это выглядит очень похоже на наследование. Последовательность — это контейнер, ассоциативный контейнер — это контейнер, но контейнер — это не последовательность и не ассоциативный контейнер. Однако это не наследование в смысле С++, а наследование с точки зрения концепции, vector — это последовательность, но это самостоятельный класс. Он не наследует от класса container или подобного ему (реализации стандартной библиотеки имеют свободу в реализации vector и других контейнеров, но стандарт не предписывает реализации стандартной библиотеки включать базовый класс container). При разработке контейнеров было приложено большое количество усилий, и если вы хотите поподробнее узнать о них, обратитесь к книге Мэтта Остерна (Matt Austern) Generic Programming and the STL (Addison Wesley).

Эта глава содержит две части. Несколько первых рецептов рассказывают, как использовать vector, который является стандартной последовательностью и одной из наиболее популярных структурой данных. Они описывают, как эффективно и рационально использовать vector. Остальные рецепты описывают большую часть остальных широко применяемых стандартных контейнеров, включая два нестандартных хеш-контейнера, о которых я упоминал ранее.