STL算法能与循环列表一起使用吗？

Question

为您的自定义列表创建一个符合STL标准的迭代器非常普通。

然而，如果reffered列表是循环列表，那么由于所有的STL算法都是在[first, last)范围和循环列表first = last中操作，所以它似乎毫无意义。

是否有一种标准/同意的方法来克服这个障碍，和是否在“国产”循环列表上运行STL算法？

我假设定义符合STL的迭代器是实现这一目标的第一步，但是在范围上操作的解决方案也是可能的。

我需要为大量的“国产”结构实现这一点。我目前的解决方案是从boost::iterator_facade派生，然后创建一个自定义的range类(如鲁道夫氏)，并使用围绕基于范围的执行的任何算法。尽管如此，这仍然存在一些合乎逻辑的障碍，并希望看到替代方案和解决办法得到解决。

Answer 1

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

Answer 2

我对STL及其迭代器的理解与您的命题不一致。C++标准库中的迭代器(如现在所知)具有指针的语义。它们不包装，end()不等于begin()。

作为指针类似物，迭代器指向缓冲区中的位置。您不能期望天真的调用方在结束时进行线性复制操作。这将通过算法和其他库应用。据我所见，他们根本不会像我所期望的那样工作。

我完全没有理由不使用STL集合和迭代器，但我认为您不应该期望(或强制) it++包装。我认为您需要明确可见的成员函数来实现所需的附加功能。

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

但是我不明白你的其他约束，所以这可能对你不起作用。我觉得这对我有用。

Answer 3

在许多算法中(我不是说STL，但通常是这样)，为了提高性能，在内部数据结构中插入了一个空叶或空元素，我觉得在循环列表中保留一个空/空元素可以达到这个目的。

• 显然，空元素不是固定的，它将根据数据流移动。
• 同时，数据结构(大小为N+1空元素)中的最后一个N样例将保持连续。
• 这使得范围[first,last)成为可行，其中first != last。
• null元素是最后一个指向的元素，也是下一个插入的位置。
• 在每次插入时，一旦N个元素在容器中，first所指向的元素就会被“空化”，并且first会增加。

希望这能帮上忙。