4

In my Data Structures in C++ class we're working on binary trees. Some of the code contains places where & and * are used at the same time (right next to each other) and it's very confusing.

void balance( AvlNode * & t )

is one example of a function definition in which this is used. What happens here with the * and &?

Edit: The answers to this have told me that I really know nothing about pointers and references, but the sources all say different things, like here for example calls * the dereference operator. Where can I find all of this information in one place? (not on stackoverflow preferably)

Mitchell Carroll
  • 479
  • 5
  • 13
  • 7
    It is a reference to a pointer. – Cory Kramer Sep 29 '14 at 21:32
  • 1
    If you are not yet comfortable with references and pointers, [this is a very thorough read](https://stackoverflow.com/questions/57483/what-are-the-differences-between-a-pointer-variable-and-a-reference-variable-in?rq=1). – Cory Kramer Sep 29 '14 at 21:35
  • See http://c-faq.com/decl/spiral.anderson.html for the "clockwise spiral rule" to parse these kinds of things in your head. – Dave Sep 29 '14 at 21:43

3 Answers3

7

Read from right to left1, reading & as a "reference to [a|an]" and * as a "pointer to [a|an]", so you get: "t is a reference to a pointer to an AvlNode".

1. For more complex cases, it's not always entirely right to left--it's from the name being declared outward to the type of the declaration. If you have multiple nested parentheses, you proceed right from name to a closing parenthesis, then left to the matching open parenthesis, then right from the place you last left off to the next closing parenthesis, and so on until you reach the outer-most level.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
2

The '&' character has a special meaning in C++ when it's used inside of a function declaration or definition. It means "pass the value by reference". When you "pass by reference" C++ will automatically create a reference of your variable when you pass it to the function, and then it will automatically dereference it inside the function.

So this function passes one variable t of type AvlNode * by reference. Hence, you have AvlNode * & t

So for example:

void balance( AvlNode * & t )
{...}

main()
{
   AvlNode * a = new AvlNode();
   balance(a);
}

is the same as:

void balance( AvlNode ** t_ptr )
{
   AvlNode * t = *t_ptr;
   ...
}

main()
{
   AvlNode * a = new AvlNode();
   balance(&a);
}
Gillespie
  • 5,780
  • 3
  • 32
  • 54
1

It is a definitian of a reference to pointer of type AvlNode *

Consider for example (for the demonstrative purpose it is not important that it has a memory leak)

#include <iostream>

typedef int AvlNode; // It is not important what is the type AvlNode

void balance( AvlNode * & t )
{
    t = new AvlNode( 10 );
}

void another_balance( AvlNode * t )
{
    t = new AvlNode( 20 );
}

int main()
{
   AvlNode *p = NULL;

    std::cout << ( void * )p << std::endl;

    another_balance( p );

    std::cout << ( void * )p << std::endl;

    balance( p );

    std::cout << ( void * )p << std::endl;
    std::cout << *p << std::endl;

    delete p;
}

Consider the results of the function calls.

Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335