Реализация swd () в std :: forward_list в C ++ 11

Question

Я предполагаю, что в std::list<> функция swap для самого списка выполняется путем замены узла привязки.Узел может получить доступ к предыдущему узлу и легко обновить следующий указатель предыдущего узла, чтобы он указывал на якорь другого списка;но это не может быть сделано в std::forward_list (ну, может быть, это просто очень дорого).

Если мое предположение верно, как swap() эффективно реализуется в std::forward_list?И пока мы это делаем, как swap() реализовано для iterator с std::forward_list?

Answer 1

A std::forward_list - это просто односвязный, а не двусвязный список, такой как std::list, поэтому вы можете просто поменять местами указатели head и tail, чтобы выполнить операцию swap().

Answer 2

Я думаю, что вы сбиты с толку (или я не понимаю, о чем вы спрашиваете). std :: forward_list :: swap (std :: forward_list & other) тривиален, каждый объект списка обменивается указателями на начало их списка (и любые другие переменные-члены) - как std :: list.

У объекта итератора нет метода подкачки. Содержащийся объект может или может использовать метод глобальной замены, но он работает с объектами и не изменяет сам список или его узлы.

Answer 3

Это полностью зависит от реализации, но если прямые списки реализованы с помощью того, что класс просто хранит указатель на первую и последнюю ячейки связанного списка, тогда swap может просто поменять эти два указателя. Так как списки с прямой связью не имеют обратных указателей, больше обновлений делать не нужно, и всю операцию можно выполнить в O (1).

Что касается обмена с итераторами, это фактически не обменивается ячейками связанного списка между двумя списками; он просто имеет первую точку итератора в ячейке, на которую ссылается второй итератор, и наоборот. Если вы хотите поменять местами значения, на которые указывают, то это можно сделать, просто изменив объекты в ячейках связанного списка, чтобы они меняли значения. Вам не нужно переписывать списки в любом случае.

Надеюсь, что поможет!