Iterator

template <typaname Key, typename Info>
class Ring {
	// doubly-linked ring with iterator
	struct Node {
		Key key;
		Info info;
		Node* next;
		Node* prev;
	};
	Node* any;

public:
	
	class Iterator {
		// this is private part of iterator class
		Node* node;
		Iterator(Node*);
	public:
		friend class Ring<Key, Info>;
	
		Iterator();
		// Iterator(const Iterator&); unnecessary
		//Iterator(Node* node) we cannot do this because Node is a public part of Ring
		// friend keeps the Node private even for Iterator

		Iterator  operator++(); // postfix increment (it++)
		Iterator& operator++(int); // prefix increment (++it)why 
		Iterator  operator--();
		Iterator& operator--(int);
		bool operator== (const Iterator other&);
		bool operator!= (const Iterator other&);
		Node operator->(); // hard to work with, advised to skip
		Info& operator*();
		Key& getKey();
		Info& getInfo(); // the same as operator*
	};
	// iterator methods
	Iterator find(const Key&, int inst = 1);
	Iterator begin();
	Iterator end();
	Iterator start(); // constructor for iterator based on a node;
}

Iterator should never do anything with the list (remove, insert etc.)
The {cpp}Ring class can have a method {cpp}removeAt(Iterator it)

It is good to use smart pointers to make the memory access for iterators much safer.

We return reference in prefix incrementation, because it is needed in example cases

++itr = jtr;
++++itr;

Without the reference, those will not work.

A problem with our class + iterator

Ring<int, string> r1;
Ring<int, string> r2;
Ring<int, string>::Iterator it;
// ...
it = r1.start();
r2.remove(itr);  // what happens now?

To prevent this situation, we should check if the iterator is currently pointing to the used object (r2 in this example).
To make it work efficiently (not by scanning the whole ring to find whether we're in the correct one), we can add the owner pointer to the iterator class

template <typename Key, typename Info>
class Ring{
// ...
public:
	class Iterator{
		Node* node;
		Iterator(Node*);
		Ring<Key, Info>* owner;
	}
}

Removing the node that iterator points to

We have to save the version of the Ring class object
The class declaration:

template <typename Key, typename info>
class Ring {
	int version;
	struct Node {/*...*/};
	Node* any;
public:
	class Iterator {
		int version;
		// ...
	}
}

If the iterator has a version of the owner that is incorrect with the version that it's operating on, the operation is not conducted.
The version of the object should change on removal - addition and swapping places won't make another iterators point to deleted data.

Inserting

{cpp}insertBefore() can be omitted by doing {cpp}insertAfter(--itr);

Info for next labs

Use owner tracking, version tracking not needed.