0

This is the node for a tree

class Node {
public:
   string name;
   map<string, string> attribute;
   Node* parent;
   set<Node*, customComparison> children;
};

Where customComparison in the line set<Node*, customComparison> children is a custom < operator I'm trying to define for Node* objects for use in the set data structure, that orders Node* objects according to their name data member (which is a string, using lexicographical order).

If I try to define the custom < before the class, it requires Node* as parameters and Node isn't defined yet. If I try to define the custom < after the class, set<Node*, customComparison> wont work because customComparison hasn't been defined yet.

It feels like what I want is self referential, because defining customComparison requires the Node class to be already fully defined, but defining the Node class requires customComparison in the first place. Is it impossible to do this? If there's a way, please show how thanks.

1 Answer 1

4

Old wisdom from C programming: when you are implementing two functions referencing each other recursively, it is all a matter of proper forward declarations.

This is not much different in C++: you need to make a forward declaration for class Node first, then for the customComparison class (containing an operator() ), then you can make a full declaration of Node and finally provide the implementation for customComparison::operator().

Putting it all together, this gives you:

using namespace std;

class Node;

struct customComparison {
    bool operator() (Node* a, Node* b) const;
};


class Node {
public:
    string name;
    map<string, string> attribute;
    Node* parent;
    set<Node*, customComparison> children;
};

bool customComparison::operator()(Node* a, Node* b) const { 
    return a->name < b->name; 
}

2
  • Note that even "plain old data" types can have mutual dependencies, so this does arise in C apart from functions. However, in C the forward declaration is not needed because the struct tag serves the purpose. Likewise here class Node; is not needed, one can write bool operator() (class Node* a, class Node* b) const;
    – Ben Voigt
    Sep 14, 2023 at 16:33
  • All you need is convince the compiler that there is a class named Node, and you can do anything you can do without knowing any further details. “class Node” tells the compiler. “Node” on its own doesn’t.
    – gnasher729
    Sep 14, 2023 at 21:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.