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;

Let's work backwards, I think we might have an XY problem. What do you want to do? Why do you need two methods of walking a linked list? Will a graph do instead? — OmnipotentEntity, Aug 29 '14 at 07:47
Note that by storing just an iterator, you can't delete the pointed node (you also need its list for that). And deleting it from somewhere else will transparently invalidate said iterator. Did you account for that ? — Quentin, Aug 29 '14 at 07:49
You're saying to compiler to "find" MyList::const_iterator BEFORE defyinig MyList. Impossible. — Luca Davanzo, Aug 29 '14 at 07:51
So after resolving the typedef what specific type would it be? `list>::const_iterator>>` ? — Kos, Aug 29 '14 at 07:56
@Jarod42 That's no problem (see [CRTP](http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern)) — Quentin, Aug 29 '14 at 07:58
@PiotrS. Just an example of an "infinite template type recursion depth". That is to say, although it *is* indeed infinite, there's no problem until you try to walk it all. — Quentin, Aug 29 '14 at 08:01
m2c, this is not a nice design, if you wanted to be smart about life times of objects, you are better off using something that reflects that. For example, the `const_iterator` above can only be used to access the element, but you have no guarantee about it's lifetime (you can't do anything else with that iterator - without knowing which instance of a list it came from..) I suggest you look at `shared_ptr<>`, `weak_ptr<>` pairs which will allow you to be certain of lifetimes of objects (and across lists.) It may seem a little heavy weight, but I'd imagine it's performant enough... — Nim, Aug 29 '14 at 08:13
@Quentin: CRTP doesn't have infinite template type depth. but OP's type has, see (partial) Kos's expansion of the OP type. — Jarod42, Aug 29 '14 at 08:55
@Jarod42 I forgot for a moment that template parameters weren't exported in the instanciated template's scope. But for example, if you do `class A{typedef A T;};`, you can walk the chain of typedefs indefinitely. But the chain itself is not infinite at all, it's just a cycle. Another example is a circular linked list. — Quentin, Aug 29 '14 at 09:01
This is syntactically correct, but not semantically correct. — M.M, Aug 29 '14 at 11:42

Quentin · Answer 1 · 2014-08-29T10:52:50.350

8

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;

edited Aug 29 '14 at 10:52

answered Aug 29 '14 at 07:57

Quentin

62,093
7
131
191

1

This is the answer I wanted to come up with, but didn't. :) Well done. – John Zwinck Aug 29 '14 at 08:01
5

Instantiating `std::list` with an incomplete type (like `Node` in your example) is UB, though in practice you can probably get away with it. – T.C. Aug 29 '14 at 08:05
`typedef` does not instantiate `std::list`. By the time it is actually instantiated, Node will have been fully defined. Edit: I'll do some research about the member though. – Quentin Aug 29 '14 at 08:09
1

@Quentin `std::list::const_iterator` (or the equivalent) instantiates it, and `Node` does not become complete until the closing brace of its definition. – T.C. Aug 29 '14 at 08:10
@T.C. Information is hard to find (or I'm really bad at googling), but what do you think of that third snippet ? – Quentin Aug 29 '14 at 08:21
2

@Quentin It's still incomplete. You can [see this](http://goo.gl/e3EWqM) by writing a simple type completeness checker. I'd simply use one of the containers in Boost.Containers, which [are guaranteed to work with incomplete types](http://www.boost.org/doc/libs/1_56_0/doc/html/container/main_features.html#container.main_features.containers_of_incomplete_types). – T.C. Aug 29 '14 at 08:28
@T.C. It's of course incomplete inside its own declaration, but if I understood template instantiation rules correctly, the first use of a Node will instantiate all types at once. Won't that work ? Edit : as always, Boost nukes the problem. I really need to start using it. – Quentin Aug 29 '14 at 08:33
@Quentin [No](http://goo.gl/DNpnpn). Think of it this way - otherwise you'd be allowed to write `template struct B { T t; }; template struct A { B b; }; A<> something;` and get infinite recursion. – T.C. Aug 29 '14 at 08:42
(Curse that chatroom link) Makes sense. Well, I give up. The final answer will be the familiar "check your lib's documentation, trust your luck or use Boost". – Quentin Aug 29 '14 at 08:44
Could you perhaps define 'UB' rather than assuming everyone knows what this acronym stands for? – Pharap Aug 29 '14 at 10:51
1

@Pharap this should be better, I forgot. I'm not including a lesson on UB everytime I mention it ghough ;) – Quentin Aug 29 '14 at 10:54
1

@Quentin Thank you, 'Undefined Behaviour' is much more understandable. Laziness may be one of the three virtues, but that acronym is incredibly lazy. – Pharap Aug 29 '14 at 10:59
@Quentin Since C++17, some standard container support incomplete type: [Minimal Incomplete Type Support For Container](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4510.html). Maybe you could update your answer. – Oliv Jan 18 '18 at 10:18

score 1 · Answer 2 · answered Aug 29 '14 at 07:56

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

The problem with `std::list` is that you cannot go from a pointer to iterator. Whereas you can do that with `boost::multi_index::iterator_to`. — Maxim Egorushkin, Aug 29 '14 at 08:47
@MaximYegorushkin: yes, I explained that quite explicitly in my answer. Though I would use `intrusive` rather than `multi_index` in this case. — John Zwinck, Aug 29 '14 at 09:13

score 0 · Answer 3 · answered Aug 29 '14 at 07:58

0

You can do a trick like this, if you want:

typedef list<pair<int, void*> > MyList;
typedef list<pair<int, void*> >::const_iterator MyListIterator;

int main() {
    MyList l;
    MyListIterator it;
    pair<int, void*> p(2, &it);
    l.push_back(p);
}

By the way, I prefer John Zwinck's solution.

answered Aug 29 '14 at 07:58

Luca Davanzo

21,000
15
120
146

3

`l` doesn't own `it`, that's very unsafe. – Marc Glisse Aug 29 '14 at 08:00

score 0 · Answer 4 · answered Aug 29 '14 at 08:44

You can achieve that by forward declaring your element.

#include <list>

struct Element;
typedef std::list<Element> ElementList;

struct Element
{
    int value;
    ElementList::iterator element;
};

int main() {
    ElementList l;
    l.push_back({0, l.end()});
    l.push_back({1, l.begin()});
}

score 0 · Answer 5 · answered Aug 29 '14 at 21:19

0

Use a boost::any, or equivalent, to store the iterator. As iterators tend to be small, the small object optimization will kick in, and the overhead will be low.

answered Aug 29 '14 at 21:19

Yakk - Adam Nevraumont

262,606
27
330
524

How to define a recursive type?

5 Answers5

Linked