[ create a new paste ] login | about

Link: http://codepad.org/EWjb1ySa    [ raw code | fork ]

Plain Text, pasted on Nov 22:
Well, I'm not claiming your understanding of pointers is wrong, so the ideas are
all correct; I just don't agree the message created is.

Let's talk about references first, because they're simpler.  A good starting
point to learn references is to think about them as a second name for some
object.  Consider the following code:

    int x;
    int& y = x;

Here, we define an object `x` that is an `int`.  We then define `y` to be
another name for `x`.  Anywhere we say `y`, we can just as well say `x`, and
vice-versa.  We say the second line "binds the reference `y` to `x`".  Note
that the following is also possible, where `x` is a member:

    struct T {
        int x, y;
    };

    T obj;
    T& t = obj;
    int& y = obj.x;

Here, t is another name for `obj`, and `y` is another name for `obj.x`.  If we
change `y`, then we will be changing `obj.y` and `t.y` because **they are the
same thing under a different name**.

Note that references have some restrictions.  Firstly, you must always
immediately state what a reference refers to (what object it is a name of) when
you define it.  The following code makes no sense:

    int x;
    int& y;

Here, we've already stated that `y` is another name for something, but there's
no way for us to state what it is a name for.  We can't just say `y = x` because
that would mean "assign `x` to whatever is referred to by `y`", but there's no
such thing!

Secondly, we can't normally take a reference to something that we can't assign
to.  An example serves well:

    int& y = 5;

This fails, and we can predict that because `5 = 3;` isn't legal.  I am cutting
some large corners in the explanation here, but the details on why things are
this way are best saved for later.

Thirdly, the type of the reference usually has to be the same as of the
referred-to object.  We can't do the following:

    int x;
    short& y = x;

Even though we can convert an `int` to a `short`, what we would be saying here
is "`y` is another name for a `short` called `x`"; however, `x` is *not* a
`short`, so this will not compile.

There are some exceptions to this rule.  If we have a derived class, we can bind
a base-class reference to it.  In other words, the following is allowed:

    struct Base {};
    struct Derived : Base {};

    Derived d;
    Base& b = d;

This makes sense, as a derived class should be able to behave like the base
class; I won't give a detailed explanation of the mechanics, though.

We're almost done with references.  There's just one last thing I'd like to
mention, and that's references to const.  These are a little magical, because
they can bind to a value that is about to be destroyed.  For example, the
following works:

    int x;
    short const& y = x;

You should read the type of `y` right to left: "`y` is a reference to a constant
`short`".  Note that **`y` is not a reference to `x`**!  If we later change `x`,
`y` will not change.  In fact, `y` will never, ever change.  What happens is
that beacuse `x` has a different type from `y`, it is converted and there's a
temporary value involved.  The above is the same as

    int x;
    short const& y = static_cast<short>(x);

The `static_cast<short>(x)` would normally exist for a very brief period of
time.  Because `y` refers to it now, its lifetime is extended so that it will
survive as long as `y` does.  This is a special case -- don't rely on this
unless you fully understand it!

Had the types of `x` and `y` been closer, the same thing would happen as with a
normal reference:

    int x;
    int const& y = x;

Now, changing `x` **will** change the value of `y`.  Don't worry if this looks
counter-intuitive and confusing: it is, and it makes much more sense when we
look at how it's used.


This brings us to the most important question: are references actually any use?
Why don't we always use the original name?  The answer is simple: scope.

When we define a local `x`, nothing outside the function can see it.  Imagine we
want to write a `swap` function that takes two `int`s and switches their values
around.  If we try the simplest version

    void swap(int x, int y) {
        int t = x;
        x = y;
        y = t;
    }

    // in some function
    int a = 5;
    int b = 6;
    swap(a, b);

we will find that the values of `a` and `b` do not change.  This is because `x`
and `y` in this example are copies; when we modify them, we don't change the
original value.

We can make it work by having `x` and `y` refer to `a` and `b` instead.  We need
to change the function to take references:

    void swap(int& x, int& y) {
        int t = x;
        x = y;
        y = t;
    }

Now, when we call `swap(a, b)`, the values of `a` and `b` will change; writing
`x = y;` inside the function is the same as writing `a = b;` outside it.  Notice
that we did not make `t` a reference; what would go wrong if we did?

(The distinction between "x has the value of a" and "x is the same thing as a"
is very significant.  If it isn't clear yet, try writing a function `minmax`
that sets its first argument to the minimum of the two and it's second argument
to the maximum; i.e. `int x = 5; int y = 3; minmax(x, y);` should set `x` to 3
and `y` to 5.  Calling `minmax(x, y);` again shouldn't change anything, because
the values are already correct.)

Let's revisit a handy use case for references to const now.  Let's say we have a
function that counts the number of times the letter `A` occurs in a string:

    int num_a(std::string s) {
        int counter = 0;
        for (char c : s) // a loop: for every char c in s
            if (c == 'A')
                counter++;
        return counter;
    }

While this function works, calling it involves making a copy of whatever string
we want to check.  If we have very long strings, this may be expensive, so we'd
rather get rid of the copy.  However, if we just change the `std::string` into
an `std::string&`, we won't be able to do `num_a("TCAAGTC")`, because only an
`std::string` can be used to initialise an `std::string&`.

The solution here is to use references to const.  We can define `num_a` to take
`std::string const& s` and then `num_a("TCAAGTC")` will create a temporary
`std::string`, bind `s` to it, and prolong the lifetime of the temporary.
Hopefully, this use-case makes the strange nature of references to const more
understandable.


Enough references!  Let's take a look at pointers.

Imagine the following function:

    void f(int& i, int const& j, int const& k) {
        i += j;
        i += k;
    }

If we know that the values of `i`, `j` and `k` were all 1 when we called `f`,
what will their values of be afterwards?

Imagine the following case:

    int x = 1;
    f(x, x, x);

When we call `f` like this, the line `i += j;` ends up changing `k`, and we end
up with the rather surprising `i == 4`.  We want to avoid cases like this, so we
want to have some way of checking whether two names refer to the same thing or
not.

For this purpose, we define the `&` operator as follows: if and only if `x` and
`y` refer to the same object, `&x == &y` is true.  Now we can add a check to
our function above:

    void f(int& i, int const& j, int const& k) {
        if (&i == &k)
            std::cout << "Warning!  i and k refer to the same thing!" << std::endl;
        i += j;
        i += k;
    }

(Convince yourself that we don't care whether `i` and `j` refer to the same
thing, or `j` and `k` refer to the same thing.)

We can see `&x` as a value that uniquely identifies `x`.  Surely, then, we can
define an operation that takes `&x` and gives us back `x`?

It turns out we can: we use the `*` operator.  We can now use `*&x` in order to
refer to `x`, instead of just using `x` directly.  This includes things like:

    int x;
    int& y = *&x;
    // or even:
    int& z = *&*&*&x;

Let's get our hands dirty and think about how `&` could be implemented.  You
should know that roughly speaking, variables are all just areas of memory that
we've given names to.  Internally, computers use numbers to specify what bit of
memory something should happen to.  We call the number of a byte its address,
and if we have the address of the first byte of a variable, we've uniquely
identified the variable.  This is what `&` will return, and because of this `&`
is called the address-of operator.

(For the curious, the `*` operator is called the `dereference` operator.  They
can't all have obvious names. :) )

This immediately hints at a limitation of `&`: we can't take the address of
something that doesn't have a place in memory.  For example, we can't do `&5`
because there's no piece of memory we're talking about.  Similarly, we can't do
`&&x` because the address of `x` doesn't have a proper location.

All named variables have addresses.  All references have addresses (equal to the
address of the referred to object).

On the other hand, temporaries all do not have addresses.  The return values of
functions (except functions that return references) do not have addresses.

When something has an address, we call it an `lvalue`.  When something doesn't,
we call it an `rvalue`.  Think back to when we saw we couldn't do `int& y = 5;`.
The explanation then was that references only bind to something that can be on
the left side of an assignment; the better explanation is that (non-const)
references bind only to lvalues.  Confusingly, some things are lvalues even
though you can't assign to them; such is life.

Again, don't worry if the details of the above are not entirely clear: remember
that if something has a name, it has an address, and if something exists for a
very short time, it doesn't.  In practice, this will get you a very long way.


Let's take another look at what we can do with `&x`.  We know we can dereference
it; it turns out we can also store it.  We do this as follows:

    int x;
    int* p = &x;

We say `p` is a pointer.  We can do all the things we could do to `&x` to `p`:
for instance, `*p` is the same thing as `x`.  We can print `p`, if we want to;
it will look like a number.  Finally, we can take the address of `&p` using `p`,
and even put it in another pointer if we so desire:

    int x;
    int* p = &x;
    int** p2 = &p;

Now, `**p2` is the same thing as `x`.

What if we want to point to nothing?  It turns out there's a special value that
we can assign to any pointer, which will make it "not point anywhere"; this
value is `NULL`.  This can be convenient for initialising pointers:

    int* p = NULL;

We can now check whether `p` is pointing to something valid using `p != NULL`.

What happens if `p == NULL` and we attempt to do `*p`?  The most correct answer
here is "we don't know".  The C++ language does not define the result in such a
case; anything could happen and you shouldn't complain.  In practice, this will
usually lead to a crash.

Let's introduce one last feature before I leave you with a code sample to think
about.  Wouldn't it be nice if I could say "I want a pointer to a variable of
such and such type" and get it even if I don't have a variable like that lying
around?

It turns out this is a very common need, and the C++ language provides the `new`
operator for this purpose.  The syntax is as follows:

    int* p = new int;

Here, `p` points to a completely new int.  We can use that int for as long as we
want; it's another variable we can work with.  This has a flip side, however:
seeing as we are allowed to use it for as long as we want, we have to explicitly
state we don't want it when we're done with it.  This is done using the `delete`
operator:

    delete p;

After that, using `*p` will be an error, just like using `*p` when `p == NULL`
is.

In practice, getting the usages of `new` and `delete` right is a rather
bothersome task, and there are ways around doing it explicitly.  Before you use
the two, you should read up about a technique called RAII.

This wraps up the basics of pointers and references.  Summary:

 * References allow one to define another name for something.
 * References must always be initialised.
 * Pointers store the address of a variable.
 * Pointers are objects; they have addresses and can be passed to functions.
 * The address of a references is the address of what it refers to.

Here's an example of a practical use for pointers:

    class Stack {
        struct Node {
            Node* next;
            int value;

            Node() : next(), value() {}
            Node(Node* n, int v) : next(n), value(v) {}
            ~Node() {
                // Note that deleting NULL is perfectly fine.
                delete next;
            }

          private:
            // These two lines forbid Node from being copied or assigned; this
            // is done because doing so would not be safe.  Don't worry about
            // it.
            // This is called the Rule of Three.
            Node(Node const&);
            void operator=(Node const&);
        };

        Node* head;

        // Again, prevent copying:
        Node(Node const&);
        void operator=(Node const&);
      public:

        Stack() : head() {}
        ~Stack() {
            delete head;
        }

        void push(int i) {
            head = new Node(head, i);
        }

        void pop() {
            Node* p = head;
            head = head->next;
            delete p;
        }

        int peek() const {
            return head->value;
        }

        bool empty() const {
            return head != NULL;
        }
    };

Exercises:

 1. Add a print function to the above class that prints nodes in the order they
    were added.
 2. Implement copying for the class.
 3. Write an immutable stack class.  Make stacks share tails whenever possible.



Create a new paste based on this one


Comments: