class (or struct) self-reference by template

Question

Is the following legal?

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

A comment to this post seems to suggest that it is not.

EDIT: This doesn't strike me as an "undefined behavior" type of scenario. The intended semantics are unambiguous. If it is an invalid usage of an incomplete type then it should be a compile-time error.

In my tests this seems to work fine (I have used both GCC and Clang -- both with -Wall -Werror -std=c++11).

Is there something in the language definition (prior to C++17) that directly or indirectly specifies this as undefined behavior, or is it just under-specified?

Keep in mind that this is very similar, structurally, to something like the following:

typedef int T;
struct tree_node;

struct tree_node
   {
   T t;
   tree_node * children;
   }

Possible dupliucate: http://stackoverflow.com/questions/31345193/how-can-an-incomplete-type-be-used-as-a-template-parameter-to-vector-here — NathanOliver, Sep 09 '15 at 19:35
The "exception for shared_ptr" cracks me up: https://stackoverflow.com/a/31347287/86967 — Brent Bradburn, Jul 13 '17 at 20:49
Worst-case scenario, you could use `shared_ptr` instead of just `tree_node`. — Brent Bradburn, Sep 01 '17 at 23:49

score 14 · Answer 1 · answered Sep 09 '15 at 19:31

14

Actually, as a result of N4371 we have (from N4527, [vector.overview], will be in C++17):

An incomplete type T may be used when instantiating vector if the allocator satisfies the allocator completeness requirements 17.6.3.5.1. T shall be complete before any member of the resulting specialization of vector is referenced.

Prior to this, vector could not be constructed with an incomplete type (which tree_node is at that point), and that would be undefined behavior.

answered Sep 09 '15 at 19:31

Barry

286,269
29
621
977

that's incredible. how do you do small object optimization with such a loose requirement ? – v.oddou May 09 '19 at 07:17
@v.oddou `std::vector` doesn't do a small buffer optimization. – Barry May 09 '19 at 12:11
It's not something we can tell for sure, "this implementation of std::vector" doesn't do it, sure. but implementation is not specified. if we start to put these weird phrasings in the spec, now the implementation becomes constrained to not do it, but by mistake rather than by explicit design. – v.oddou May 10 '19 at 04:52
@v.oddou Sure we can. `std::vector` has to support incomplete types and `swap` can't invalidate iterators. – Barry May 10 '19 at 12:19
yes but that's what I mean. It's not specifically said "small object optimization is prohibited" in the standard. It's implied from constraints set by unrelated phrasings. This seems like a bug. – v.oddou May 13 '19 at 02:36

class (or struct) self-reference by template

1 Answers1

Linked