如何更改 begin() 迭代器指向的值？

Question

在使用 STL 的 C++ 中，我有一个 std::forward_list<int> 我想修改其迭代器，但我不确定如何 to/if 它甚至是可能的。

假设我有一个包含以下元素的转发列表：

std::forward_list<int> list {1,2,3,4,5};

这里，list.begin()returns1。我怎样才能移动 list.begin()？假设我想将起始迭代器设置为索引 3。然后列表将如下所示：

{4,5,1,2,3} // includes adjusting list.end() the same amount of begin()

这可能吗？或者这是一种通过指针来做到这一点的方法？

Answer 1

这会将列表向前旋转 3 个元素（需要 #include <algorithm>）：

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

不过效率不是特别高，因为 std::next 是 O(n)。

也许可以考虑使用不同的数据结构，例如 std::vector 如果你真的关心这个。

Answer 2

我们来看一张图。您有一个包含五个元素的单链表。

  1 --> 2 --> 3 --> 4 --> 5 --> null
  ^                               ^
  |                               |
begin                            end

现在你想使列表的开头指向 4 的节点。

  1 --> 2 --> 3 --> 4 --> 5 --> null
                    ^             ^
                    |             |
                  begin          end

请注意在这张图片中，不再有任何东西指向带有 1 的节点。即使您调整了 end 迭代器，也无法按照箭头到达 1。节点 1、2 和 3 悬而未决，再也找不到了。这就是 std::forward_list 不允许您这样做的原因之一。

根本没有从 5 到 1 的路径，除非你自己造一条。不过你可以做一个。一种方法需要计算一个指向 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

这给你下面的图片。

           1 --> 2 --> 3 --> 4 --> 5 --> null
     ^                       ^     ^
     |                       |     |
slice_begin              slice_end |
                                   |
                               destination

现在的目标是严格在 slice_begin 和 slice_end 之间移动节点，以便它们排在 destination 之后。幸运的是，forward_list 有一个方法可以做到这一点。

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

现在你有你想要的4 -> 5 -> 1 -> 2 -> 3。

Answer 3

您似乎在问如何通过旋转来重新排列列表中的元素。有一种标准算法称为 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 会做的很多事情。

如何更改 begin() 迭代器指向的值？

How to change what value begin() iterator points to?

c++

iterator

linked-list