C++. Сборник рецептов

Когсуэлл Джефф

Имеется множество других политик, которые можно использовать с типом

ConstrainedValue

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

Глава 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

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

6.1. Использование vector вместо массивов

Проблема

Требуется сохранить элементы (встроенные типы, объекты, указатели и т.п.) в виде последовательности, обеспечить произвольный доступ к ним, и не ограничивать место хранения массивом статического размера.

Решение

Используйте шаблон класса

vector

стандартной библиотеки, определенный в

<vector>

, и не используйте массивы.

vector

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

vector

.

Пример 6.1. Использование некоторых методов vector

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int main {

 vector<int> intVec;

 vector<string> strVec;

 // Добавление элементов в "конец" вектора с помощью push_back

 intVec.push_back(3);

 intVec.push_back(9);

 intVec.push_back(6);

 string s = "Army";

 strVec.push_back(s);

 s = "Navy";

 strVec.push_back(s);

 s = "Air Force";

 strVec.push_back(s);

 // Для доступа к элементам используется operator[], как и для массивов

 for (vector<string>::size_type i = 0; i < intVec.size; ++i) {

cout << "intVec[" << i << "] = " << intVec[i] << '\n';

 }

 // Или можно использовать итераторы

 for (vector<string>::iterator p = strVec.begin;

p != strVec.end; ++p) {

cout << *p << '\n';

 }

 // Если требуется безопасность, вместо operator[] используйте at. Она

 // при использовании индекса > size выбрасывает исключение out_of_range.