0

When we make a structure for let's say a tree or a linked list, something of this nature:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

What is the type for queue to store nodes of the structure? I thought it was a pointer to the struct. 

std::queue<TreeNode*> q;

But if I try to initialize multiple nodes like this:

TreeNode* l = nullptr, r = nullptr;

It doesn't work and you have to do 

TreeNode *l = nullptr, TreeNode *r = nullptr;

Can someone help me understand this a little better?

edit: After reading this answer Declaring multiple object pointers on one line causes compiler error What I'm understanding is that: In both C and C++, the * binds to the declarator, not the type specifier. In both languages, declarations are based on the types of expressions, not objects.

Then how is the queue declared the way it is?

Xgh05t
  • 230
  • 2
  • 11
  • What is `queue`? Is it `std::queue` you're using, or some custom one you haven't shown us (if so, why)? – John Zwinck Feb 07 '20 at 11:34
  • The second to last declares a `TreeNode *` and a `TreeNode` (the latter of which is thoroughly confusing the compiler when you initialize it with `nullptr`). Clearly you received an error that will probably tell you as much. "It doesn't work" is nebulous. You should include the *verbatim* error message you received, and what in particular about it you didn't understand. And, lets be clear `TreeNode *l = nullptr, TreeNode *r = nullptr;` won't work either; that should be `TreeNode *l = nullptr; TreeNode *r = nullptr;`. Or `TreeNode *l = nullptr, *r = nullptr;` – WhozCraig Feb 07 '20 at 11:35
  • 2
    `TreeNode* l = nullptr, r = nullptr;` doesn't work because https://stackoverflow.com/questions/13618282/declaring-multiple-object-pointers-on-one-line-causes-compiler-error – John Zwinck Feb 07 '20 at 11:35
  • @WhozCraig I get a type mismatch when assigning it values of type ```TreeNode*``` later on in the program with the words 'invalid conversion from nullptr to non scalar type TreeNode' and I also get invalid conversion from TreeNode* to int, if I assign it the root instead of nullptr in the beginning and change it to a TreeNode* later. – Xgh05t Feb 07 '20 at 11:42
  • [That all belongs in your question](https://stackoverflow.com/posts/60112613/edit), and it isn't clear what about that error message you're not understanding. – WhozCraig Feb 07 '20 at 11:43
  • Oh yea that is a typo my bad, I don't do it like that actually – Xgh05t Feb 07 '20 at 11:45
  • Yes, I already knew the right way to declare, I was more confused about what is going on rather than how to fix it, my main question after reading the answer John Zwinck provided is what type does the queue get? – Xgh05t Feb 07 '20 at 11:48
  • "Struct TreeNode" it's better to use struct – QuentinUK Feb 07 '20 at 11:51
  • Good eye with that, but my main question is regarding what type the queue will get, not small typos I made while typing here! – Xgh05t Feb 07 '20 at 11:54
  • The queue is of ```TreeNode*```s. Define ```using TreeNodePtr = TreeNode *;``` Then you can use ```TreeNodePtr l, r``` and ```std::queue< TreeNodePtr>``` – QuentinUK Feb 07 '20 at 12:01
  • it is unclear why you think the type of the queue `std::queue q;` has something to do with your problem. There is no queue in `TreeNode *l = nullptr, TreeNode *r = nullptr;` – 463035818_is_not_an_ai Feb 07 '20 at 12:18

2 Answers2

3

The second variable r is not declared as a pointer, it should be:

TreeNode *l = nullptr, *r = nullptr;

TreeNode* is a type, like a char or int, but if you delclare it in the same line you must use the * indirection operator so that the compiler knows that the specific variable is a pointer to object, not an object. When you declare it in a deque or a vector or somenthing like that, you must also be able to tell if the tpyes admitted are pointers to object or objects, hence the declaration TreeNode* inside angular brackets.

If you think about it, it makes sense semantically speaking.

anastaciu
  • 23,467
  • 7
  • 28
  • 53
  • That was just a typo, my main question is related to the queue type. – Xgh05t Feb 07 '20 at 12:09
  • So when you say "But if I try to initialize multiple nodes like this: `TreeNode* l = nullptr, r = nullptr;` It doesn't work and you have to do `TreeNode *l = nullptr, TreeNode *r = nullptr;`", is this not the question? – anastaciu Feb 07 '20 at 12:14
  • @gh05t what type you use for the queue is completely unrelated to the errors you get. Why do you thing it matters what `std::queue q;` is to make `TreeNode* l = nullptr, r = nullptr;` work? – 463035818_is_not_an_ai Feb 07 '20 at 12:16
  • @anastaciu I only mentioned that to highlight that the `*` operator binds to the declarator not the type specifier, I think my main confusion is between declarators and type specifiers, that was just an example to highlight the issue, what you corrected is a typo I overlooked – Xgh05t Feb 07 '20 at 12:23
  • 1
    @idclev463035818 I knew how to make it work, but that was just from experience and tweaking around, I wanted to know what is going on – Xgh05t Feb 07 '20 at 12:24
  • @gh05t that typo is the reason why you get the error " I get a type mismatch when assigning it values of type TreeNode* later on in the program with the words 'invalid conversion from nullptr to non scalar type TreeNode' " you mention in the comment. – anastaciu Feb 07 '20 at 12:25
  • @anastaciu That was just to help the other person understand the problem better – Xgh05t Feb 07 '20 at 12:28
  • 1
    `Then how is the queue declared the way it is?` -> Because `TreeNode*` is also the correct syntax for a pointer type with underlying type `TreeNode`. Likewise `T&` is a reference type. – Sebastian Hoffmann Feb 07 '20 at 12:31
  • 2
    The "inconsistency" in syntax stems from the way declarations are defined. See https://en.cppreference.com/w/cpp/language/declarations and especially the example code. `4) Pointer declarator: the declaration S * D; declares D as a pointer to the type determined by decl-specifier-seq S.` – Sebastian Hoffmann Feb 07 '20 at 12:32
  • @gh05t, my friend, you can use the queue with whatever you want `TreeNode`, `TreeNode*`, `int`, `potatoes`, you decide, but the nodes you then insert must be consistent with the type you declare, `TreeNode != TreeNode*` – anastaciu Feb 07 '20 at 12:34
  • @anastaciu Yes, the confusion was about `*` binding to the type in one case and with the variable in other, this part is obvious!!! – Xgh05t Feb 07 '20 at 12:40
  • @gh05t, so what is your question? – anastaciu Feb 07 '20 at 12:41
  • @SebastianHoffmann That looks very useful, I will try to read and understand, just one small question, inside the angles brackets, we have a declarator or type specifier? – Xgh05t Feb 07 '20 at 12:42
  • Basically it is how can I give TreeNode* as a type, as * can't be bound to the type specifier, I learned these terms while reading answers here, so I couldn't have asked it like that from the beginning. – Xgh05t Feb 07 '20 at 12:44
  • @gh05t yes, you use the angular brackets to pass a template parameter to the template which is a type specifier in this case. So `TreeNode*` is a regular type specifier like `int`. Notice that the type of your `l` and `r` types is `TreeNode*` as well. Just the way how you declare variables of such a type is a bit messed up. – Sebastian Hoffmann Feb 07 '20 at 12:47
0

In std::queue<TreeNode*> q;, the brackets enclose a complete type name. (By “name,” I mean the entire declarator for the type, TreeNode *, not an identifier.) When describing a type with a declarator, the form used is as if a complete normal declaration with an identifier had its identifier removed. For example, starting with a declaration TreeNode *Placeholder, the type name is TreeNode *.

In TreeNode* l = nullptr, r = nullptr;, there are no brackets to group the * with TreeNode. According to the C++ grammar, it is grouped with l. If brackets were allowed here, so that we could write <TypeNode *> l = nullptr, r = nullptr;, then that could work. The issue here is the same as if you write - a + b: The rules are simply that - is grouped with a, so the expression is -a + b, not - (a + b).

You can of course work around this with typedef TreeNode *TreeNodeP; TreeNodeP l = nullptr, r = nullptr;. This shows the effects are simply the results of how the C++ grammar is structured—there is no inherent reason a compiler could not accept any type description first and then a list of identifiers to be declared with that type, but the grammar design simply does not support that.

(One consequence of this is that it is misleading to write int* a, because the proximity of tokens in the text is different from their proximity in the grammar—* is closer to int in the text but is closer to a in the grammar, so the spacing sends the wrong message.)

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312