Filip S Filip S - 13 days ago 9
C++ Question

Can I implement iterator end() in ring?

First, I cannot really find much info about ring data structure on the Internet, so here's a short implementation showing what a ring is (according to my lecturer)

template<typename Key, typename Info>
class Ring
{
struct Node // structure for storing the data
{
Key k;
Info inf;

Node* next;
Node* prev;
};

Node* any; // pointer to a node belonging to the ring, NULL if the ring is empty
};


It's similar to a circular list, but
any
can point to any element in the structure, we don't care about the order, where we add, etc.

Besides my main task for the project, which I have already done, we have to implement iterator in such a way, that

for(auto it = r1.begin(); it != r1.end(); ++it) // r1 is a ring
{ cout << *it << ' '; }


works properly, ie. prints whole ring.

Is it even possible? Iterator end() should point to a place, where the next element will be added, and we don't have such a point. If it's set to
any
(same as begin()), the loop will not be executed at all, and if it's set to
any->prev
, it will omit the last element.

Do you have any ideas, how can I implement this? Or am I right that it is impossible?

Answer

It's impossible: you can't identify a position in a ring that's "one past the last element", which is what end() is.

The idiomatic way of iterating over a ring is to send two iterators out in opposite directions from any point and terminate after both iterators have reached, and one of them has "processed", the same element.