How to define a recursive type?

Question

I want to have a list. An entry in the list would store a value as well as an iterator to another entry in the list. How do I define this type? It'd be something like this, but syntactically correct.

typedef list<pair<int, MyList::const_iterator>> MyList;

Answer 1

Let's turn the problem inside-out with a sprinkle of user-defined types to break the declarations' recursion :

struct Node {
    int _value;
    std::list<Node>::const_iterator _next;
};

If you want to use a typedef, well you can :

struct Node;
typedef std::list<Node> NodeList;

struct Node {
    int _value;
    NodeList::const_iterator _next;
};

Edit: As T.C. reminded me, instantiating standard containers with incomplete types may be Undefined Behaviour (some standard library implementations do guarantee it's not). So, let's postpone all of it to a later point.

Edit: Well that doesn't help either. So, verify that your std::list implementation supports incomplete types (or trust it to do so, it often works to be honest), or use Boost::containers.

template <class = void>
struct Node_ {
    int _value;
    typename std::list<Node_>::const_iterator _next;
};

typedef Node_<> Node;

Answer 2

Not only will iterators in a list not be invalidated by other elements being inserted or deleted, but the elements those iterators point to will also remain unchanged. Therefore we can do:

struct Element {
  int first;
  Element* second;
};

typedef list<Element> MyList;

This is quite similar to what you asked for, but second is a pointer rather than an iterator. If you really need it to be an iterator, we can switch out std::list<> for boost::intrusive::list<> (or a homegrown intrusive list if you can't use Boost). Then, the value_type (i.e. Element) would actually contain the prev/next pointers, and you could use that as an iterator. In Boost, that's called iterator_to(), explained here: http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/obtaining_iterators_from_values.html