C++ recursive type definition

Question

Why is the following code valid? The struct test contains a vector of test, so that the following code compiles (IDEOne):

#include <iostream>
#include <vector>

using namespace std;

struct test {
    vector<test> a;
};

int main() {
    // your code goes here
    test t;
    if (t.a.size() > 0)
        return -1;
    else if (t.a[0].a[0].a.size() > 0)
        return 1;
    return 0;
}

How does the compiler handle the struct so that is is possible to test for t.a[0].a[0].a.size()? Is there a limit on how often I could repeat the .a[0]?

Edit: This questions has an answer that claims this is undefined behaviour: Are C++ recursive type definitions possible, in particular can I put a vector<T> within the definition of T?

=> This is confusing

=> perhaps my question is a duplicate

The default constructor for `std::vector` does not require the template argument to be a fully qualified name. — paddy, Mar 06 '17 at 11:54
To push things farther, `struct WTF : std::vector {};` I use it to build [Peano's natural numbers](https://en.wikipedia.org/wiki/Peano_axioms) :D — YSC, Mar 06 '17 at 11:58
(hint : `operator++()` is just `{push_back(*this); return *this;}`) — YSC, Mar 06 '17 at 11:59

score 3 · Accepted Answer · answered Mar 06 '17 at 12:06

This boils down to vector<T> not needing to know the size a value of type T occupies, which allows T to be an incomplete type. Essentially, the mechanism in play here is the same as in this declaration:

struct test {
    test* start;
    test* end;
};

The compiler has no problem declaring pointers to any type, as long as you promise to define it at some later point.

This behavior changes based on the template: you have no problem defining test with a vector<T>, but an array<T,Size> or even a pair<T,K> would be problematic:

struct broken1 {
    array<broken1,3> a; // Does not compile
};
struct broken2 {
    pair<broken2,broken2> p; // Does not compile
};

C++ recursive type definition

1 Answers1