restituisce un puntatore locale

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); 
    x-r = 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 
} 

Questa è una parte di codice da "Algorithm in C++" di Robert Sedgewick, pagina 252, Programma 5.19. E nella funzione max(), la variabile restituita è un puntatore che viene creato all'interno della funzione.

A mio parere, restituire un puntatore locale non è consentito in c/C++. Quindi la mia domanda è che "è OK scrivere una funzione come questa"? Non posso credere che un libro così classico commetta errori come questo. O ho frainteso il principio? Per favore aiuto. Grazie.

Answer 1

x non è un "puntatore locale", ovvero un puntatore a una variabile locale. *x è stato allocato utilizzando new. x punta alla memoria allocata dinamicamente e restituire quel puntatore va bene. Quindi sì, è OK scrivere una funzione come questa, e non c'è un errore nel libro.

Answer 2

È un errore restituire un puntatore a una variabile locale. x indica una variabile allocata sul mucchio:

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

Così x non punta a una variabile locale.

Il motivo per cui restituire un puntatore a una variabile locale è un errore è che tale variabile esiste solo fino a quando la funzione è attiva (ad esempio, tra l'immissione e l'uscita). Le variabili allocate nello heap (ad esempio con l'uso dell'operatore new) esistono finché non vengono deallocate (ad esempio con l'operatore delete).

Answer 3

Questo va perfettamente bene, perché i contenuti di x sono allocati nell'heap, non nello stack. Potresti essere confuso visto che c'è uno typedef node* link; lì, che lo fa apparire come un'allocazione dello stack poiché maschera il fatto cheè in realtà un node *.