Filip S Filip S - 1 year ago 91
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 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download