28 August 2011

C/C++ Pointers




Pointer Rules

One of the nice things about pointers is that the rules which govern how they work are pretty simple. The rules can be layered together to get complex results, but the individual rules remain simple.
  1. Pointers and Pointees
    A pointer stores a reference to something. Unfortunately there is no fixed term for the thing that the pointer points to, and across different computer languages there is a wide variety of things that pointers point to. We use the term pointee for the thing that the pointer points to, and we stick to the basic properties of the pointer/pointee relationship which are true in all languages. The term "reference" means pretty much the same thing as "pointer" -- "reference" implies a more high-level discussion, while "pointer" implies the traditional compiled language implementation of pointers as addresses. For the basic pointer/pointee rules covered here, the terms are effectively equivalent.
    Pointer pointing to pointee
    The above drawing shows a pointer named x pointing to a pointee which is storing the value 42. A pointer is usually drawn as a box, and the reference it stores is drawn as an arrow starting in the box and leading to its pointee.
    Allocating a pointer and allocating a pointee for it to point to are two separate steps. You can think of the pointer/pointee structure as operating at two levels. Both the levels must be set up for things to work. The most common error is concentrating on writing code which manipulates the pointer level, but forgetting to set up the pointee level. Sometimes pointer operations that do not touch the pointees are called "shallow" while operations on the pointees are called "deep".
  2. Dereferencing
    The dereference operation starts at the pointer and follows its arrow over to access its pointee. The goal may be to look at the pointee state or to change the pointee state.
    The dereference operation on a pointer only works if the pointer has a pointee -- the pointee must be allocated and the pointer must be set to point to it. The most common error in pointer code is forgetting to set up the pointee. The most common runtime crash because of that error in the code is a failed dereference operation. In Java the incorrect dereference will be flagged politely by the runtime system. In compiled languages such as C, C++, and Pascal, the incorrect dereference will sometimes crash, and other times corrupt memory in some subtle, random way. Pointer bugs in compiled languages can be difficult to track down for this reason.
  3. Pointer Assignment
    Pointer assignment between two pointers makes them point to the same pointee. So the assignment y = x; makes y point to the same pointee as x. Pointer assignment does not touch the pointees. It just changes one pointer to have the same reference as another pointer. After pointer assignment, the two pointers are said to be "sharing" the pointee.

    Pointers and Memory

    A 31 page introduction to programming with pointers and memory in C, C++ and other languages. Explains how pointers and memory work and how to use them -- from the basic concepts through all the major programming techniques. Can be used as an introduction to pointers for someone with basic programming experience or as a quick review. Many advanced programming and debugging problems only make sense with a solid understanding of pointers and memory -- this document tries to provide that understanding.
    Topics include: pointers, local memory, allocation, deallocation, dereference operations, pointer assignment, deep vs. shallow copies, the ampersand operator (&), bad pointers, the NULL pointer, value parameters, reference parameters, pointer to pointers, dynamic heap memory, memory ownership models, and memory leaks. The article focuses on pointers and memory in compiled languages like C and C++ with occasional notes about Java.


    Linked List Basics

    A 26 page introduction to linked lists in C/C++. Includes examples, drawings, and practice problems, and solution code. The more advanced article, Linked List Problems, has 18 sample problems with solutions.

    This article introduces the basic structures and techniques for building linked lists with a mixture of explanations, drawings, sample code, and exercises. The material is useful if you want to understand linked lists or if you want to see a realistic, applied example of pointer-intensive code. Even if you never really need a linked list, they are an excellent way to learn pointers and pointer algorithms.


    Linked List Problems

    A quick review of linked list basics followed by 18 linked list problems, basic through advanced, with solution code in C/C++. Nobody really uses linked lists any more, so why bother with these problems? Linked lists are a superb source of complex practice problems. Link list problems are simple to define, yet can have complicated, pointer-intensive solutions (which is why they are often used on exams and in interviews). If you are serious about your pointer/algorithm skills, there's no substitute for practice and this is the place to start.

    For a few problems, multiple solutions are presented, such as iteration vs. recursion or dummy node vs. reference pointer. The problems are: Count, GetNth, DeleteList, Pop, InsertNth, SortedInsert, InsertSort, Append, FrontBackSplit, RemoveDuplicates, MoveNode, AlternatingSplit, ShuffleMerge, SortedMerge, SortedIntersect, Reverse, and RecursiveReverse.


    Binary Trees

    Introduces the basic concepts of binary trees, and works through a series of practice problems with solution code in C/C++ and Java. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.


    The Great Tree-List Recursion Problem

    One of the neatest recursive pointer problems ever devised. This is an advanced recursive pointer problem that uses a binary tree and a doubly linked list. You should be comfortable with pointers and recursion to understand this problem. This article introduces the problem with a few memory diagrams, gives some hints, and provides solution code in both Java and C/C++.


    Essential C

    A 45 page summary of the C language. Explains all the common features and techniques for the C language. The coverage is pretty quick, so it is most appropriate for someone with some programming background who needs to see how C works. Topics include variables, int types, floating point types, promotion, truncation, operators, control structures (if, while, for), functions, value parameters, reference parameters, structs, pointers, arrays, the pre-processor, and the standard C library functions.




Send Suggestion and Comment

Subscribe to:
 
Powered by Blogger.