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

Чтобы лучше понять, почему у контейнера 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

lst.before_begin() lst.cbefore_begin()	Возвращает итератор, обозначающий несуществующий элемент непосредственно перед началом списка. К значению этого итератора обратиться нельзя. Функция cbefore_begin() возвращает итератор const_iterator
lst.insert_after(p,t) lst.insert_after(p,n,t) lst.insert_after(p,b,e) lst.insert_after(p,il)	Вставляет элемент (элементы) после обозначенного итератором p. t — это объект, n — количество, b и е — обозначающие диапазон итераторы (они не должны принадлежать контейнеру lst), il — список, заключенный в скобки. Возвращает итератор на последний вставленный элемент. Если диапазон пуст, возвращается итератор p. Если p — итератор после конца, результат будет непредсказуемым
emplace_after(p, args)	Параметр args используется для создания элементов после обозначенного итератором p. Возвращает итератор на новый элемент. Если p — итератор после конца, результат будет непредсказуемым
lst.erase_after(p) lst.erase_after(b,e)	Удаляет элемент после обозначенного итератором p или диапазоном элементов после обозначенного итератором b и до, но не включая обозначенного итератором е. Возвращает итератор на элемент после удаленного или на элемент после конца контейнера. Если p — итератор после конца или последний элемент контейнера, результат будет непредсказуемым

При добавлении или удалении элементов в контейнер 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. Функция должна находить первую строку и вставлять вторую непосредственно после первой. Если первая строка не найдена, то вставьте вторую строку в конец списка.