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

Это выглядит очень похоже на наследование. Последовательность — это контейнер, ассоциативный контейнер — это контейнер, но контейнер — это не последовательность и не ассоциативный контейнер. Однако это не наследование в смысле С++, а наследование с точки зрения концепции, 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.
 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 Value, // Тип элемента, который будет храниться в этом векторе
 typename Allocator = allocator<Value> > // используемый распределитель (allocator)
 // памяти

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

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

vector<int> intVec;

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

vector<string> 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 окажется достаточно места для добавления аргумента. Если место есть, то он добавляется в следующий неиспользуемый индекс, а если нет, то буфер увеличивается с помощью зависящего от реализации алгоритма, а затем в него добавляется аргумент