Д. Стефенс - C++. Сборник рецептов

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

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

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

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

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

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

#include

#include

#include

using namespace std;

int main() {

vector intVec;

vector 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::size_type i = 0; i < intVec.size(); ++i) {

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

}

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

for (vector::iterator p = strVec.begin();

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

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

}

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

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

try {

intVec.at(300) = 2;

} catch(out_of_range& e) {

cerr << "out_of_range: " << e.what() << endl;

}

}

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

Если вы не знакомы с контейнерами, поставляющимися в составе стандартной библиотеки, или не сталкивались с использованием шаблонов классов (и их написанием), то объявление vectorв примере 6.1 требует некоторых пояснений. Объявление vectorимеет следующий вид.

vector

typename Allocator = allocator > // используемый распределитель (allocator)

// памяти

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

Если вы хотите, чтобы vectorхранил элементы типа int, объявите его, как в этом примере.

vector intVec;

А если вам требуется, чтобы он хранил строки, просто измените тип аргумента vector.

vector strVec;

vectorможет содержать любой тип С++, который поддерживает конструктор копирования и присвоение.

Следующее, что логически требуется сделать после создания экземпляра vector, — это что-либо поместить в него. В конец вектора элементы добавляются с помощью push_back.

intVec.push_back(3);

intVec.push_back(9);

intVec.push_back(6);

Это примерно эквивалентно добавлению элементов 0, 1 и 2 в массив. Это «примерно» эквивалентно потому, что, конечно, push_back— это метод, который возвращает voidи помещает свой аргумент в конец вектора. operator[]возвращает ссылку на область памяти, на которую указывает индекс массива, push_backгарантирует, что во внутреннем буфере vectorокажется достаточно места для добавления аргумента. Если место есть, то он добавляется в следующий неиспользуемый индекс, а если нет, то буфер увеличивается с помощью зависящего от реализации алгоритма, а затем в него добавляется аргумент

Также с помощью метода insertможно вставить элементы в середину вектора, хотя этого следует избегать из-за линейно возрастающей сложности этой операции. За более подробным обсуждением проблем производительности и их решения при использовании vectorобратитесь к рецепту 6.2. Чтобы вставить элемент, получите итератор на точку, куда требуется его вставить (обсуждение итераторов приводится в рецепте 7.1).

string s = "Marines";

vector::iterator p = find(strVec.begin()