循环缓冲区的 C++ 自定义迭代器，如何实现 end()？

Question

我写了一个大小为 N 的循环缓冲区。我还写了一个自定义迭代器。

我将它们用于这样的逻辑:

auto iter = circular_buffer.begin();
while(iter != circular_buffer.end())
{
    ++iter;
}

end() 的实现是什么？通常它应该指向最后一个元素+1，但如果缓冲区包含 N 个项目，最后一个元素+1 将是第一个元素，上面的代码甚至不会循环一次。我做不到:

do
{
   ++iter;
} while(iter != circular_buffer.end());

因为如果缓冲区为空，它会执行一次。

有办法解决吗？

Answer 1

注意:以下假设缓冲区的循环性质是一个向用户公开供其使用的属性，而不是系统的实现细节(如 std::列出实现)。

给圆一个合适的“范围”是个问题，因为……它是一个圆。它在概念上既没有开始也没有结束。

一种方法是将“圆”变成螺旋线。每个迭代器都存储它需要的任何正常信息以及循环计数。当迭代器递增到列表的任意“开始”时，循环计数递增。如果迭代器递减到列表开头之前，则循环计数递减。两个迭代器只有在它们的位置 和 循环计数相等时才相等。

大多数由循环列表创建的迭代器在构建时的循环计数应该为零。 end 迭代器的循环计数应为 1，同时在圆中的位置与 begin 迭代器相同。

当然，还有一些实现问题。这样做需要每个迭代器的递增/递减操作都知道圆的“起点”在哪里。所以他们都需要一个指向第一个元素的指针什么的。但是如果他们有那个，那么如果你修改列表，这些迭代器都会变得无效，因为这会改变“第一个元素”是什么。现在，在容器修改时使迭代器失效是许多容器迭代器类型的真实情况，所以这不是什么大问题。但这是您应该注意的事情。

这是尝试将范围与本质上既没有开始也没有结束的概念一起使用时不可避免的缺点。