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

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

Обсуждение

vector

— это динамическая последовательность объектов, которая предоставляет произвольный доступ с помощью оператора в стиле массивов

operator[]

. Метод

push_back

при помощи копирующего конструктора копирует свой аргумент, добавляет копию в последний элемент вектора и увеличивает его размер на единицу.

pop_back

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

В большинстве

случаев

vector

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

vector

при использовании метода

at

(но не при использовании

operator[]

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

Пример 4.7. Проверка границ для векторов

#include <iostream>

#include <vector>

#include <exception>

using namespace std;

int main {

 char carr[] = {'a', 'b', 'c', 'd', 'e'};

 cout << carr[100000] << '\n'; // Оп, кто знает, что дальше

// произойдет

 vector<char> v;

 v.push_back('a');

 v.push_back('b');

 v.push_back('c');

 v.push_back('d');

 v push_back('e');

 try {

cout << v.at(10000) << "\n"; // at проверяет границы и выбрасывает

 } catch(out_of_range& е) { // out_of_range, если произошел выход за них

cerr << e.what << '\n';

 }

}

Перехват

out_of_range

, определенного в

<stdexcept>

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

what

, позволяющий в зависимости от используемой реализации получить осмысленное сообщение об ошибке, как возвращаемая в коде примера 4.7:

invalid vector<T> subscript

Однако

vector

не является единственной возможностью. В C++ имеется большое количество способов хранить последовательности. Кроме

vector

имеются

list

,

set

и двунаправленные очереди (

deque

— double-ended queue). Все они поддерживают множество одинаковых операций, и каждый поддерживает свои собственные. Кроме того, каждый имеет различную алгоритмическую сложность, требования по хранению и семантику. Так что имеется богатый выбор.

Посмотрите внимательно на пример 4.6. Вы, вероятно, обратите внимание, что я изменяю значение строки

s

до того, как добавляю ее в конец контейнера с помощью

push_back

. Логично ожидать такого вывода этого примера

three

three

three

Я

поместил в вектор одну и ту же строку три раза, так что каждый раз, когда я переприсваиваю строку, разве не должны все элементы вектора указывать на одну и ту же строку? Нет. Это важный момент, касающийся контейнеров STL.

Контейнеры STL сохраняют копии объектов, помещаемых в них, а не сами объекты. Так что после помещения в контейнер всех трех строк в памяти остается четыре строки: три копии, созданные и хранящиеся в контейнере, и одна копия, которой присваиваются значения.

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

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

delete

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

В целях создания альтернативного решения давайте рассмотрим еще одну возможность. Рассмотрим шаблон класса

list

, определенный в

<list>

, который является двусвязным списком (doubly linked list). Если планируется большое количество вставок и удалений элементов в середине последовательности или если требуется гарантировать, что итераторы, указывающие на элементы последовательности, не станут недействительными при ее изменении, используйте

list

. Пример 4.8 вместо

vector

для хранения нескольких строк типа

string

использует

list

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

for_each

.

Пример 4.8. Хранение строк в списке

#include <string>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

void write(const string& s) {

 cout << s << '\n';

}

int main {

 list<string> lst;

 string s = "нож";

 lst.push_front(s);

 s = "вилка";

 lst.push_back(s);

 s = "ложка";

 lst.push_back(s);

 // У списка нет произвольного доступа, так что

 // требуется использовать for_each

 for_each(lst.begin, lst.end, write);

}

Целью этого отступления от первоначальной проблемы (хранения строк в виде последовательностей) является краткое введение в последовательности STL. Здесь невозможно дать полноценное описание этого вопроса. За обзором STL обратитесь к главе 10 книги C++ in a Nutshell Рэя Лишнера (Ray Lischner) (O'Reilly).