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

В качестве примера рассмотрим следующий цикл, удаляющий нечетные элементы списка:

list lst = {0,1,2,3,4,5,6,7,8,9};

auto it = lst.begin();

while (it != lst.end())

if (*it % 2) // если элемент является нечетным

it = lst.erase(it); // удалить его

else

++it;

На каждой итерации проверяется нечетность текущего элемента. Если это так, то данный элемент удаляется, а итератор itустанавливается на следующий элемент после удаленного. Если элемент *itчетный, осуществляется приращение итератора it, чтобы при следующей итерации он указывал на следующей элемент.

Версия функции erase()с парой итераторов позволяет удалить диапазон элементов:

// удалить диапазон элементов между двумя итераторами

// возвращает итератор на элемент сразу после последнего удаленного

elem1 = slist.erase(elem1, elem2); // после вызова elem1 == elem2

Итератор elem1указывает на первый удаляемый элемент, а итератор elem2— на следующий после последнего удаляемого.

Чтобы удалить все элементы в контейнере, можно либо вызвать функцию clear(), либо перебирать итераторы от возвращаемого функцией begin()до end()и передавать их функции erase():

slist.clear(); // удалить все элементы в контейнере

slist.erase(slist.begin(), slist.end()); // эквивалент

Упражнение 9.25. Что будет, если в программе, где удалялся диапазон элементов, итераторы elem1и elem2равны? Что если итератор elem2или оба итератора ( elem1и elem2) являются итератором после конца?

Упражнение 9.26. Используя приведенное ниже определение массива ia, скопируйте его содержимое в вектор и в список. Используя версию функции erase()для одного итератора, удалите из списка элементы с нечетными значениями, а из вектора — с четными.

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };

Чтобы лучше понять, почему у контейнера forward_listесть специальные версии функций добавления и удаления элементов, рассмотрим, что происходит при удалении элемента из односвязного списка. Как показано на рис. 9.1, удаление элемента изменяет связи в последовательности. В данном случае удаление элемента elem3изменяет связь элемента elem2; элемент elem2указывал на элемент elem3, но после удаления элемента elem3элемент elem2указывает на элемент elem4.

Рис. 9.1. Специализированные функции контейнера forward_list

При добавлении или удалении элемента у элемента перед ним будет другой последователь. Чтобы добавить или удалить элемент, необходимо обратиться к его предшественнику и изменить его ссылку. Однако контейнер forward_list— это односвязный список. В односвязном списке нет простого способа доступа к предыдущему элементу. Поэтому функции добавления и удаления элементов в контейнере forward_listработают, изменяя элемент после указанного. Таким образом, у нас всегда есть доступ к элементам, на которые влияет изменение.

Поскольку эти функции ведут себя отлично от функций других контейнеров, класс forward_listне определяет функции-члены insert(), emplace()и erase(). Вместо них используются функции-члены insert_after(), emplace_after()и erase_after()(перечислены в табл. 9.8). На рисунке выше, например, для удаления элемента elem3использовалась бы функция erase_after()для итератора, обозначающего элемент elem2. Для реализации этих операций класс forward_listопределяет также функцию before_begin(), которая возвращает итератор после начала (off-the-beginning iterator). Этот итератор позволяет добавлять или удалять элементы после несуществующего элемента перед первым в списке.

Таблица 9.8. Функции вставки и удаления элементов контейнера forward_list

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

forward_list 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.