c++ 如何改变开始()迭代器指向的值?

dnph8jn4  于 2023-04-08  发布在  其他
关注(0)|答案(3)|浏览(108)

在使用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()

这是可能的吗?或者这是一种通过指针来实现的方法?

tf7tbtn2

tf7tbtn21#

看起来你是在问如何通过旋转来重新排列列表中的元素。有一个标准的算法叫做std::rotate(及其对应的ranges),它可以用线性复杂度来完成这个任务。它通过交换元素来工作。
然而,链表-与大多数其他序列数据结构不同-有另一个工具,允许您以恒定的复杂度旋转它们:拼接。与双向链表相比,单链链表的拼接有点棘手,但它仍然是可能的。下面是一个例子:

int size = 5;
int new_first_index = 3;
auto new_first = std::next(list.begin(), new_first_index);
auto inclusive_last = std::next(new_first, size - new_first_index - 1);

// the rotation:
list.splice_after(inclusive_last, list, list.before_begin(), new_first);

重要的是要理解,尽管拼接具有恒定的复杂度并且非常快,但对std::next的调用具有线性复杂度,因此与std::rotate渐近相同。因此,为了能够充分利用这一点,它最好用在你已经有了相关的迭代器而不需要搜索的情况下。这个条件通常适用于几乎所有的列表操作。如果你没有存储迭代器,那么要么你可能使用了错误的列表,要么你可能应该使用另一种数据结构。
即使你确实需要搜索迭代器,如果交换元素的开销很大(不适用于int),这也会比std::rotate快得多(不是渐进的,而是一个常数因子),而std::rotate会做很多事情。

kpbpu008

kpbpu0082#

这将列表向前旋转3个元素(需要#include <algorithm>):

std::rotate(list.begin(), std::next(list.begin(), 3), list.end());

这将具有O(n)的复杂度,因为它必须遍历整个列表(不能通过list.end()到达最后一个元素,因为这是一个前向迭代器)。
如果这是不可接受的,请考虑使用不同的数据结构

ruoxqz4g

ruoxqz4g3#

让我们看一张图。你有一个包含五个元素的单链表。
现在,您希望使列表的开头指向具有4的节点。
请注意,在此图中,不再有任何内容指向具有1的节点。即使您调整了end迭代器,也无法按照箭头到达1。节点123仍然悬空,再也找不到了。这也是std::forward_list不会让你这么做的一个原因。
51根本没有路径,除非你创建一个。不过,你可以创建一个。一种方法需要计算一个指向5节点的迭代器和一个指向4节点的迭代器。

auto slice_begin = list.before_begin();       // For consistent naming
auto slice_end = std::next(list.begin(), 3);  // Calculate iterator to 4
auto destination = std::next(slice_end);      // Calculate iterator to 5

这给你以下的图片。
现在的目标是严格地在slice_beginslice_end之间移动节点,使它们位于destination之后。幸运的是,forward_list有一个方法可以做到这一点。

list.splice_after(destination, list, slice_begin, slice_end);

现在你已经有了你想要的4 -> 5 -> 1 -> 2 -> 3

相关问题