std :: forward_list在C++中的swap（）实现11

我的假设是，在std::list<>中，列表本身的swap函数是通过交换锚节点完成的。该节点可以访问前一个节点并轻松更新前一个节点的下一个指针，以指向另一个列表的锚点;但是这不能在std::forward_list中完成（当然，这可能非常昂贵）。std :: forward_list在C++中的swap（）实现11

如果我的假设是正确的，swap()如何以有效的方式在std::forward_list中实现？而我们在这个时候，swap()如何实现的std::forward_list？

来源

2012-01-25 Samaursa

一个std::forward_list简直就是一个单链接，而不是像std::list双向链表，所以你可以简单地交换名单的head和tail指针以完成swap()操作。

来源

2012-01-25 18:31:44 Jason

我的印象是'std :: list'在内部是一个循环列表，我假设'std :: forward_list'是一样的。我猜测这完全取决于实施。 – Samaursa

即使它们是循环链表，仍然不需要更新节点上的任何指针。整个列表正在交换，因此没有任何节点链接会改变。所有这些变化都是从std :: list到节点的指针。 – bames53

@ bames53：如果它是一个循环列表，那么每个节点都指向下一个节点或列表的尾部。而列表尾部指向头部，而头部又指向第一个元素。那么如何交换尾指针，因为您需要调整指向尾部的节点，并且除非遍历整个列表，否则无法到达尾指针。或者尾指针是指向头部以及最后一个节点的对象？ – Samaursa

这完全是特定于实现的，但如果通过让类只存储指向第一个和最后一个链接列表单元的指针来实现转发列表，那么swap就可以交换这两个指针。由于前向链表没有任何后退指针，因此不需要进行更新，整个操作可以在O（1）中完成。

至于与迭代器交换，这实际上并没有交换两个列表之间的链接列表单元格;它只有第一个迭代器指向第二个迭代器引用的单元格，反之亦然。如果要交换指向的值，则可以通过修改链接列表单元格中的对象以便更改值来完成此操作。你不需要以任何方式重新列表。

希望有所帮助！

来源

2012-01-25 18:32:46 templatetypedef

啊，当然！（+1） – Samaursa

我相信forward_list甚至不需要存储尾指针，但可以使用通用的空迭代器作为结束迭代器。 –

我觉得你很困惑（或者我对你的要求感到困惑）。 std :: forward_list :: swap（std :: forward_list &其他）很简单，每个列表对象交换指向其列表头部的指针（以及任何其他成员变量） - 就像std :: list一样。

迭代器对象没有交换方法。包含的对象可能或可能使用全局交换方法 - 但是对对象进行操作，并且不会改变列表本身或其节点。

来源

2012-01-25 18:32:49

std :: forward_list在C++中的swap（）实现11

回答

相关问题