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

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

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

string s = "Marines";

vector<string>::iterator p = find(strVec.begin()

strVec.end(), s);

if (s != strVec.end()) // Вставляет s непосредственно перед элементом,

 strVec.insert(p, s);  // на который указывает p

Перегруженные версии insert позволяют вставлять в вектор n копий объекта, а также вставлять целый диапазон другой последовательности (эта последовательность может быть другим vector, массивом, list и т.п.).

Вместо вставки можно просто присвоить вектору уже существующую другую последовательность, стерев при этом то, что в нем содержалось до этого. Это выполняет метод assign. Вектору можно присвоить диапазон значений или n копий одного и того же объекта, как здесь.

string sarr[3] = {"Ernie", "Bert", "Elmo"};

string s = "Oscar";

strVec.assign(&sarr[0], &sarr[3]); // Присвоить эту последовательность

strVec.assign(50, s);              // Присвоить 50 копий s

Если новая последовательность окажется больше, чем имеющийся размер буфера vector, то assign изменит размер буфера так, чтобы разместить в нем всю новую последовательность.

После того как данные помещены в vector, имеется несколько способов получения их назад. Вероятно, наиболее интуитивным является operator[], который возвращает ссылку или const-ссылку в зависимости от того, является ли вектор const или нет, на элемент по указанному индексу. В этом отношении он ведет себя почти как массив:

for (int i = 0; i < intVec.size(); ++i) {

 std::cout << "intVec[" << i << "] = "

  << intVec[i] << 'n'; // rvalue

}

intVec[2] = 32; // lvalue

operator[] также ведет себя как массив в том, что при использовании индекса, который больше, чем индекс последнего элемента vector, результат не определен, что обычно означает, что будут повреждены данные программы или она обрушится. Избежать этого можно, запросив число элементов, содержащихся в vector, с помощью size(). Однако использованию operator[] следует предпочитать итераторы, так как их использование является стандартным для перебора элементов любого стандартного контейнера.

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

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

 std::cout << *p << 'n';

}

Итераторы являются наиболее мощным подходом, так как они позволяют обращаться с контейнерами одинаковым образом. Например, при написании алгоритма, который работает с последовательностями элементов, расположенными между двумя итераторами, он сможет работать с любым стандартным контейнером. Это общий подход. При использовании произвольного доступа с помощью operator[] вы ограничиваете себя использованием только тех контейнеров, которые поддерживают произвольный доступ. Первый подход позволяет алгоритмам стандартной библиотеки из <algorithm> одинаково работать со стандартными контейнерами (и другими типами, ведущими себя, как они).

Также vector предоставляет безопасность, которой просто невозможно достичь в случае обычных массивов. В отличие от массивов vector с помощью метода at предлагает проверку диапазонов. Если в at передается неправильный индекс, он выбрасывает исключение out_of_range, которое затем можно перехватить с помощью catch и адекватно на него отреагировать. Например:

try {

 intVec.at(300) = 2;

} catch(std::out_of_range& e) {

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

}

Как вы знаете, если обратиться к элементу за пределами массива с помощью operator[], оператор сделает то, что ему сказано сделать, и вернет то, что находится в указанной области памяти. Это плохо, так как либо программа обрушится в результате попытки доступа к области памяти, к которой она доступа не имеет, либо она молча изменит содержимое области памяти, принадлежащей другому объекту кучи, что обычно еще хуже. operator[] для vector работает точно так же, но когда требуется обезопасить код, используйте at.

Итак, вот краткий курс по vector. Но что такое vector? Если вы используете С++, то вас, вероятно, волнуют проблемы производительности, и вам не понравится, если вам просто дадут что-то и скажут, что это работает. Вполне справедливо. За обсуждением работы vector и советами по его эффективному использованию обратитесь к рецепту 6.2.

Рецепт 6.2.

6.2. Эффективное использование vector

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

Поймите, как реализован vector, узнайте о сложности методов вставки и удаления и минимизируйте ненужные операции с памятью с помощью метода reserve. Пример 6.2 показывает некоторые из этих методик в действии.

Пример 6.2. Эффективное использование vector

#include <iostream>

#include <vector>

#include <string>

using std::vector;

using std::string;

void f(vector<string>& vec) {

 // Передача vec по ссылке (или,

 // если требуется, через указатель)

 // ...

}

int main() {

 vector<string> vec(500); // При создании vector говорим, что в него

                          // планируется поместить определенное количество

                          // объектов

 vector<string> vec2;

 // Заполняем vec...

 f(vec);

 vec2 reserve(500); // Или постфактум говорим vector,

                    // что требуется буфер достаточно большого

                    // размера для хранения объектов

                    // Заполняем vec2...

}

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

vector — это по сути управляемый массив. Более конкретно, vector<T> — это непрерывный фрагмент памяти (т.е. массив), который достаточно велик для хранения n объектов типа T, где n больше или равно нулю и меньше или равно зависящему от реализации максимальному размеру. Обычно n увеличивается в процессе жизни контейнера при добавлении или удалении элементов, но оно никогда не уменьшается. Что отличает vector от массива — это автоматическое управление памятью массива, методы для вставки и получения элементов и методы, которые предоставляют метаданные о контейнере, такие как размер (число элементов) и емкость (размер буфера), а также информацию о типе: vector<T>::value_type — это тип T, vector<T>::pointer — это тип указатель-на-T и т.д. Два последних и некоторые другие являются частью любого стандартного контейнера, и они позволяют писать обобщенный код, который работает независимо от типа T. Рисунок 6.1 показывает графическое представление того, что предоставляют некоторые из методов vector, если vector имеет размер 7 и емкость 10.