Return local pointer

Question

struct node { Item item; node *l, *r; node(Item x) {item = x; l = 0; r = 0;} }; typedef node* link; link max(Item a[], int l, int r) { int m = (l+r)/2; link x = new node(a[m]); if (l==r) return x; // return a local pointer x->l = max(a, l, m); xr = max(a, m+1, r); Item u = x->l->item, v = x->r->item; if (u>v) x->item = u; else x->item=v; return x; // return a local pointer } 

This is a code snippet from Robert Sedgewick's Algorithm in C ++, p. 252, Program 5.19. And in the max() function, the returned variable is a pointer that is created inside the function.

In my opinion, returning to a local pointer is not allowed in c / C ++. So my question is, "is it right to write such a function"? I can’t believe that such a classic book is mistaken. Or did I misunderstand the principle? Please help. Thanks.

Answer 1

x not a "local pointer", that is, a pointer to a local variable. *x was allocated using new . x points to dynamically allocated memory and returns this pointer. So yes, it’s normal to write such a function, and there is no error in the book.

Answer 2

Error returning a pointer to a local variable. x indicates the variable allocated on the heap:

 link x = new node(a[m]); 

Thus, x does not indicate a local variable.

The reason that returning a pointer to a local variable is an error is because such a variable exists only as long as the function is active (i.e. between its input and output). Variables allocated on the heap (for example, using the new operator) exist until they are freed (for example, with the delete operator).

Answer 3

This is great because the contents of x allocated on the heap, not on the stack. You may get confused as there is typedef node* link; , which makes it look like stack distribution, as it masks the fact that x is actually node * .