STL算法能否用于循环链表？

Question

创建一个符合STL标准的迭代器以适应自定义列表是相当平凡的。然而，如果所涉及的列表是循环的，则似乎毫无意义，因为所有STL算法都在一个“[first，last)”范围内操作，在循环列表中，“first = last”。是否有一种标准/简明的方法来克服这个障碍，并使STL算法操作“自制”的循环列表？我假设定义符合STL标准的迭代器是实现此目标的第一步，但也可能存在操作范围的解决方案。

---

我需要为大量“自制”结构体实现这个功能。我的当前解决方案是从boost::iterator_facade派生，然后创建一个自定义的range类（例如 Rudolph's），并使用任何包装在基于范围执行的算法周围的算法。尽管如此，这仍然存在一些逻辑障碍，我希望看到其他替代方案或解决方案。

- Nikos Athanasiou

---

只有在循环列表中定义了 end()，这才能正常工作。如果您能够做到这一点，并且从 begin() 迭代可以到达那里，我就看不出有什么问题了。 - Salgar

你可以拥有两种不同类型的迭代器，一种实现环绕功能，另一种实现通常的语义。 - filmor

你会发现一个主要的障碍是循环列表具有依赖于上下文的“第一”和“最后”的概念。从列表中的两个不同位置开始作为“第一”将产生两个不同的“最后”概念。听起来微不足道，但在实践中可能会很快变得混乱。 - WhozCraig

请查看boost::circular_buffer（http://www.boost.org/doc/libs/1_55_0/doc/html/circular_buffer.html）。 - tillaert

Answer 1

您需要自定义迭代器，但解决方案仍然可以基于范围。 一种可能性是`begin()`可以返回一个特别标记的迭代器（标志为`initial=true`），以便它知道它还没有完成整个循环。`end()`将返回一个标志设置为false的迭代器。然后`operator++`会将标志设置为false，这样`begin()`就不等于`end()`了。您也可以使用不同的标记方案。

- isarandi

---

不幸的是，这只适用于“只读”迭代器。这种方法的基本问题是，在迭代过程中，初始节点可能会被删除，因此*begin()和end()都可能失效，并且end()*无法重新计算。 - Grim Fandango

Answer 2

我的理解与你的主张不一致，C++标准库中迭代器的语义类似于指针。它们不会被包装，end()也不等于begin()。

作为指针的类比，迭代器指向缓冲区中的位置。你不能期望一个天真的调用者进行线性复制操作时在结尾处环绕。这将适用于算法和其他库。据我所见，它们根本不会像预期的那样工作。

我认为你完全可以使用STL集合和迭代器，但我不认为你应该期望（或强制）it++进行环绕。我认为你需要清晰可见的成员函数来实现所需的附加功能。

例如，你可以有一个incr()函数来增加一个迭代器，但如果它指向end()，则会回到开头。你可以有一个copy()函数，它可以理解如何在包装的缓冲区中提取或插入数据块。

但是我不理解你的其他限制，所以这可能对你无效。但我认为这对我来说是有效的。

- david.pfx

---

你肯定不能预期线性复制操作能在所有容器上都适用。以链表或映射为例。 - Skizz

@Skizz：我可能可以更好地表达，但是如果first===last，copy(first,last,result)肯定不起作用。 - david.pfx

Answer 3

在许多算法中（我不是在谈论STL，而是一般情况下），为了提高性能，在内部数据结构中插入一个空叶子或空元素。我认为，在循环列表中保留一个空/空元素可以起到同样的效果。

• 显然，空元素的位置不固定，它将根据您的数据流移动。
• 同时，您将在数据结构中保留最后N个样本（大小为N + 1的空元素）。
• 这使得范围[first，last)成为可能，其中first！= last。
• 空元素是由last指向的元素，也是下一个插入的位置。
• 每次插入时，一旦容器中有N个元素，指向first的元素就会被“置空”，并且first会递增。

希望这可以帮助到您。

- Stefano Buora