ii
                     C++lecture notes
                         Fran¸cois Fleuret
                     
                        November 21, 2005
                                                                                                               iv
           Note
           This document is based on a C++ course given at the University of Chicago in
           spring of 2001 and was modified for a course at EPFL in fall of 2004. It is still
           a work in progress and needs to be polished to be a reference text.
           The tools for this course are free-softwares. Mainly the GNU/Linux operating
           system, the GNU C++ compiler, the emacs text editor, and a few standard
           UNIX commands.
                    c
           This document is 
 Franc¸ois Fleuret. It can be redistributed for free as is,
           without any modification.
             $Id: cpp-course.tex,v 1.33 2004/12/19 21:04:27 fleuret Exp $
                                                                                                                                                                                                     CONTENTS                                                                                vi
                                                                                                                                                                                                               2.3.9    The do { } while statement . . . . . . . . . . . . . . . .          19
                                                                                                                                                                                                               2.3.10 The continue statement          . . . . . . . . . . . . . . . . . .   20
                                                                                                                                                                                                               2.3.11 The switch / case statements . . . . . . . . . . . . . . .            20
                                                                                                                                                                                                               2.3.12 Computation errors with floating point counters             . . . . .  21
                                                                                                                                                                                                         2.4   An example of extreme C syntax . . . . . . . . . . . . . . . . . .           22
                            Contents                                                                                                                                                                 3 Expressions, variable scopes, functions                                              23
                                                                                                                                                                                                         3.1   Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      23
                                                                                                                                                                                                         3.2   Arithmetic operators . . . . . . . . . . . . . . . . . . . . . . . . .       23
                                                                                                                                                                                                               3.2.1    List of operators . . . . . . . . . . . . . . . . . . . . . . .     23
                                                                                                                                                                                                               3.2.2    Operators depend on the types of the operands . . . . . .           24
                                                                                                                                                                                                               3.2.3    Implicit conversions    . . . . . . . . . . . . . . . . . . . . .   24
                            1 Memory, CPU, files                                                                     1                                                                                          3.2.4    Arithmetic exceptions . . . . . . . . . . . . . . . . . . . .       25
                                1.1   Memory, files, CPU and compilation . . . . . . . . . . . . . . . .              1                                                                                         3.2.5    Boolean operators . . . . . . . . . . . . . . . . . . . . . .       26
                                      1.1.1    Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . .        1                                                                                         3.2.6    Comparison operators . . . . . . . . . . . . . . . . . . . .        27
                                      1.1.2    Data types . . . . . . . . . . . . . . . . . . . . . . . . . .        2                                                                                         3.2.7    Assignment operator . . . . . . . . . . . . . . . . . . . . .       27
                                      1.1.3    Signal quantification . . . . . . . . . . . . . . . . . . . . .        2                                                                                         3.2.8    Increment and decrement operators          . . . . . . . . . . . .  27
                                      1.1.4    File system . . . . . . . . . . . . . . . . . . . . . . . . . .       3                                                                                         3.2.9    Precedence of operators . . . . . . . . . . . . . . . . . . .       28
                                      1.1.5    Size orders of magnitude . . . . . . . . . . . . . . . . . . .        3                                                                                         3.2.10 Grammar, parsing and graph of an expression . . . . . . .             29
                                1.2   CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        3                                                                                         3.2.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . .         29
                                      1.2.1    What is a CPU . . . . . . . . . . . . . . . . . . . . . . . .         3                                                                                   3.3   lvalue vs. rvalue    . . . . . . . . . . . . . . . . . . . . . . . . . . .   30
                                      1.2.2    Speed orders of magnitude       . . . . . . . . . . . . . . . . .     4                                                                                   3.4   Scopes of variables . . . . . . . . . . . . . . . . . . . . . . . . . .      30
                                1.3   Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        5                                                                                   3.5   Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      31
                                      1.3.1    Role of compilation . . . . . . . . . . . . . . . . . . . . . .       5                                                                                         3.5.1    Defining functions . . . . . . . . . . . . . . . . . . . . . .       31
                                      1.3.2    Example . . . . . . . . . . . . . . . . . . . . . . . . . . . .       5                                                                                         3.5.2    void return type . . . . . . . . . . . . . . . . . . . . . . .      32
                                1.4   Object-Oriented Programming . . . . . . . . . . . . . . . . . . .              7                                                                                         3.5.3    Argument passing by value . . . . . . . . . . . . . . . . .         33
                                                                                                                                                                                                               3.5.4    Argument passing by reference . . . . . . . . . . . . . . .         33
                            2 Shell and basic C++                                                                   9                                                                                          3.5.5    Recursive function call . . . . . . . . . . . . . . . . . . . .     34
                                2.1   GNU/Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          9                                                                                         3.5.6    Stopping condition . . . . . . . . . . . . . . . . . . . . . .      35
                                      2.1.1    What is Linux . . . . . . . . . . . . . . . . . . . . . . . .         9                                                                                   3.6   The abort() function . . . . . . . . . . . . . . . . . . . . . . . .         35
                                      2.1.2    What is Open-Source . . . . . . . . . . . . . . . . . . . .           9
                                      2.1.3    Tools for this course . . . . . . . . . . . . . . . . . . . . .     11                                                                                4 Arrays and pointers, dynamic allocation                                              37
                                2.2   Shell and simple file management . . . . . . . . . . . . . . . . . .          11                                                                                    4.1   Arrays and pointers      . . . . . . . . . . . . . . . . . . . . . . . . .   37
                                      2.2.1    File names and paths      . . . . . . . . . . . . . . . . . . . .   11                                                                                          4.1.1    Character strings . . . . . . . . . . . . . . . . . . . . . . .     37
                                      2.2.2    Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   12                                                                                          4.1.2    Built-in arrays . . . . . . . . . . . . . . . . . . . . . . . .     37
                                      2.2.3    Basic commands . . . . . . . . . . . . . . . . . . . . . . .        12                                                                                          4.1.3    Index of arrays, the [ ] operator, out of bounds exception 38
                                      2.2.4    References for documentation . . . . . . . . . . . . . . . .        14                                                                                          4.1.4    Pointers, the *, and & operators . . . . . . . . . . . . . . .      39
                                2.3   First steps in C++ . . . . . . . . . . . . . . . . . . . . . . . . . .       14                                                                                          4.1.5    Pointers to pointers to pointers to ... . . . . . . . . . . . .     39
                                      2.3.1    Data types . . . . . . . . . . . . . . . . . . . . . . . . . .      14                                                                                          4.1.6    Dereference operator * . . . . . . . . . . . . . . . . . . . .      40
                                      2.3.2    Asimple example of variable manipulation . . . . . . . .            15                                                                                          4.1.7    Pointers to arrays    . . . . . . . . . . . . . . . . . . . . . .   41
                                      2.3.3    Variable naming conventions . . . . . . . . . . . . . . . .         16                                                                                          4.1.8    Pointers do not give information about pointed array sizes          41
                                      2.3.4    Streams, include files . . . . . . . . . . . . . . . . . . . . .     16                                                                                          4.1.9    Box and arrows figures . . . . . . . . . . . . . . . . . . . .       42
                                      2.3.5    The sizeof operator . . . . . . . . . . . . . . . . . . . . . .     17                                                                                          4.1.10 The main function’s parameters . . . . . . . . . . . . . . .          42
                                      2.3.6    The if statement . . . . . . . . . . . . . . . . . . . . . . .      17                                                                                          4.1.11 Adding integers to pointers . . . . . . . . . . . . . . . . .         43
                                      2.3.7    The for statement . . . . . . . . . . . . . . . . . . . . . .       18                                                                                    4.2   Dynamic allocation . . . . . . . . . . . . . . . . . . . . . . . . . .       44
                                      2.3.8    The while statement . . . . . . . . . . . . . . . . . . . . .       19                                                                                          4.2.1    Why? How? . . . . . . . . . . . . . . . . . . . . . . . . .         44
                            vii                                                                     CONTENTS                                                                                    CONTENTS                                                                            viii
                                     4.2.2   Dynamic arrays . . . . . . . . . . . . . . . . . . . . . . . .     45                                                                                        7.1.5   Combining O(:)s . . . . . . . . . . . . . . . . . . . . . . .      75
                                     4.2.3   Test of a null pointer . . . . . . . . . . . . . . . . . . . . .   46                                                                                        7.1.6   Family of bounds . . . . . . . . . . . . . . . . . . . . . . .     75
                                     4.2.4   Anon-trivial example using dynamic memory allocation .             46                                                                                        7.1.7   Some examples of O(:) . . . . . . . . . . . . . . . . . . . .      76
                                     4.2.5   Dynamically allocated bi-dimensional arrays . . . . . . . .        47                                                                                        7.1.8   Estimating the cost of an algorithm       . . . . . . . . . . . .  76
                                     4.2.6   What is going on inside: the stack and the heap         . . . . .  48                                                                                                Succession of statements . . . . . . . . . . . . . . . . . . .     76
                               4.3   Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    49                                                                                                Conditional execution . . . . . . . . . . . . . . . . . . . .      77
                                     4.3.1   Declaration vs. definition . . . . . . . . . . . . . . . . . .      49                                                                                                Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    77
                                     4.3.2   The const statements . . . . . . . . . . . . . . . . . . . .       50                                                                                        7.1.9   Cost and recursion . . . . . . . . . . . . . . . . . . . . . .     77
                                     4.3.3   The enum type . . . . . . . . . . . . . . . . . . . . . . . .      51                                                                                        7.1.10 Average cost . . . . . . . . . . . . . . . . . . . . . . . . .      78
                                     4.3.4   The break statement . . . . . . . . . . . . . . . . . . . . .      51                                                                                  7.2   Some algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .      79
                                     4.3.5   Bitwise operators . . . . . . . . . . . . . . . . . . . . . . .    52                                                                                        7.2.1   Searching a value in a sorted array . . . . . . . . . . . . .      79
                                     4.3.6   The comma operator . . . . . . . . . . . . . . . . . . . . .       52                                                                                        7.2.2   Pivot sort . . . . . . . . . . . . . . . . . . . . . . . . . . .   80
                                                                                                                                                                                                    7.3   Simple questions . . . . . . . . . . . . . . . . . . . . . . . . . . .     81
                            5 War with the bugs                                                                 55                                                                                  7.4   Fusion sort    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
                               5.1   Preamble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     55                                                                                  7.5   Quick sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   81
                               5.2   The Bug Zoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      55                                                                                  7.6   Strategies when two parameters are involved ?         . . . . . . . . . .  83
                                     5.2.1   The program crashes: Segmentation fault . . . . . . . .            55
                                             Unauthorized memory access . . . . . . . . . . . . . . . .         56                                                                              8 Creating new types                                                                 85
                                             Incorrect system call . . . . . . . . . . . . . . . . . . . . .    57                                                                                  8.1   Preamble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     85
                                     5.2.2   The program crashes: Floating point exception . . . .              57                                                                                  8.2   Asimple example . . . . . . . . . . . . . . . . . . . . . . . . . . .      85
                                     5.2.3   The program never stops . . . . . . . . . . . . . . . . . .        58                                                                                  8.3   Pointers to defined types, and the -> operator . . . . . . . . . . .        86
                                     5.2.4   The program uses more and more memory. . . . . . . . .             58                                                                                  8.4   Operator definitions, a complex class . . . . . . . . . . . . . . . .       86
                                     5.2.5   The program does not do what it is supposed to do           . . .  58                                                                                  8.5   Passing by value vs. passing by reference       . . . . . . . . . . . . .  87
                               5.3   How to avoid bugs . . . . . . . . . . . . . . . . . . . . . . . . . .      60                                                                                  8.6   Some timing examples . . . . . . . . . . . . . . . . . . . . . . . .       88
                                     5.3.1   Write in parts . . . . . . . . . . . . . . . . . . . . . . . . .   60
                                     5.3.2   Good identifiers . . . . . . . . . . . . . . . . . . . . . . . .    60                                                                              9 Object-Oriented programming                                                        91
                                     5.3.3   Use constants instead of numerical values . . . . . . . . .        60                                                                                  9.1   Intro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  91
                                     5.3.4   Comment your code . . . . . . . . . . . . . . . . . . . . .        61                                                                                  9.2   Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     92
                                     5.3.5   Symmetry and indentation . . . . . . . . . . . . . . . . .         61                                                                                  9.3   Protected fields . . . . . . . . . . . . . . . . . . . . . . . . . . . .    92
                                     5.3.6   Use a DEBUG flag . . . . . . . . . . . . . . . . . . . . . .        62                                                                                  9.4   Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    93
                               5.4   How to find bugs . . . . . . . . . . . . . . . . . . . . . . . . . . .      63                                                                                  9.5   Calling methods     . . . . . . . . . . . . . . . . . . . . . . . . . . .  93
                                     5.4.1   Print information during execution . . . . . . . . . . . . .       63                                                                                  9.6   Some memory figures . . . . . . . . . . . . . . . . . . . . . . . . .       94
                                     5.4.2   Write the same routine twice . . . . . . . . . . . . . . . .       63                                                                                  9.7   Separating declaration and definition . . . . . . . . . . . . . . . .       95
                                     5.4.3   Heavy invariants . . . . . . . . . . . . . . . . . . . . . . .     64                                                                                  9.8   Protection of data integrity . . . . . . . . . . . . . . . . . . . . .     95
                               5.5   Anti-bug tools     . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64                                                                                  9.9   Abstraction of concepts . . . . . . . . . . . . . . . . . . . . . . .      96
                                     5.5.1   gdb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    64                                                                                  9.10 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      97
                                     5.5.2   Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . .   65                                                                                  9.11 Default constructor . . . . . . . . . . . . . . . . . . . . . . . . . .     98
                                                                                                                                                                                                    9.12 Destructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    99
                            6 Homework                                                                          69                                                                                  9.13 Tracing precisely what is going on       . . . . . . . . . . . . . . . . .  99
                                                                                                                                                                                                    9.14 The member operators . . . . . . . . . . . . . . . . . . . . . . . . 100
                            7 Cost of algorithm, sorting                                                        73                                                                                  9.15 Summary for classes . . . . . . . . . . . . . . . . . . . . . . . . . 102
                               7.1   Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . .     73
                                     7.1.1   Why? How ? . . . . . . . . . . . . . . . . . . . . . . . . .       73                                                                              10 Homework                                                                        103
                                     7.1.2   Definition of O(:) . . . . . . . . . . . . . . . . . . . . . . .    74
                                     7.1.3   Some O(:) . . . . . . . . . . . . . . . . . . . . . . . . . . .    74                                                                              11 Detail of class definitions                                                      105
                                     7.1.4   Summing O(:)s . . . . . . . . . . . . . . . . . . . . . . . .      74                                                                                  11.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105