Filip S Filip S - 9 months ago 71
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
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
(same as begin()), the loop will not be executed at all, and if it's set to
, 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 Source

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.