Pointer Syntax C++

Question

Regarding binary trees - I had seen the following code as part of the solution for a problem:

struct Node
{
    int key;
    struct Node *left, *right;
};

My question is what does "struct Node *left, *right" mean given it is defined w/in the body of the first struct Node definition. Also if this is C++ why would you use struct instead of just class/object here?

`struct` and `class` are essentially the same thing in C++. The only difference is that `struct` members are `public` by default and `class` members are `private` by default. For that reason it is common to use `class` anytime you want encapsulation, and `struct` when you merely want to gather together related public data members e.g. [`std::pair`](http://en.cppreference.com/w/cpp/utility/pair). — JBentley, Apr 11 '15 at 05:48
This has been answered before: http://stackoverflow.com/a/7729819/1236397 — James Wilkins, Apr 11 '15 at 05:50
Why couldn't you just write "Node *left, *right" instead of "struct Node *left, *right" — djfkdjfkd39939, Apr 11 '15 at 05:52
@djfkdjfkd39939: You can, as long as you're writing C++ and not C. — Ben Voigt, Apr 11 '15 at 05:54
Sorry - can you explain that a little more - i.e. what advancement does C++ have that makes it not ok to do that for C? — djfkdjfkd39939, Apr 11 '15 at 05:57
@djfkdjfkd39939 nothing "advanced", really; just a different (but similar) language. C++ is more of a high level language; think of C as one step up from machine code. You have to be pretty specific with C; C++ allows you to do a lot more at the expense of simplicity and understandability. — Qix - MONICA WAS MISTREATED, Apr 11 '15 at 05:59
Thanks! Last question - I could look this up but I'd just get your take on it. If Javascript doesn't have pointers, how would they handle implementing a binary search tree (or something like the above snippet of code)? — djfkdjfkd39939, Apr 11 '15 at 06:02
@djfkdjfkd39939 with pointers in the background. In JS, pointers are not exposed in the language, but object have reference semantics meaning that a practical implementation will use pointers in the background. (JavaScript engines are almost universally written in C or C++.) — The Paramagnetic Croissant, Apr 11 '15 at 06:06
@djfkdjfkd39939 as to your question "why do we need the struct keyword in C but not in C++": it's a purely syntactic thing. C++'s grammar allows the omission of struct, C's doesn't. It has nothing to do with how "advanced" each language is. (C is just as "advanced" as C++. It takes a lifetime to master. It's just not as complex as C++.) — The Paramagnetic Croissant, Apr 11 '15 at 06:08

Qix - MONICA WAS MISTREATED · Accepted Answer · 2015-04-11T06:06:11.717

2

In C++ (and especially C), types are usually always represented by their construct.

For instance,

enum Foo { ... };
void doSomethingWithAFoo(enum Foo f);

struct Bar { ... };
void doSomethingWithABar(struct Bar bar);

While this is required in C, it is not in C++. In C, it is achieved by using a typedef.

typedef struct { ... } Foo; // Can now be referenced with just `Foo`

However, there is a particular part of the spec that states that struct types cannot have instance of themselves inside of them (more specifically it states types cannot refer to themselves before they're fully declared).

Except in pointer form. This is because pointers are known sizes at the beginning of compilation, whereas structures are only known after they are declared.

Since structs pre-date C++ (only by a little) and have been present since ANSI C (C89) and before in most major compilers, they are also present in C++ (since ANSI C can be compiled gracefully in compliant C++ compilers).

However, C++ adds the concept of classes, which don't exist in C. As others have mentioned, classes and structs are similar in that they both holds members. In C++, structs can have methods just like classes - obviously this is not the case in C.

The only difference as far as I'm aware is the visibility; structs default to public and classes default to private. C does not have the notion of visibility.

edited Apr 11 '15 at 06:06

answered Apr 11 '15 at 05:49

Qix - MONICA WAS MISTREATED

14,451
16
82
145

I explain that; you're more than likely working with code that is actually C. It just happens to work with your C++ compiler. – Qix - MONICA WAS MISTREATED Apr 11 '15 at 05:53
Interesting, so it is in pointer form bc it is of type struct and its recursive (i.e. "struct Node *left, *right" instead of "struct Node left, right")? – djfkdjfkd39939 Apr 11 '15 at 05:54
Correct. Think about it; if the struct had to allocate space for itself, and then a copy of itself, those copies of themselves would also have to allocate space for more copies, and so on. It'd be never ending. – Qix - MONICA WAS MISTREATED Apr 11 '15 at 05:55
1

@djfkdjfkd39939: If you wrote `Node left, right;` (without the pointers), then each `Node` would contain two Nodes. How much memory, then, would a Node require? – Ben Voigt Apr 11 '15 at 05:56
C structs have existed since the 1970s - with K&R C. It is not just "certain compilers" that supported them. – Peter Apr 11 '15 at 06:04
@Peter I know about friends that have talked about unofficial C compilers before ANSI standards were in place that didn't support structs and had other mechanisms for structured data. I'll clarify wording. – Qix - MONICA WAS MISTREATED Apr 11 '15 at 06:05
If you check, you'll find those compilers were of subsets of C. K&R (Kernighan and Ritchie) designed the original C with struct types. That didn't stop some vendors producing stripped down versions that only implemented a subset of the language. Similarly, there are some compilers now that only support a subset of ISO C. – Peter Apr 11 '15 at 06:10
@Peter I know who K&R are and what they did ;) Subsets of C or not, they were still considered C compilers in the day. – Qix - MONICA WAS MISTREATED Apr 11 '15 at 06:11

score 1 · Answer 2 · answered Apr 11 '15 at 05:43

1

Means exactly what it looks like. A recursive declaration just means a Node struct had two fields that are pointers to other Nodes.

I've read that the main difference between structs and classes in C++ is the default permissions (structs are all public by default). Slightly simpler, especially since inheriting is unlikely.

answered Apr 11 '15 at 05:43

Will

4,299
5
32
50

Why couldn't you just write "Node *left, *right" instead of "struct Node *left, *right"? – djfkdjfkd39939 Apr 11 '15 at 05:52

score 0 · Answer 3 · answered Apr 11 '15 at 05:58

The meaning of struct Node *left, *right; within the definition of struct Node is that each instance of struct Node contains members (left and right) that point to other struct Nodes.

It is the programmer's responsibility to ensure that, whenever a struct Node is created, that those members are initialised appropriately. They may be set to NULL (indicating they don't point at any object) or to the address of another struct Node.

In C++, initialisation of left and right will often be done in a constructor. C doesn't have that feature so, every time some C code creates a struct Node, it will typically have to explicitly initialise the left and right members.

The code you have shown is really C, although it will be accepted by a C++ compiler. C++ allows the declaration struct Node *left, *right; to omit the struct keyword. C does not.

In C++, a struct and a class are the same thing - the difference is accessibility of members: C++ struct members are public and class members are private by default. C++ structs (and classes) are able to do numerous other things that C structs cannot.

Pointer Syntax C++

3 Answers3