5

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
};
Agrim Pathak
  • 3,047
  • 4
  • 27
  • 43
  • 1
    I think you want array – Steve M Dec 30 '14 at 06:20
  • 1
    I think you don't want that. – Lightness Races in Orbit Dec 30 '14 at 06:20
  • @LightnessRacesinOrbit shared_ptr or did you have some other wrongness in mind? – Steve M Dec 30 '14 at 06:28
  • 1
    @SteveM: Containers of pointers are reserved for special cases. You don't want them. – Lightness Races in Orbit Dec 30 '14 at 06:29
  • 1
    Just to be clear: `std::vector` **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?***](http://stackoverflow.com/questions/18672135/why-c-containers-dont-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 Dec 30 '14 at 07:50
  • @juanchopanza This just gave me a revelation as to why std library code looks the way it does – jfh May 15 '20 at 17:37

4 Answers4

4

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.

Mark
  • 3,806
  • 3
  • 21
  • 32
  • Using `std::vector` is *not* fine in principle (see links in comments to the other answers.) – juanchopanza Dec 30 '14 at 07:04
  • @juanchopanza - If you read the article you continue to link, it does actually quite clearly state that it is a non-issue with `vector` (as opposed to std::map). Even though the standard may disallow such an implementation, in principle there is no actual problem with it; indeed the "obvious implementation" does not require a complete type. Nevertheless, my statements go to why an implementation *might* compile; let's not get hung up over the meaning of "in principle". – Mark Dec 30 '14 at 07:16
  • 1
    Still, it is not fine in principle, unless you consider writing code with UB "fine". There are implementations that actually reject the code, but they are free to fail silently too. It shouldn't pass any half-serious code review. – juanchopanza Dec 30 '14 at 07:17
  • @juanchopanza - We are evidently bickering over the meaning of "in principle". I refuse to participate beyond this. It is good that you posted technical information, I merely dispute the context in which you presented it. – Mark Dec 30 '14 at 07:20
  • I am just pointing out that a vector of an incomplete type is undefined behaviour. You seem to suggest it is fine. My contention is that it is never fine to write code with undefined behaviour. I didn't think that would be a controversial point. – juanchopanza Dec 30 '14 at 07:56
  • @Mark Undefined behavior is not fine neither in "principle" or "practice". Your response also seems unnecessarily hostile for a valid criticism. –  Dec 30 '14 at 08:19
  • The misinterpretation specifically relates to the framing of the problem. The contention is not whether it is undefined behavior according to the standard. It is whether or not it is possible to implement a `vector`, in principle, that does not have that restriction. It *is* possible, and indeed, the libstdc++ version *does*. It may not be standards compliant, but that is only because the restriction is baseless and arbitrary for `vector`, as opposed to containers like `map`. I agree that the way I carried myself was sub-standard, apologies. – Mark Dec 30 '14 at 08:33
  • 1
    FFS you are basically saying it is fine to have a vector of a type as a data member of that type. **It is undefined behaviour**. It does not matter at all whether it is possible to implement a vector type for which this is not UB, and OP is not asking that. Your answer is dangerously misleading. – juanchopanza Dec 30 '14 at 14:13
3

A Node obviously cannot contain three Nodes.
This would be a recursive relationship which could only end under one of two conditions:

  1. the end of the universe
  2. she cheats on you

Your choice. IMO neither are optimal.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • 2
    Can you please elaborate in your answer on why can't you have a recursive relationship? Is it because Node isn't fully defined at line 9? If so, why can I have a vector or array,3>? – Agrim Pathak Dec 30 '14 at 06:27
  • @anon: Those have a dynamic size. None is a valid length. Arrays are different. – Lightness Races in Orbit Dec 30 '14 at 06:28
  • 3
    @anon You can't have a vector either, but the reasons are rather technical. See [*Why C++ containers don't allow incomplete types?* (sic)](http://stackoverflow.com/questions/18672135/why-c-containers-dont-allow-incomplete-types). – juanchopanza Dec 30 '14 at 06:44
1

You are trying to declare that Node contains a member which holds 3 Nodes. That is simply not possible, as it is unbounded recursion.

std::vector< Node > works because vectors are initially empty and added to dynamically.

std::array< std::unique_ptr< Node >, 3> works because this type of array only contains pointers to Node objects, and not the objects themselves.

user4404422
  • 27
  • 1
  • 2
    `vector` would be undefined behaviour. `std::vector` needs a complete type. See http://stackoverflow.com/questions/18672135/why-c-containers-dont-allow-incomplete-types. – juanchopanza Dec 30 '14 at 06:41
0

In my case, I only had the declaration of the class type ahead of using it in an array declaration. C++ was expecting the definition.

Anandaraja Ravi
  • 79
  • 4