Стенли Липпман - Язык программирования C++. Пятое издание

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

// нечетных

vector vi = {0,1,2,3,4,5,6,7,8,9};

auto iter = vi.begin(); // поскольку vi изменяется, используется

// функция begin(), а не cbegin()

while (iter != vi.end()) {

if (*iter % 2) {

iter = vi.insert(iter, *iter); // дублирует текущий элемент

iter +=2; // переместить через элемент

} else

iter = vi.erase(iter); // удалить четные элементы

// не перемещать итератор; iter обозначает элемент после

// удаленного

}

Эта программа удаляет четные элементы и дублирует соответствующие нечетные. После вызова функций insert()и erase()итератор обновляется, поскольку любая из них способна сделать итератор недопустимой.

После вызова функции erase()никакой необходимости в приращении итератора нет, поскольку возвращенный ею итератор обозначает следующий элемент в последовательности. После вызова функции insert()итератор увеличивается на два. Помните, функция insert()осуществляет вставку перед указанной позицией и возвращает итератор на вставленный элемент. Таким образом, после вызова функции insert()итератор iterобозначает элемент (недавно добавленный) перед обрабатываемым. Приращение на два осуществляется для того, чтобы перескочить через добавленный и только что обработанный элементы. Это перемещает итератор на следующий необработанный элемент.

Не храните итератор, возвращенный функцией end()

При добавлении или удалении элементов в контейнер vectorили stringлибо при добавлении или удалении элементов в любую, кроме первой, позицию контейнера dequeвозвращенный функцией end()итератор всегда будет недопустимым. Потому циклы, которые добавляют или удаляют элементы, всегда должны вызывать функцию end(), а не использовать хранимую копию. Частично поэтому стандартные библиотеки С++ реализуют обычно функцию end()так, чтобы она выполнялась очень быстро.

Рассмотрим, например, цикл, который обрабатывает каждый элемент и добавляет новый элемент после исходного. Цикл должен игнорировать добавленные элементы и обрабатывать только исходные. После каждой вставки итератор позиционируется так, чтобы обозначить следующий исходный элемент. Если попытаться "оптимизировать" цикл, сохраняя итератор, возвращенный функцией end(), то будет беда:

// ошибка: поведение этого цикла непредсказуемо

auto begin = v.begin(),

end = v.end(); // плохая идея хранить значение итератора end

while (begin != end) {

// некоторые действия

// вставить новое значение и переприсвоить итератор begin, который

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

++begin; // переместить begin, поскольку вставка необходима после

// этого элемента

begin = v.insert(begin, 42); // вставить новое значение

++begin; // переместить begin за только что добавленный элемент

}

Поведение этого кода непредсказуемо. На многих реализациях получится бесконечный цикл. Проблема в том, что возвращенное функцией end()значение хранится в локальной переменной end. В теле цикла добавляется элемент. Добавление элемента делает итератор, хранимый в переменной end, недопустимым. Этот итератор не указывает ни на какой элемент в контейнере v, ни на следующий после его конца.

Не кешируйте возвращаемый функцией end()итератор в циклах, которые вставляют или удаляют элементы в контейнере deque, stringили vector.

Вместо того чтобы хранить итератор end, его следует повторно вычислять после каждой вставки:

// существенно безопасный: повторно вычислять end после каждого

// добавления/удаления элементов

while (begin != v.end()) {

// некоторые действия

++begin; // переместить begin, поскольку вставка необходима после

// этого элемента

begin = v.insert(begin, 42); // вставить новое значение

++begin; // переместить begin за только что добавленный элемент

}

Упражнение 9.31. Программа из пункта «Создание циклов, которые изменяют контейнер», удаляющая четные и дублирующая нечетные элементы, не будет работать с контейнером listили forward_list. Почему? Переделайте программу так, чтобы она работала и с этими типами тоже.

Упражнение 9.32. Будет ли допустим в указанной выше программе следующий вызов функции insert()? Если нет, то почему?

iter = vi.insert(iter, *iter++);

Упражнение 9.33. Что будет, если в последнем примере этого раздела не присваивать переменной beginрезультат вызова функции insert()? Напишите программу без этого присвоения, чтобы убедиться в правильности своего предположения.

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

iter = vi.begin();

while (iter != vi.end())

if (*iter % 2)

iter = vi.insert(iter, *iter);

++iter;

Для обеспечения быстрого произвольного доступа элементы вектора хранятся последовательно — каждый элемент рядом с предыдущим. Как правило, нас не должно заботить то, как реализован библиотечный тип; достаточно знать, как его использовать. Но в случае векторов и строк реализация частично просачивается в интерфейс.

С учетом того, что элементы последовательны и размер контейнера гибок, рассмотрим происходящее при добавлении элемента в вектор или строку: если для нового элемента нет места, контейнер не сможет просто добавить элемент в некую другую область памяти — элементы должны располагаться последовательно. Поэтому контейнер должен зарезервировать новую область памяти, достаточную для содержания уже существующих элементов, плюс новый элемент, а затем переместить элементы из старой области в новую, добавить новый элемент и освободить старую область памяти. Если бы вектор осуществлял резервирование и освобождение памяти при каждом добавлении элемента, его работа была бы неприемлемо медленной.

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