I have written a circular buffer of size N. I've also written a custom iterator.

I'm using them for logic like this:

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

What is the implementation for end()? Usually it should point to the last element 1, but if the buffer contains N items, last element 1 will be the first element and the above code won't even loop once. I cannot do:

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

because if the buffer is empty, it will execute once.

Is there a way to solve this?

CodePudding user response：

Note: the following assumes that the circular nature of the buffer is a property that is being exposed to the user for their use, rather than being an implementation detail of the system (as is the case for std::list implementations).

Giving a circle a proper "range" is something of a problem since... it's a circle. It conceptually has neither a beginning nor an end.

One way to do this is to make the "circle" into a helix. Every iterator stores both whatever normal information it needs as well as a cycle count. When an iterator is incremented to whatever the arbitrary "beginning" of the list is, the cycle count is incremented. If the iterator is decremented to before the beginning of the list, the cycle count is decremented. Two iterators are only equal if their position and cycle counts are equal.

Most iterators created by the circular list should have a cycle count of zero on construction. The end iterator should have a cycle count of 1 while having the same position in the circle as the begin iterator.

Of course, there are some implementation problems. Doing this requires that every iterator's increment/decrement operations to know where the "beginning" of the circle is. So they all need a pointer to the first element or something. But if they have that, then these iterators all become invalid if you modify the list, since that can change what the "first element" is. Now, invalidating iterators on container modification is something that is true of many container iterator types, so it's not too big of a problem. But it is something you should be aware of.

That's kind of an unavoidable downside of trying to use ranges with a concept that inherently has neither a beginning nor an end.