-6

For this function TreeNode* buildTree(vector& preorder, vector& inorder). Why there is a * in front of the function name? Why they use & in front of the variables?

ChengW
  • 1
  • 2

1 Answers1

-1

Try looking at * not as being in front of function name, but rather as being behind TreeNode. In other words, that * changes function return type from structure to pointer to a structure.

& in front of variables means that they are, essentially, still pointers, but they can't be NULL (there are ways to get around that, but that would just confuse the issue further). So vector& preorder means that preorder is pointer (the term used is reference) to vector, but you don't need to check if that pointer is NULL. You can simply go ahead and use it.

Without much loss you could change those & into *, changing . in your function to -> and things would work the same. I bet assembly code would be exactly the same as well.

TCvD
  • 600
  • 2
  • 8
  • 1
    "So vector& preorder means that preorder is pointer " thats wrong. References are not pointers. They can be implemented via pointers, but that doesn make them pointers – 463035818_is_not_an_ai Nov 15 '20 at 15:14
  • I'll be eternally grateful if you can point me to an actual difference between the two. Syntactically they are different, I agree, but semantically they are not. You can cast pointer to reference and vice versa and the universe keeps turning exactly as it did before. – TCvD Nov 15 '20 at 15:32
  • biggest difference is that a reference cannot be NULL (and there are no ways to get around that). – 463035818_is_not_an_ai Nov 15 '20 at 17:32
  • a reference cannot be rebound to refer to a different object after initialization. – 463035818_is_not_an_ai Nov 15 '20 at 17:33
  • there are no const and non-const references (because they cannot be rebound) but there are const and non-const pointers – 463035818_is_not_an_ai Nov 15 '20 at 17:34
  • void fun(Obj &o); fun( *((Obj*)NULL) ); Sadly, learned this the hard way. – TCvD Nov 15 '20 at 17:38
  • Thats undefined behavior. In code that has UB anything is possible, and nothing – 463035818_is_not_an_ai Nov 15 '20 at 17:41
  • 1
    with that logic you could say that accessing arrays out of bound is possible, because you wrote code like this `int x[5]; x[42] = 3;`. The fact that you can write such code and you do not get a compiler error doesn't imply that it is correct C++. Reference cannot be null, just like you cannot access an array out of bounds. – 463035818_is_not_an_ai Nov 15 '20 at 17:43
  • How is it undefined? I know that most people consider C++ somehow superior and from reading standards you can certainly get that impression. But compiler writers need to get down to earth. And down in mud reference and pointer are no different. I will even give you the 'reference cannot be NULL' -- when things are OK. But sometimes, once you realize that may not always hold (due to bugs of course), previously unsolvable problems become easy to solve. – TCvD Nov 15 '20 at 17:47
  • As I was writing my response I now see the point of disagreement. You are right, as far as good practices and "normal operation" goes. But as I said, making such assumptions can lead to less night sleep than is healthy. – TCvD Nov 15 '20 at 17:48
  • in general a compiler cannot tell you if your code has undefined behavior. Derferencing a NULL is undefined. When you compile code that has undefined behavior you can get anything as outcome. You do not have to dive into details of compilers for that. Compilers are simply not made to compile wrong code – 463035818_is_not_an_ai Nov 15 '20 at 17:48
  • avoiding undefined behavior is not just "good practice" it is necessary practice. – 463035818_is_not_an_ai Nov 15 '20 at 17:49
  • There I must disagree with you. Dereferencing any pointer is a completely defined behavior -- it leads to memory access. What happens after that depends on hardware. These days it usually leads to SEGFAULT, but I still remember days when you could read from nonexistent memory locations (no RAM or anything else at that location). – TCvD Nov 15 '20 at 17:53
  • you can disagree as much as you like, you are still wrong. Derereferincing an invalid or null pointer is undefined. https://en.cppreference.com/w/cpp/language/ub – 463035818_is_not_an_ai Nov 15 '20 at 17:54
  • And compiler will compile anything syntactically correct. That doesn't mean it's not wrong. – TCvD Nov 15 '20 at 17:54