55

I'm trying to speed up a python routine by writing it in C++, then using it using ctypes or cython.

I'm brand new to c++. I'm using Microsoft Visual C++ Express as it's free.

I plan to implement an expression tree, and a method to evaluate it in postfix order.

The problem I run into right away is:

class Node {
    char *cargo;
    Node left;
    Node right;
};

I can't declare left or right as Node types.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
Peter Stewart
  • 2,857
  • 6
  • 28
  • 30
  • 2
    "_I can't declare left or right as Node types._" This should include an explanation of why, with verbatim quotes of any errors received. Presumably your compiler complained about something like `Node` being an incomplete type at that point in time. – underscore_d Nov 21 '19 at 13:34

4 Answers4

105

No, because the object would be infinitely large (because every Node has as members two other Node objects, which each have as members two other Node objects, which each... well, you get the point).

You can, however, have a pointer to the class type as a member variable:

class Node {
    char *cargo;
    Node* left;   // I'm not a Node; I'm just a pointer to a Node
    Node* right;  // Same here
};
James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • 1
    In this case a bare pointer is the proper and intuitive choice. It is worth mentioning that holding myself as a member can be using other choices, such as: `reference`, `std::unique_ptr`, `std::shared_ptr` or `std::weak_ptr`, see also: https://stackoverflow.com/questions/63365537/c-instance-of-same-class/63365597#63365597 – Amir Kirsh Aug 12 '20 at 09:15
57

Just for completeness, note that a class can contain a static instance of itself:

class A
{
    static A a;
};

This is because static members are not actually stored in the class instances, so there is no recursion.

Felipe
  • 571
  • 4
  • 2
  • This has turned my head upside down for a bit, so I would add something: in this case, each instance of the class 'A' will only store a pointer to a space allocated in static memory for the particular 'a' instance. So the 'a' instance also have a pointer, pointing to itself infinitely: `A* someA = new A;` `someA->.a.a.a...etc.` (supposing 'a' is a public attribut) and that is why memory used in finite. – hymced Nov 29 '17 at 13:45
  • 3
    @hymced: No, none of the instances of `A` contains a pointer, certainly nothing pointing to the static member. `->` and `.` will get you that object thanks to name lookup rules, not because of any memory layout. – Lightness Races in Orbit Jul 19 '19 at 16:08
  • @Lightness-Races-in-Orbit you are right, there are no pointers in the above example. What I meant is that the used memory is finite, not because the static member is stored outside of the class instance, but rather because this particular static member is the same for any class instance. It is also because the ´a´ instance only contains itself and nothing else. Add a simple (non-static) int member in the mix, you are out of memory, even with a static class member. – hymced Jul 20 '19 at 19:17
  • @hymced That is simply not true. Why do you think adding a non-`static` `int` member to `A` would cause the computer to run out of memory? – Lightness Races in Orbit Jul 20 '19 at 19:32
  • Again, I was wrong : 'A' would have an int member (not in static memory) different from 'a' (in static memory), but the int member of 'a' would be the same than 'a.a' (since 'a.a' IS 'a'), same than 'a.a.a', etc. So used memory is finite. – hymced Jul 21 '19 at 20:21
  • @hymced With static members the class is simply used as a namespace. The connection of the static member to the class is purely syntactical (including potential access restrictions). To the linker etc. it is like any global variable and can be used thus (pass it to C functions etc.) – Peter - Reinstate Monica Nov 21 '19 at 13:36
  • This should have been the right accepted answer. The static keyword seems clever. – Jayanth Jun 27 '23 at 16:34
12

No, but it can have a reference or a pointer to itself:

class Node
{
    Node *pnode;
    Node &rnode;
};
R Samuel Klatchko
  • 74,869
  • 16
  • 134
  • 187
  • 5
    References don't really work in this case because they aren't allowed to be null, and you need null endings or the graph would be infinite. – Blindy Apr 24 '10 at 21:17
  • 4
    You could create a dummy node to take the pace of NULL. However, this doesn't work well because references can't be reassigned to something else, and modification to any link would require reconstructing all nodes up to the root. – Potatoswatter Apr 24 '10 at 21:32
  • 1
    @Blindy: You could also set the node reference to `*this` instead of NULL. – MSalters Apr 26 '10 at 12:38
  • @Blindy, @All: Yes. Like I say, I'm a real beginner. I've been having a very difficult time trying to put this together. – Peter Stewart Apr 26 '10 at 23:10
  • @Blindy but there is `std::optional< std::reference_wrapper >`! Don't laugh. It's easier to throw if 'null' and less prone to accidental pointer arithmetic and suchlike. – underscore_d Nov 21 '19 at 13:32
3

Use a pointer, & better initialized:

class Node {
    char * cargo = nullptr;
    Node * left = nullptr;
    Node * right = nullptr;
};

Modern C++

It is a better practice to use smart-pointers (unique_ptr, shared_ptr, etc.), instead of memory allocations by 'new':

#include <string>
#include <memory> // For 'std::unique_ptr' 

class Node {
public:
    std::string cargo;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};

int main()
{
    auto bt = std::make_unique<Node>();

    (*bt).cargo = "Coffee";
    (*bt).left = std::make_unique<Node>();
}
Amit G.
  • 2,546
  • 2
  • 22
  • 30