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

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

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};

auto prev = flst.before_begin(); // обозначает элемент "перед началом"

                                 // контейнера flst

auto curr = flst.begin(); // обозначает первый элемент контейнера flst

while (curr != flst.end()) { // пока есть элементы для обработки

 if (*curr % 2)                  // если элемент нечетный

  curr = flst.erase_after(prev); // удалить его и переместить curr

 else {

  prev = curr; // переместить итератор на следующий элемент

  ++curr;      // и один перед следующим элементом

 }

}

Здесь итератор curr обозначает проверяемый элемент, а итератор prev — элемент перед curr. Итератор curr инициализирует вызов функции begin(), чтобы первая итерация проверила на четность первый элемент. Итератор prev инициализирует вызов функции before_begin(), который возвращает итератор на несуществующий элемент непосредственно перед curr.

Когда находится нечетный элемент, итератор prev передается функции erase_after(). Этот вызов удаляет элемент после обозначенного итератором prev; т.е. элемент, обозначенный итератором curr. Итератору curr присваивается значение, возвращенное функцией erase_after(). В результате он обозначит следующий элемент последовательности, а итератор prev останется неизменным; он все еще обозначает элемент перед (новым) значением итератора curr. Если обозначенный итератором curr элемент не является нечетным, то в части else оба итератора перемещаются на следующий элемент.

Упражнения раздела 9.3.4

Упражнение 9.27. Напишите программу для поиска и удаления нечетных элементов в контейнере forward_list<int>.

Упражнение 9.28. Напишите функцию, получающую контейнер forward_list<string> и два дополнительных аргумента типа string. Функция должна находить первую строку и вставлять вторую непосредственно после первой. Если первая строка не найдена, то вставьте вторую строку в конец списка.

9.3.5. Изменение размеров контейнера

Для изменения размера контейнера, за исключением массива, можно использовать функцию resize(), представленную в табл. 9.9. Если текущий размер больше затребованного, элементы удаляются с конца контейнера; если текущий размер меньше нового, элементы добавляются в конец контейнера:

list<int> ilist(10, 42); // 10 целых чисел со значением 42

ilist.resize(15);        // добавляет 5 элементов со значением 0

                         // в конец списка ilist

ilist.resize(25, -1);    // добавляет 10 элементов со значением -1

                         // в конец списка ilist

ilist.resize(5);         // удаляет 20 элементов от конца списка ilist

Функция resize() получает необязательный аргумент — значение элемента, используемое для инициализации всех добавляемых элементов. Если этот аргумент отсутствует, добавленные элементы инициализируются значением по умолчанию (см. раздел 3.3.1). Если контейнер хранит элементы типа класса и функция resize() добавляет элементы, то либо следует предоставить инициализатор, либо тип элемента должен иметь стандартный конструктор.

Таблица 9.9. Функции размера последовательного контейнера

За исключением массива c.resize(n) Измените размеры контейнера с так, чтобы у него было n элементов. Если n < c.size(), то лишние элементы отбрасываются. Если следует добавить новые элементы, они инициализируются значением по умолчанию с.resize(n,t) Измените размеры контейнера с так, чтобы у него было n элементов. Все добавляемые элементы получат значение t

Если функция resize() сокращает контейнер, то итераторы, ссылки и указатели на удаленные элементы окажутся некорректными; выполнение функции resize() для контейнеров vector, string и deque может сделать некорректными все итераторы, указатели и ссылки.

Упражнения раздела 9.3.5

Упражнение 9.29. Если контейнер vec содержит 25 элементов, то что делает выражение vec.resize(100)? Что если затем последует вызов vec.resize(10)?

Упражнение 9.30. Какие ограничения (если они есть) налагает использование функции resize() с одиночным аргументом, имеющим тип элемента?

9.3.6. Некоторые операции с контейнерами делают итераторы недопустимыми

Функции, добавляющие и удаляющие элементы из контейнера, могут сделать некорректными указатели, ссылки или итераторы на его элементы. Некорректными считаются те указатели, ссылки и итераторы, которые больше не указывают на элемент. Использование некорректного указателя, ссылки или итератора является серьезной ошибкой, последствия которой, вероятно, будут схожи с использованием неинициализированного указателя (см. раздел 2.3.2, стр. 89).

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

• Итераторы, указатели и ссылки на элементы вектора или строки становятся недопустимыми после повторного резервирования пространства контейнера. Если повторного резервирования не было, ссылки на элементы перед позицией вставки остаются допустимыми, а на элементы после позиции вставки — нет.

• Итераторы, указатели и ссылки на элементы двухсторонней очереди становятся недопустимыми после добавления элементов в любую позицию кроме начала или конца. При добавлении в начало или в конец недопустимыми становятся только итераторы, а ссылки и указатели на существующие элементы — нет.

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

• У контейнеров list и forward_list все остальные итераторы, ссылки и указатели (включая итераторы после конца и перед началом) остаются допустимыми.

• У контейнера deque все остальные итераторы, ссылки и указатели становятся недопустимыми, если удалены элементы в любой позиции, кроме начала или конца. Если удаляются элементы в конце, итератор после конца становится недопустимым, но другие итераторы, ссылки и указатели остаются вполне допустимыми. То же относится к удалению из начала.

• У контейнеров vector и string все остальные итераторы, ссылки и указатели на элементы перед позицией удаления остаются допустимыми. При удалении элементов итератор после конца всегда оказывается недопустимым.

Использование недопустимого итератора, указателя или ссылки является серьезной ошибкой, которая проявится во время выполнения программы.

Совет. Контроль итераторов

При использовании итератора (или ссылки, или указателя на элемент контейнера) имеет смысл минимизировать ту часть программы, где итератор обязан оставаться допустимым.

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

Создание циклов, которые изменяют контейнер

Циклы, добавляющие или удаляющие элементы из контейнеров vector, string или deque, должны учитывать тот факт, что итераторы, ссылки и указатели могут стать недопустимыми. Программа должна гарантировать, что итератор, ссылка или указатель обновляется на каждом цикле. Если цикл использует функцию insert() или erase(), обновить итератор довольно просто. Они возвращают итераторы, которые можно использовать для переустановки итератора:

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

// нечетных

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