C++. Сборник рецептов - [83]

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

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

6.1. Использование 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).