How do I declare a vector of a struct within that same struct?

Question

I am trying to create a struct that includes a vector with type being that same struct. However, when I build, errors that indicate I am missing a ';' before '>' appear. I am not sure if the compiler is even recognizing that the vector as a thing :/ and I have already included in my code. Here is what I have so far:

#include <vector>

typedef struct tnode
{
    int data;
    vector<tnode> children;
    GLfloat x; //x coordinate of node 
    GLfloat y; //y coordinate of node
} tnode;

Any help would be greatly appreciated!!

You surely mean `std::vector`? – celtschk Jun 26 '13 at 18:46 — celtschk, Jun 26 '13 at 18:46

interjay · Accepted Answer · 2013-06-26T17:13:51.357

6

Your code is invoking undefined behavior because standard containers such as vector cannot contain incomplete types, and tnode is an incomplete type within the struct definition. According to the C++11 standard, 17.6.4.8p2:

the effects are undefined in the following cases: [...] if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

The Boost.Container library provides alternative containers (including vector) which can contain incomplete types. Recursive data types such as the one you want are given as a use case of this.

The following would work with Boost.Container:

#include <boost/container/vector.hpp>
struct tnode
{
    int data;

    //tnode is an incomplete type here, but that's allowed with Boost.Container
    boost::container::vector<tnode> children;

    GLfloat x; //x coordinate of node 
    GLfloat y; //y coordinate of node
};

edited Jun 26 '13 at 17:13

answered Jun 26 '13 at 16:36

interjay

107,303
21
270
254

2

@wilsonmichaelpatrick It’s trivial. In fact, a naive vector implementation allows this. The standard is over-cautious here and gives implementors more leeway than necessary. It’s a bad restriction. – Konrad Rudolph Jun 26 '13 at 17:41
1

@wilsonmichaelpatrick: The reason it can be done is that the `vector`'s member functions won't be instantiated until they are needed, and at that point `tnode` will be a complete type. – interjay Jun 26 '13 at 18:06
@interjay It gives me a fatal error when I include boost/container/vector.hpp. C1083 (not sure if that helps). Apparently there is 'no such file or directory.' – red Jun 28 '13 at 18:14
I also added "using namespace boost::container;" but that did not seem to help anything. I'm very very new to C++, so if there was something obvious that I was also supposed to add, then I missed it. – red Jun 28 '13 at 18:17
@red Boost is a commonly-used additional library that you need to install, not part of the standard libraries. You can download it from boost.org. After installing you need to setup your include directories, see instructions at http://www.boost.org/doc/libs/1_53_0/more/getting_started/windows.html or http://stackoverflow.com/questions/2629421/how-to-use-boost-in-visual-studio-2010. – interjay Jun 28 '13 at 19:00

score 3 · Answer 2 · edited May 23 '17 at 10:25

3

What you have is not standards compliant (thanks to @jonathanwakely for confirming that). So it is undefined behaviour, even if it compiles on some popular platforms.

The boost container library has some standard library-like containers that do support this, so you could in principle modify your struct to use one of these:

#include <boost/container/vector.hpp>
struct tnode
{
    int data;
    boost::container::vector<tnode> children;
    GLfloat x; //x coordinate of node 
    GLfloat y; //y coordinate of node
};

edited May 23 '17 at 10:25

Community

1
1

answered Jun 26 '13 at 16:27

juanchopanza

223,364
34
402
480

1

Does C++ now allow incomplete types as template arguments for containers? I remember in C++03 this would be illegal. (Just want to verify, it is the right language choice if it is indeed allowed.) – GManNickG Jun 26 '13 at 16:31
@GManNickG I am now pretty convinced it is not standards compliant. Thanks for pointing this out! – juanchopanza Jun 26 '13 at 16:40
2

It doesn't allow it, it's undefined behaviour to instantiate any `std` template with an incomplete type, unless specified otherwise (it is explicitly allowed for `unique_ptr` and `shared_ptr`) – Jonathan Wakely Jun 26 '13 at 16:43
1

@JonathanWakely: Thanks for confirming. Do you know if this issue was brought up? I'd imagine I'm not the only one who thinks it should be allowed. – GManNickG Jun 26 '13 at 17:06
1

@GManNickG According to [Matthew H. Austern](http://www.drdobbs.com/the-standard-librarian-containers-of-inc/184403814) it was discussed before the first standard. However, take the article with a grain of salt, it incorrectly claims that implementing a `std::map` which allows incomplete types would be hard/impossible when in reality it’s neither. – Konrad Rudolph Jun 26 '13 at 17:45
@KonradRudolph: Hm. Well now that Boost does it perhaps the next revision to the standard library can adopt this (as tends to be the case). – GManNickG Jun 26 '13 at 18:47
@GManNickG, AFAIK noone has proposed changing that rule, either in general (which I would object to) or specifically for containers (which _might_ be feasible). GCC's unordered containers currently can't be instantiated with incomplete types, although that's temporary and I'm fixing it for a future release. – Jonathan Wakely Jun 27 '13 at 10:36

How do I declare a vector of a struct within that same struct?

2 Answers2