CODEWITHSUNDEEP
c++field
flacko32
flacko32

Reputation: 13

"Field has incomplete type" question for classes that reference themselves

I'm new to C++ from Java, so apologies for the basic question. I'm trying to make just a simple Node class for a tree structure, and running into a "field has incomplete type TreeNode" error on the TreeNode children[] line. Is it illegal to have self-referential classes in c++? The code works in Java.

I tried researching the issue, but all questions I found were for more complicated issues, and I'm just trying to understand the basics right now. 

/*
 * TreeNode.h
 *
 *  Created on: Aug 16, 2019
 *      Author: dbarrett24
 */

#ifndef TREENODE_H_
#define TREENODE_H_

class TreeNode {
public:
    int value;
    TreeNode children [];
    TreeNode(int x, TreeNode kids[]);
    virtual ~TreeNode();
};

#endif /* TREENODE_H_ */

Upvotes: 0

Views: 482

Answers (3)

Peter
Peter

Reputation: 36617

Your underlying problem is that you assume C++ works like Java. And you are making that assumption in a context where C++ is emphatically different from Java.

The "incomplete type" error is because of

TreeNode children [];

since declaring an array member of a class without a dimension gives an incomplete type (an array with unknown dimension is incomplete).

If you were to supply an array dimension that is known at compile time.

TreeNode children [25];

that would be a complete type, but is still invalid within class TreeNode since it effectively means that a TreeNode object contains 25 instances of TreeNode, each of which contains 25 instances of TreeNode - which is infinitely recursive containment.

Unlike Java, which uses reference semantics by default, C++ uses value semantics. A consequence of this is that an object of type TreeNode cannot contain an instance of TreeNode (i.e. another complete object of type TreeNode) and cannot contain an array of TreeNode (i.e. a complete SET of objects of type TreeNode).

The way to handle that is by indirection - explicitly using a code construct that allows use of pointer or reference semantics. One example is

#include <vector>
class TreeNode
{
 public:
     int value;
     std:vector<TreeNode> children;
     TreeNode(int x, TreeNode kids[], std::size_t n);
     virtual ~TreeNode();
};

since a std::vector<TreeNode> actually (in effect) contains a pointer to a dynamically allocated array of TreeNode, and manages dynamic allocation and deallocation of TreeNode objects at run time.

The constructor declaration in the above

  TreeNode(int x, TreeNode kids[], std::size_t n);

works a little differently than you expect. I am adding third argument, n, to represent the number of kids being passed since there is no way in standard C++ to obtain the number of elements of an array argument. The second argument can use array syntax, but this is actually treated by the compiler as a pointer. So the above constructor declaration is actually equivalent to

  TreeNode(int x, TreeNode *kids, std::size_t n);

Either way, this constructor needs to be defined. One way would be

TreeNode::TreeNode(int x, TreeNode *kids, std::size_t n) : children(n)
{
      // presumably also do something with x

      for (std::size_t i = 0; i < n; ++i)
          children[i] = kids[i];
}

where the children(n) in the constructor initialiser list has the effect, for a std::vector, of setting the number of elements to n.

An even better way to implement the constructoror would be to use the fact that a std::vector can be initialised using a pair of iterators

TreeNode::TreeNode(int x, TreeNode *kids, std::size_t n) : children(kids, kids + n)
{
      // presumably also do something with x
}

where children(kids, kids + n) uses pointer syntax. kids is equivalent to &kids[0] (i.e. the address of the first element of a passed array) and kids + n is equivalent to &kids[n] (i.e. the address of the "one past the end" element of kids).

Upvotes: 2

Coral Kashri
Coral Kashri

Reputation: 3506

The problem is in the following class's member: TreeNode children [];. Ignoring the array syntax error in c++, TreeNode is the current class definition, and currently it's an incomplete type. You can use pointers to solve it (if you don't want to use std collections), or vector (which is one of the std collections). Consider something like this:

std::vector<TreeNode> children;

Or for future problems, in case you don't want collections (usually whenever you want just a single value):

std::shared_ptr<TreeNode> property_name;

Upvotes: 1

Anmol Jain
Anmol Jain

Reputation: 1

Your class declaration cannot have a object of self type. Though it can also have pointer to self type.

Actually what happening is, you are making an array of TreeNode which is calling TreeNode() to create new instance and that new instance of TreeNode also have TreeNode children []; which again calls TreeNode() to create this array, and this goes on and on.

Try replacing your code to:

class TreeNode {
public:
    int value;
    TreeNode *children[];
    TreeNode(int x, TreeNode kids[]);
    virtual ~TreeNode();
};

an array of pointers

Upvotes: 0

Related Questions