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
};
Improve this question
6
  • 1
    I think you want array<Node*, 3> Commented Dec 30, 2014 at 6:20
  • 1
    I think you don't want that. Commented Dec 30, 2014 at 6:20
  • @LightnessRacesinOrbit shared_ptr or did you have some other wrongness in mind? Commented Dec 30, 2014 at 6:28
  • 1
    @SteveM: Containers of pointers are reserved for special cases. You don't want them. Commented Dec 30, 2014 at 6:29
  • 1
    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.) Commented Dec 30, 2014 at 7:50

4 Answers 4

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Using std::vector<Node> is not fine in principle (see links in comments to the other answers.)
@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".
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 - 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.
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.
|
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.

Improve this answer

3 Comments

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<Node> or array<unique_ptr<Node>,3>?
@anon: Those have a dynamic size. None is a valid length. Arrays are different.
@anon You can't have a vector either, but the reasons are rather technical. See Why C++ containers don't allow incomplete types? (sic).
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.

Improve this answer

1 Comment

vector<Node> would be undefined behaviour. std::vector needs a complete type. See stackoverflow.com/questions/18672135/….
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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.