Creating a tree using std::array

Question

The code at the bottom generates the following compile-time error. The errors goes away if I use std::vector<Node> or std::array<unique_ptr<Node>, 3>. Can someone please explain what this is about?

In file included from main.cpp:1:0: /usr/include/c++/4.9/array: In instantiation of ‘struct std::array’: main.cpp:9:23:
required from here /usr/include/c++/4.9/array:97:56: error: ‘std::array<_Tp, _Nm>::_M_elems’ has incomplete type typename _AT_Type::_Type _M_elems; ^ main.cpp:3:7: error: forward declaration of ‘class Node’ class Node

#include <array>

class Node
{
public:
  Node(Node* parent, int x) : parent_(parent), x_(x) {}
  Node* parent_;
  int x_;
  std::array<Node, 3> children_; // ERROR
};

@LightnessRacesinOrbit shared_ptr or did you have some other wrongness in mind? — Steve M
@SteveM: Containers of pointers are reserved for special cases. You don't want them. — Lightness Races in Orbit
Just to be clear: std::vector<Node> is not a viable option, despite some answers suggesting that. The reasons for this unfortunate fact are technical and tedious. See Why C++ containers don't allow incomplete types?. Also bear in mind that simply using a container of (smart) pointers has deep implications on the semantics of the class, so it is not a drop-in replacement for a real container with value semantics (e.g. boost::container::vector.) — juanchopanza

Mark Mark · Accepted Answer · 2014-12-30T06:46:04

As noted in the other answers, the fundamental problem here is that you are using a type inside the definition of that type.

The reason this is a problem is because the compiler must know how big a type is in order for you to have it as a data member. Because you have not finished declaring the Node type, the compiler does not know how much space it should use for a data member of type Node.

The reason why a pointer does work is because all pointers are the same size in memory, what varies is the size of what they point to, which you only need to know when you dereference the pointer.

Accordingly, using a std::array<Node, 3> inside of your Node definition does not work because std::array puts its memory in the same place as it was declared (in a function, that'd be the stack, in an object, that'd be in the object itself). To figure out how much memory is needed, it needs to know the size of a Node, and there's the issue.

Using a std::unique_ptr<Node> is fine for the same reason a normal pointer is: a pointer is always the same size.

Using a std::vector<Node> is fine (in principle, but not necessarily in practice) for the same reasons again, but perhaps less obviously so: you can think of vector as having 2 data members, a pointer to an array of Nodes and a size. The key part is the pointer. Because only the "handle" to the vector lives inside a Node's memory and the data is allocated elsewhere, this is a perfectly fine way to store things.

Probably the best way to express your intent given the constraints of the language is: std::array<std::unique_ptr<Node>, 3>

You still have a fixed number of children, automatic memory management, and no longer run into the issue of not knowing how big that data member's storage footprint is.

For what it's worth, this same reasoning is what enables the pimpl idiom.

Creating a tree using std::array

4 Answers