在使用STL的C++中,我有一个std::forward_list<int>
,我想修改它的迭代器,但我不确定如何修改/是否可能。
假设我有一个包含以下元素的前向列表:
std::forward_list<int> list {1,2,3,4,5};
这里,list.begin()
返回1
。我如何移动list.begin()
?假设我想将开始迭代器设置为索引3。然后列表看起来像这样:
{4,5,1,2,3} // includes adjusting list.end() the same amount of begin()
这是可能的吗?或者这是一种通过指针来实现的方法?
3条答案
按热度按时间tf7tbtn21#
看起来你是在问如何通过旋转来重新排列列表中的元素。有一个标准的算法叫做
std::rotate
(及其对应的ranges
),它可以用线性复杂度来完成这个任务。它通过交换元素来工作。然而,链表-与大多数其他序列数据结构不同-有另一个工具,允许您以恒定的复杂度旋转它们:拼接。与双向链表相比,单链链表的拼接有点棘手,但它仍然是可能的。下面是一个例子:
重要的是要理解,尽管拼接具有恒定的复杂度并且非常快,但对
std::next
的调用具有线性复杂度,因此与std::rotate
渐近相同。因此,为了能够充分利用这一点,它最好用在你已经有了相关的迭代器而不需要搜索的情况下。这个条件通常适用于几乎所有的列表操作。如果你没有存储迭代器,那么要么你可能使用了错误的列表,要么你可能应该使用另一种数据结构。即使你确实需要搜索迭代器,如果交换元素的开销很大(不适用于
int
),这也会比std::rotate
快得多(不是渐进的,而是一个常数因子),而std::rotate
会做很多事情。kpbpu0082#
这将列表向前旋转3个元素(需要
#include <algorithm>
):这将具有O(n)的复杂度,因为它必须遍历整个列表(不能通过
list.end()
到达最后一个元素,因为这是一个前向迭代器)。如果这是不可接受的,请考虑使用不同的数据结构
std::list
std::vector
ruoxqz4g3#
让我们看一张图。你有一个包含五个元素的单链表。
现在,您希望使列表的开头指向具有
4
的节点。请注意,在此图中,不再有任何内容指向具有
1
的节点。即使您调整了end
迭代器,也无法按照箭头到达1
。节点1
,2
和3
仍然悬空,再也找不到了。这也是std::forward_list
不会让你这么做的一个原因。从
5
到1
根本没有路径,除非你创建一个。不过,你可以创建一个。一种方法需要计算一个指向5
节点的迭代器和一个指向4
节点的迭代器。这给你以下的图片。
现在的目标是严格地在
slice_begin
和slice_end
之间移动节点,使它们位于destination
之后。幸运的是,forward_list
有一个方法可以做到这一点。现在你已经有了你想要的
4 -> 5 -> 1 -> 2 -> 3
。