Notes, code and various other snippets from Stroustrup's PPP, arranged by part, chapter and subchapter.

0 Notes to the Reader

0.1 The structure of this book

0.1.1 General approach

0.1.2 Drills, exercises, etc.

0.1.3 What comes after this book?

0.2 A philosophy of teaching and learning

0.2.1 The order of topics

0.2.2 Programming and programming language

0.2.3 Portability

0.3 Programming and computer science

0.4 Creativity and problem solving

0.5 Request for feedback

0.6 References

0.7 Biographies

1 Computers, People, and Programming

1.1 Introduction

1.2 Software

1.3 People

The best programmers spend most of their time not writing code.

1.4 Computer science

1.5 Computers are everywhere

1.5.1 Screens and no screens

1.5.2 Shipping

1.5.3 Telecommunications

1.5.4 Medicine

1.5.5 Information

1.5.6 A vertical view

1.5.7 So what?

1.6 Ideals for programmers

Programming is understanding.

Discuss designs and programming techniques with others. You can learn so much simply trying to articulate an idea.

Direct expression of ideas in code is a fundamental ideal of programming.

Part I The Basics

2 Hello, World!

2.1 Programs

2.2 The classic first program

#include "std_lib_facilities.h"
int main()
    cout << "Hello, World!\n";
    return 0;

For << say 'output'

Remember, code is read by humans too (including 'future you').

2.3 Compilation

Put a ; after every expression not ending in a }

2.4 Linking

2.5 Programming environments

3 Objects, Types, and Values

3.1 Input

An object is a region of memory with a type that specifies what kind of information can be placed in it.

A named object is called a variable.

string first_name;
cin >> first_name;

>> say 'input to' or 'in to'

cin is type sensitive. Whitespace terminates strings, otherwise ignored.

3.2 Variables

The "places" in which we store data are called objects.

To access an object we need a name.

A named object is a variable and has a specific type.

The data items we put into variables are values.

A statement that defines a variable is a definition. (It usually should provide an initial value.)

Some types and their literals:

int     39
double  3.5
char    '.'
string  "Annemarie"
bool    true

3.3 Input and type

Initialise your variables.

3.4 Operations and operators

                    bool    char    int     doub    str
assignment          =       =       =       =       =
addition                            +       +
concatenation                                       +
subtraction                         -       -
multiplication                      *       *
division                            /       /
remainder (modulo)                  %
increment by 1                      ++      ++
decrement by 1                      --      --
increment by n                      += n    += n
append                                              +=
decrement by n                      -= n    -= n
multiply & assign                   *=      *=
divide & assign                     /=      /=
remainder & assign                  %=
read s into x       s>>x    s>>x    s>>x    s>>x    s>>x
to s write x        s<<x    s<<x    s<<x    s<<x    s<<x
equals              ==      ==      ==      ==      ==
not equal           !=      !=      !=      !=      !=
greater than        >       >       >       >       >
greater or equal    >=      >=      >=      >=      >=
less than           <       <       <       <       <
less or equal       <=      <=      <=      <=      <=

A compiler knows illegal but not non-sensical operations.

sqrt() not defined for int.

3.5 Assignment and initialization

3.5.1 An example: delete repeated words

while (cin>>current) {...}

Terminate loop with EOF/end of file character:

3.6 Composite assignment operators

3.6.1 An example: count repeated words

Don't start from scratch if possible, use previous work as a base.

3.7 Names

A name starts with a letter and contains only letters, digits or underscores.

Can't be a reserved keyword.

Don't use leading underscores e.g. _foo

Choose meaningful names.

All caps conventionally reserved for macros e.g. __PLUGINPROCESSOR_H_526ED7A9__

Avoid easily confused characters, 0OIl1 etc.

3.8 Types and objects

The meaning of bits in memory is completely dependent on the type used to access it.

3.9 Type safety

A program is type-safe when objects are used only according to the rules for their type.

Again, always initialise variables. (Very few exceptions to this. e.g. a variable we immediately use as the target of an input operation.)

If we have to do something type unsafe, we must do some checking ourselves.

3.9.1 Safe conversions

For a really large int, we can sometimes suffer a loss of precision when converting to double.

3.9.2 Unsafe conversions

By unsafe conversion we mean that a value can be implicitly turned into a value of another type that does not equal the original value. e.g:

int i = 20000;
char c = i;

Such conversions are called 'narrowing' conversions.

Accepted by compiler but unsafe.

C++11 universal and uniform initialisation:

double x {2.7};    // OK
int y {x};         // error: double->int might narrow

Use {} initialisers to avoid conversion accidents.

4 Computation

4.1 Computation

4.2 Objectives and tools

Express computations:

These concerns are ours as soon as we start writing code for others (don't forget 'future you').

Organise by breaking up a problem:

If you can use an existing library (such as the C++ standard library) you can save yourself a lot of work, not just on programming but on testing and documentation.

4.3 Expressions

The most basic building block of programs is the expression, which computes a value from a number of operands.

The simplest expression is a literal value e.g. 10, 'a', 3.14, "Norah"

lvalue and rvalue distinction:

int a = 20;  // lvalue of a: object named a
int b = a*2; // rvalue of a: value of object named a

4.3.1 Constant expressions

Symbolic constant: A named object to which you can't give a new value after it has been initialised. (Also value must be known at compile time.)

constexpr double pi = 3.14159265359

We prefer not to use literals (except very, very obvious ones).

Non-obvious literals in code are derisively referred to as magic constants. Avoid magic constants!

If the value isn't known at compile time use the C++98 style const.

constexpr int c1 = 100;
const int c2 = n+7;     // n not known at compile time
                        // both c1 and c2 are immutable

Variables that are not constant expressions but do not change values after initialisation are in themselves widely useful.

4.3.2 Operators

        Name                    Comment
f(a)    function call           pass a to f as argument
++lval  pre-increment           increment and use new
--lval  pre-decrement           decrement and use new
!a      not                     result is bool
a%b     modulo (remainder)      integer types only
a+b     add
a-b     subtract
o<<b    o output/write b        where o is an ostream
i>>b    i into/read to b        where i is an istream
a<b     less than               result is bool
a<=b    less than or equal      result is bool
a>b     greater than            result is bool
a>=b    greater than or equal   result is bool
a==b    equal                   do not confuse with =
a!=b    not equal               result is bool
a&&b    logical and             result is bool
a||b    logical or              result is bool
lval=a  assignment              do not confuse with ==
lval*=a compound assignment     lval=lval*a also / % + -

lval: Value that can appear on the left hand side of an assignment.

Remember: a<b<c means (a<b)<c not 'Is a between b and c?'

++a is concise and direct.

4.3.3 Conversions


5/2 == 2
2.5/2 == 1.25

One term must be a double if you don't want truncation to int!

List initialisation can help again:

int i2 = d/i;  // i2 == 1
int i3 {d/i};  // error: double->int may narrow

4.4 Statements

Expression statement: expression followed by a ; e.g. i=100;

Watch for non-effecting statement:

a*b; // multiply but don't use result

Watch for empty statement. Very difficult to spot:

if (x==5);  // Eek! Logical error. This will compile.
{ y = 3; }  // ...and this will do nothing

4.4.1 Selection

Always test for bad input.

if statement:

if (unit == 'i')
    cout << "Inches.\n";
    cout << "Sorry, I only know inches.\n";

if's can be nested i.e. if (a) {...} else if (b) {...} else {...}

You don't demonstrate your cleverness by writing the most complex program. Rather, you demonstrate competence by writing the simplest code that does the job.

switch statement:

switch (unit) {
case 'i':
    cout << "Inches.\n";
case 'c':
    cout << "Centimetres.\n";
    cout << "Sorry, I only know inches and centimetres.\n";

Several case labels:

switch (letter) {
case 'a': case 'b': case 'c':
    cout << "First 3 letters";
case 'x': case 'y': case 'z':
    cout << "Last 3 letters";

To select based on a string use an if-statement of a STL map.

Larger switch statements generally yield more efficient code than equivalent if-statements.

Don't forget to terminate with a break;! (The compiler will accept and drop through to the following case!)

4.4.2 Iteration

while statement:

int i=0;
while (i<100) {
    cout << i << '\t' << square(i) << '\n';

\t is a tab character.

Compilers are almost certainly right when they warn about uninitialised variables.


A sequence of statements delimited by { and } is called a block or a compound statement

An empty block is sometimes useful for expressing nothing to be done

if (a<b) {}
else { a = b }

for statements:

for (int i=0; i<100; ++i)
    cout << i << '\t' << square(i) << '\n';

Prefer for over while statements if possible.

Never modify a for loop's variable inside the body of a for statement.

4.5 Functions

int square(int x)
    return x*x;

The syntax of a function definition can be described as:

type identifier ( parameter-list ) function-body

4.5.1 Why bother with functions?

Why not...

void printSquare(int v) { cout ... v*v ... }

printSquare() performs two logical actions, printing and squaring.

Programs are usually easier to write and understand if each function performs a single logical action.

4.5.2 Function declarations

We don't need to look at the function body. C++ provides a way of supplying the information we need separate from the complete function definition: a function declaration

int square(int);
double sqrt(double);

Note terminating ;

If you want to use a function you write—or more commonly #include—its declaration.

4.6 Vector

A vector is a sequence of elements you can access by index.

Indices for a vector always start at 0 and increase by 1.

vector<int> v = {5,9,6,7,8,3};

A vector will only accept elements of its declared type.

someStrings[2] = 99;  // error: trying to assign int...
someInts[4] = "Hume"; // error: trying to assing string

We can define a vector of a given size without specifying element values.

vector<int> v(6);  // vector of 6 ints initialised to 0

You cannot refer to a non-existent element of a vector.

v[20000] = 44;     // run-time error

4.6.1 Traversing a vector

A vector 'knows' its size.

vector<int> v = {5,7,9,4,6,8};
for (int i=0; i<v.size(); ++i)
    cout << v[i] << '\n';

The range for a vector v is [0:v.size()) (the mathematical notation for a half-open sequence of elements) or from 0 to v.size()-1.

Range-for-loop is much simpler and succinct. Use it!

for (int x : v)     // for each x in v
    cout << x << '\n';

4.6.2 Growing a vector

vector<double> v;

Would give the same vector as:

vector<double> v = {2.7,5.6,7.9};

push.back() is a member function call.

member-function-call: object-name.member-function-name ( argument-list )

v.size() is also a member function.

4.6.3 A numeric example

This is good code. Better than a while statement as it limits the scope of temp.

vector<double> temps;
for (double temp; cin>>temp; )

sort(temps);    // standard library sort algorithm

4.6.4 A text example

... // read in some words
if (i==0 || words[i-1]!=words[i]) {
    ... // print out words without repeating any

Note good 'if' construct.

4.7 Language features

5 Errors

5.1 Introduction

We assume your program:

  1. Should produce desired results for all legal inputs
  2. Should give reasonable error messages for all illegal inputs
  3. Need not worry about misbehaving hardware
  4. Need not worry about misbehaving system software
  5. Is allowed to terminate after finding an error

Three approaches to producing acceptable software:

5.2 Sources of errors

5.3 Compile-time errors

5.3.1 Syntax errors

Code lines that are not well formed according to the C++ grammar will be rejected by the compiler.

If you don't see anything wrong with the line the compiler points to, also look at previous lines in the program.

5.3.2 Type errors

The compiler will report mismatches between the types you declared (or forgot to declare) for your variables, functions, etc. and the types of values or expressions you assign to them, pass as function arguments, etc.

5.3.3 Non-errors

As you gain experience you'll begin to wish that the compiler would reject more code.

int a5 = area(10,-7);       // negative area?
int a6 = area(10.7, 9.3);   // truncated doubles?

A program compiling doesn't mean it will run. Even if it does run, it typically gives wrong results at first until you find the flaws in your logic.

A program consists of several separately compiled parts called translation units.

Every function in a program must be declared with exactly the same type in every translation unit in which it is used. (We use header files to ensure that.)

Every function must also be defined exactly once in a program.

Either of these rules being violated the linker will give an error.

Functions with the same name but different types will not give a linker error.

Linkage rules for functions also hold for other entities of a program, such as variables and types: there has to be exactly one definition of an entity with a given name, but there can be many declarations, and all have to agree exactly on type.

5.5 Run-time errors

E.g. a variable leading to a divide by zero will give a hardware-detected error that terminates the program with some cryptic message relating to hardware.

5.5.1 The caller deals with errors

We'd have to choose if function in a library we can't modify.

But this can lead to "brittle" code.

if (z<=2)
    error("non-positive 2nd area() argument");
int ar2 = framed_area(1,z);
// ... and then over and over again for every call of
// framed_area()

Note the magic constant 2. Littering the code with a check before every call leads to brittle code (breaks easily if there's a minor modification e.g. change frame size something other than 2).

5.5.2 The callee deals with errors

int area(int length, int width)
    if (length<=0 || width<=0)
        error("non-positive area() argument");
    return length*width;

Much simpler, only need to put check in one place this way.

Why not always check in function?

So what should you do? Callee or caller check?

Check your arguments in a function unless you have a good reason not to.

5.5.3 Error reporting

5.6 Exceptions

Like most modern languages, C++ provides a mechanism to help deal with errors: exceptions. The fundamental idea is to separate detection of an error (which should be done in the callee) from the handling of an error (which should be done in the caller).

5.6.1 Bad arguments

class Bad_area { };

int area(int l, int w)
    if (l<=0 || w<=0) throw Bad_area{};
    return l*w;

int main()
try {
    int area1 = area(-1,4); // throws Bad_area{}
catch (Bad_area) {
    cout << "Bad argument(s) to area()\n";

5.6.2 Range errors

Subscripting outside a vector's range is so common it's called an off-by-one error, a range error or a bounds error.

int main()
try {
    // ... do some stuff with vectors
    return 0;
} catch (out_of_range) {
    cerr << "Range error\n";
    return 1;
} catch (...) {
    cerr << "Exception: something went wrong\n";
    return 2;

5.6.3 Bad input

int main()
try {
    // ... our program
    return 0;
} catch (exception& e) {
    cerr << "error: << e.what() << '\n';
    return 1;
} catch (...) {
    cerr << "Unknown exception!\n";
    return 2;

When you use error() you'll often want to pass two pieces of information along to describe the problem so we provide:

void error(string s1, string s2)
    throw runtime_error(s1+s2); // concatenate strings

5.6.4 Narrowing errors

Stroustrup's std_lib_facilities.h provides narrow_cast.

int x1 = narrow_cast<int>(2.9);

The <...> brackets are the same as used for vector. They are used when we need to specify a type, rather than a value, to express an idea and are called template arguments.

int x1 = narrow_cast<int>(2.9);     // throws
int x2 = narrow_cast<int>(2.0);     // OK
char c1 = narrow_cast<char>(1066);  // throws
char c2 = narrow_cast<char>(85);    // OK

We use narrow_cast when we need to convert a value and we are not sure "if it will fit".

The word cast means "type conversion".

5.7 Logic errors

Basically, a computer is a fast moron. It does exactly what you tell it to do, and that can be most humbling.


// temperature program
double low_temp = 0.0;
// ... read in some temperatures with cin
for (int x : temps)
    if (x < low_temp) low_temp = x;

Output for dataset 1:

Low temperature: -21.0 F

Output for dataset 2:

Low temperature: 0.0 F

Whoops. Our if statement for assigning the lowest temperature only records a low_temp if it's below 0.0, our (poorly chosen) default. (We've run the program, gotten to the end of the data and recorded no lowest temperature.)


double low_temp = 1000.0;

5.8 Estimation

Unless we have some idea of what the correct answer will be like—even ever so approximately—we don't have a clue whether our result is reasonable.

Always ask yourself:

  1. Is this answer to this particular problem plausible?

You should also ask the more general (and far harder) question:

  1. How would I recognise a plausible result?

Estimation is a noble art that combines common sense and some very simple arithmetic to a few facts.

"On the back of an envelope" is better than in the head as we get less confused this way.

5.9 Debugging

  1. Get the program to compile
  2. Get the program to link
  3. Get the program to do what it's supposed to do

If you consider debugging tedious go to great lengths during design and programming to minimise the amount of time spent hunting for bugs.

How would I know if the program actually worked correctly?

5.9.1 Practical debug advice

Start thinking about debugging before you write the first line of code. Once you have a lot of code written it's too late to try and simplify debugging.

Decide on how to report errors: "Use error() and catch exception in main()" will be most used for this book.

Make the program easy to read so that you have a chance of spotting bugs:

Unless you are a real expert, assume the compiler is always right.

When looking for a bug, carefully follow the code statement by statement from the last point that you are sure it was correct.

A statement that states an invariant is called an assertion or just an assert.

Remember: Messy code easily harbours bugs.

5.10 Pre- and post-conditions

Our suggestion is to always document pre and post conditions in comments (so that a caller can see what a function expects). A function with no comments will be assumed to handle every possible argument value.

But we still need to check too!

5.10.1 Post-conditions

int area(int l, int w)
// calculate area of rectangle
// pre-conditions: l and w are positive
// post-conditions: returns positive value area
    if (l<=0 || w<=0) error("bad arg to area()");
    int a = l*w;
    if (a<=0) error("bad return value from area()");
    return a;

5.11 Testing

"The last bug" is a programmers' joke: there is no such creature; we never find "the last bug" in a large program.

Attitude 1: I'm smarter than any program! I'll break that &%£$ code!

Good testers are worth their weight in gold.

6 Writing a Program

6.1 A problem

6.2 Thinking about the problem

First think about what the problem should do and how you'd like to interact with it. Later, you can think about how the program could be written to do that.

Maybe discuss the problem and how to solve with a friend. Trying to explain something to a friend is a marvelous way of figuring out what's wrong with ideas, even better than writing them down.

Ideally, design isn't a lonely activity.

6.2.1 Stages of development

6.2.2 Strategy

6.3 Back to the calculator!



pseudo code is useful in early stages of design when we're not yet certain wht our notation means.

6.3.1 First attempt

(Kind of works but only reads left-to-right so * and / don't 'bind tighter' than addition.)

6.3.2 Tokens

A token is a sequence of characters that represents something we consider a unit (in our case an operator or a number).

The conventional solution is to represent our tokens as a kind,value pair.

We define a type Token to represent tokens.

Why? Remember why we use types. They hold the data we need and give us useful operations to perform on that data.

6.3.3 Implementing tokens

class Token {
    char kind;
    double value;
};                      // note the trailing ;

Token t;
t.kind = '+';
Token t2;
t2.kind = '8';          // '8' represents kind double
t2.value = 4.5887;

6.3.4 Using tokens

Planning ahead a bit, a function to get tokens and its use:

Token get_token();

vector<Token> tok;

int main()
    while (cin) {
        Token t = get_token();
    // ...


for (int i=0; i<tok.size(); ++i) {
    if (tok[i].kind=='*') {
        double d = tok[i-1].value * tok[i+1].value;
        // ... ermmm now what?

We've found a multiply, we've multiplied the surrounding numbers but where to put the result? Then what do we do to the rest of the expression?

We've hit a dead end. We need to back off, stop programming for a while and think about how we read and understand an input string and evaluate it as an arithmetic expression.

This first enthusiastic attempt to solve the problem ran out of steam. That's not uncommon for first tries and serves to increase our understanding of the problem.

6.3.5 Back to the drawing board

It's important to avoid "feature creep" early in the project. Instead it's best to build a simple version first, implementing the essential features only.

What would an experienced programmer do when faced with a tricky question such as this?

There is often a standard answer. An experienced programmer consults colleagues and/or the literature.

6.4 Grammars

The standard answer is we write a grammar defining the syntax of our input and then write a program that implements the rules of that grammar.

    Expression "+" Term     // addition
    Expression "-" Term     // subtraction
    Term "*" Primary        // multiplication
    Term "/" Primary        // division
    "(" Expression ")"      // bracketing

From our first tentative pseudo-code approach, using tokens and a grammar is actually a huge conceptual jump. It's the kind of jump we hope for but rarely manage without help.

This is what experience, the literature, and Mentors are for.

How do you read a grammar? Given some input you start with the "top rule", Expression and search through the rules to find a match for the tokens as they are read.

Reading a stream of tokens according to a grammar is called parsing and a program that does that is called a parser or a syntax analyser.

6.4.1 A detour: English grammar

6.4.2 Writing a grammar

We need to know how to:

  1. Distinguish a rule from a token.
  2. Put one rule after another (sequencing).
  3. Express alternative patterns (alteration).
  4. Express a repeating pattern (repetition).
  5. Recognise the grammar rule to start with.

Differing notation may refer to tokens as terminals and rules as non-terminals or productions.

6.5 Turning a grammar into code

There are many ways of getting a computer to follow a grammar. We will use the simplest: write one function for each grammar rule and use our type Token to represent tokens.

6.5.1 Implementing grammar rules

Note: Each functions deals with a specific part of an expression and leaves everything else up to other functions: this radically simplifies each function.

Token get_token()       // read chars and compose Tokens
double expression()     // deal with + -
double term()           // deal with * /
double primary()        // deal with numbers and ( )

6.5.2 Expressions

The term recursion is used to describe what happens when a function calls itself. Not all recursions are infinite and recursion is a very useful programming technique.

double expression()
    double left = term();
    Token t = get_token();
    switch (t.kind) {
    case '+':
        return left + expression();
    case '-':
        return left - expression();
        return left;

This actually, more or less works.

But how about 1-2-3?

Unfortunately it will evaluate 1-(2-3)=2 and not (1-2)-3=-4. It will read 1 as a Term then read 2-3 as an Expression (consisting of Term 2 followed by Expression 3). A dangerous situation because it gives the right answer in many cases.

What fundamentally did we do wrong from a programming point of view? We should always ask ourselves this question when we have found an error. That way we might avoid making the same mistake again and again.

Don't look at the code and guess!

Analysing our errors is often the best way to find a correct solution.

It is the wrong grammar:

    Term '+' Expression
    Term '-' Expression

Often the trickiest programming problems come when we must match conventional rules established by and for humans long before we started using computers.

double expression()
    double left = term();
    Token t = get_token();
    while (true) {
        switch (t.kind) {
        case '+':
            left += term();
            t = get_token();
        case '-':
            left -= term();
            t = get_token();
            return left;

6.5.3 Terms

double term()
    double left = primary();
    Token t = get_token();
    while (true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = get_token();
        case '/':
        {   double d = primary();
            if (d==0) error("divide by zero");
            left /= d;
            t = get_token();
            return left;

Why {} block for division handling statements? The compiler insists.

If you want to define and initialise variables in a switch statement, you must place them in a block.

6.5.4 Primary expressions

double primary()
    Token t = get_token();
    switch (t.kind) {
    case '(':
        {   double d = expression();
            t = get_token();
            if (t.kind!=')') error("')' expected");
            return d;
    case '8':
        return t.value;
        error("primary expected");

6.6 Trying the first version

1 2 3 4+5 6+7 8+9 10 11 12

The program "eats" some of our input without evaluating it.

When the token returned by get_token() is not a + or a - we just return. We don't use that token and we don't store if for use by another function later. Let's put the token back into the input stream to be used by another function.

istream has putback() for char's so lets make a similar situation for tokens.

So assume we have a stream of tokens—a Token_stream—called ts. Assume further that a Token_stream has a member function get() that returns the next token and a member function putback(t) that puts a token t back into the stream.

double expression()
    double left = term();
    Token t = ts.get();
    while (true) {
        switch (t.kind) {
        case '+':
            left += term();
            t = ts.get();
        case '-':
            left -= term();
            t = ts.get();
            return left;

double term()
    double left = primary();
    Token t = ts.get();
    while (true) {
        switch (t.kind) {
        case '*':
            left *= primary();
            t = ts.get();
        case '/':
        {   double d = primary();
            if (d==0) error("divide by zero");
            left /= d;
            t = ts.get();
            return left;

double primary()
    Token t = ts.get();
    switch (t.kind) {
    case '(':
        {   double d = expression();
            t = ts.get();
            if (t.kind!=')') error("')' expected");
            return d;
    case '8':
        return t.value;
        // no ts.putback() primary uses every token
        error("primary expected");

6.7 Trying the second version

2 3 4 2+3 2*3

Correct answers but where's the final 2*3=6?

The result seems not to be printed immediately but postponed until it sees the first token of the next expression.

Let's add a print command ;. And while we're at it, an quit command q.

int main()
try {
    double val = 0;
    while (cin) {
        Token t = ts.get();

        if (t.kind=='q') break;
        if (t.kind==';')
            cout << "=" << val << '\n';
        val = expression();
} // ... catch etc.


At this point we have a good initial version of the calculator. It's not quite what we really wanted, but we have a program that we can use as a base for making a more acceptable version. Importantly, we can now correct problems and add features one by one while maintaining a working program as we go along.

6.8 Token streams

We need a stream that produces a token when we ask for one using get() and where we can put a token back into the stream using putback().

We define the type Token_stream.

class Token_stream {
    Token get();
    void putback(Token t);
    // implementation details

The public interface should contain (only) what the user needs, which is typically a set of functions. The private implementation contains what is necessary to implement those public functions, typically data and functions dealing with messy details that user need not know about and shouldn't directly use.

Why the relatively verbose putback name rather than put? We wanted to emphasise the asymmetry between it and the get() function, this is an input stream not something you can also use for general purpose output. Also istream has a putback(): consistency for an equivalent function helps people remember and helps people avoid errors.

6.8.1 Implementing Token_stream

To simplify, let's say we can put back one token at a time. That happens to be sufficient for our program (and for many, many similar programs). That way we just need space for one token and an indicator of whether it's full or empty.

class Token_stream {
    Token get();
    void putback(Token t);
    bool full (false);
    Token buffer;   // where we store token to putback

void Token_stream::putback(Token t)
    buffer = t;
    full = true;

When defining a member of a class outside of the class definition we use the notation:

class-name :: member-name

Why outside? For clarity: the class definition (primarily) states what the class can do. Member function definitions are implementations that specify how things are done. We keep them separate so they don't distract.

Our ideal is to have every logical entity in a program fit on one screen.

void Token_stream::putback(Token t)
    if (full) error("putback() into a full buffer");
    buffer = t;
    full = true;

6.8.2 Reading tokens

Token Token_stream::get()
    if (full) {
        full = false;
        return buffer;
    char ch;
    cin >> ch;      // note >> skips whitespace for char

    switch (ch) {
    case ';':       // print
    case 'q':       // quit
    case '(': case ')': case '+':
    case '-': case '*': case '/':
        return Token(ch);
    case '.':
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
    {   cin.putback(ch);
        double val;
        cin >> val;
        return Token('8',val);
        error("Bad token");

6.8.3 Reading numbers

We (somewhat arbitrarily) chose 8 to represent the 'kind' attribute of a number.

Please note how we again and again avoid doing complicated work and instead find simpler solutions—often relying on library facilities. That's the essence of programing: the continuing search for simplicity. Sometimes that somewhat facetiously expressed as, "Good programmers are lazy." In that sense (and only in that sense), we should be "lazy": why write a lot of code when we can find a way of writing far less?

6.9 Program structure

It is easy to lose sight of the program when looking at all the functions, classes etc. So let's look with the details omitted:

#include "std_lib_facilities.h"

class Token {...};
class Token_stream {...};

void Token_stream::putback(Token t) {...}
Token Token_stream::get() {...}

Token_stream ts;
double expression()         // forward declare

double primary() {...}
double term() {...}
double expression {...}

int main() {...}

The order of declarations is important. You can't use a name before it was declared.

In the call graph there is an interesting loop, expression() calls term() which calls primary() which calls expression().

We need at least one declaration that isn't also a definition. We choose expression() and we "forward declare" it before the others (then define it last of the three).

Overall does this program work? In a way. Does it work in a way that we like? Not really. But it has been good enough for its main purpose which is to be something we can verify our basic ideas and get feedback from.

7 Completing a Program

7.1 Introduction

When your program first starts running reasonably you're about halfway finished. For a large program, or one that could do harm if it misbehaved, you will be nowhere near halfway finished.

7.2 Input and output

We can't think of everything all the time, so when we stop to reflect we find that we have forgotten something.

We would like a short prompt, maybe >

But this gives strange output for multiple expressions on a single line. We will have to modify Token_stream.

For now we decide what we have is good enough. It is unwise to make major structural changes to gain a minor advantage (and we haven't thoroughly tested the calculator yet).

7.3 Error handling

The first thing to do with a program that "basically works" is to try and break it; that is, we try to feed it input in the hope of getting it to misbehave. (We say "hope" because the challenge here is to find as many errors as possible.)

Try some "unreasonable" inputs too.

7.4 Negative numbers

We can't handle something like -1/2 without writing (0-1)/2.

Finding such problems during late debugging and testing is common. Only now do we have the opportunity to see what our design really does and get the feedback that allows us to refine our ideas.

When planning a project, it is wise to try to preserve time and flexibility to benefit from the lessons we learn here.

We modify grammar to allow unary minus (and plus while we're at it)

    "(" Expression ")"
    "-" Primary
    "+" Primary

Code in primary() becomes:

case '-':
    return - primary();
case '+':
    return primary();

7.5 Remainder: %

Remember we removed this from our calculator because remainder is only defined for integers.

Should we use the floating-point version of modulo provided by <cmath>'s fmod()? (<cmath> provides standard mathematical functions inc. sqrt(), log(), etc.)

Or should we allow modulo only if we are dealing with integer floating-points i.e. numbers with no fractional part? (using narrow_cast<int>() from std_lib_facilities.h)

For us, either solution will do.

7.6 Cleaning up the code

We have made changes. They are, we think, all improvements, but the code is beginning to look messy. Now is a good time to review the code and see if it can be made clearer and shorter, add and improve comments, etc.

We are not finished with the program until we have it in a state suitable for someone else to take over maintenance.

7.6.1 Symbolic constants

The use of '8' to represent floating-point literal's kind is actually a magic constant. Lets give it a symbolic name:

const char number = '8';

and replace '8' in our code with number. (JF: Maybe constexpr would be better for this purpose?)

We should not say in comments what can clearly and directly be said in code.

Repeated comments explaining something are often an indication that the code should be improved.

Let's also:

const char quit = 'q';
const char print = ';';
const string result = "=";

Note that this facilitates a change only in one part of the code should we wish to use different characters/strings.

7.6.2 Use of functions

Looking at main() we notice that it does two logically separate things:

  1. Provide general "scaffolding": start/end program, handle fatal errors etc.
  2. Handle the calculation loop.

Ideally we want a function providing the single logical action calculate() so we make one and main() looks like:

int main()
try {
    return 0;
//... error catches etc.

7.6.3 Code layout

We also find a very ugly switch statement all on one line which we tidy and change but keep it fitting on one screen if possible. (Bugs can easily lurk off-screen!)

When we clean up code, we might accidentally introduce errors. Always retest the program after cleanup. Better still, do a bit of testing after each set of minor improvements so that if something went wrong you can still remember exactly what you did.

Remember: Test early and often.

7.6.4 Commenting

See if the comments you originally wrote are:

  1. Still valid.
  2. Adequate for a reader (not you).
  3. Not so verbose that they distract from the code.

Remember: What is best said in code should be said in code.

Avoid comments that explain what is already perfectly clear to someone who knows the programming language.

Comments are for things that code expresses poorly. An example is intent: code says how to do something, not what you want to be done.

For our calculator it's a good idea to include the grammar we're working to.

7.7 Recovering from errors

Why do we exit when we find an error? (We often make little typing errors and would like to continue.)

What would "clean up the mess" entail? Basically, getting ready to compute again after an error has been handled means making sure that all our data is in a good and predictable state.

7.8 Variables

This is the kind of extension that we should not embark on without good reason and sufficient time.

7.8.1 Variables and definitions

The mechanism for keeping track of Variable's is what is often called a symbol table and could be radically simplified if we used the standard library's map.

7.8.2 Introducing names

if (isalpha(ch)) {...}

is part of the standard library.


class Token {
    char kind;
    double value;
    string name;               // for our calc Variables
    Token(char ch) :kind{ch} {}
    Token(char ch, double val) :kind{ch}, value{val} {}
    Token(char ch, string n) :kind{ch}, name{n} {}

Constructors add an important degree of control and flexibility to initialisation.

7.8.3 Predefined names

7.8.4 Are we there yet?

Not really. We have made so many changes we need to test everything again, clean up the code and review the comments.

Implementing variables was a major extension. It touched just about every function and added a completely new concept to the calculator. It increased the size of the calculator by 45%!

If we're making changes that will add about 50% to the program in terms of size and complexity then it is more like writing a new program based on the previous one, and should be treated as such.

Remember to build in small stages, testing each stage. This will leave you far better off than trying a large chunk at once.

8 Technicalities: Functions, etc.

8.1 Technicalities

Remember, what matters are ideas and how those ideas can be expressed in code, not the individual language features (don't become a language lawyer!).

Keeping this in mind appears to be amazingly difficult. Many programmers come to care passionately about minor language details. In particular, too many get the mistaken belief that the way to do something in their first programming language is "the one true way". Avoid this trap! (C++ is nice but not perfect like any other language.)

8.2 Declarations and definitions

A declaration is a statement that introduces a name into a scope.

Before a name can be used it must be declared.

In real-world programs, most declarations are contained in headers.

A declaration that also fully specifies the entity declared is called a definition.

int a = 7;
vector<double> v;
double sqrt(double d) {/*...*/}

Declarations that are not definitions:

double sqrt(double);
extern int a;

All definitions are declarations also, but what we usually mean by 'declaration' is a declaration that doesn't define (even though it's slightly sloppy terminology).

In particular, a definition of a variable sets aside memory for that variable. (So you can't define twice!)

You can declare as often as you want as long as your consistent (e.g. with your return types, arguments etc.)

By the way extern forces a declaration rather than definition, it is rarely useful and we recommend that we don't use it in your code.

Why both declarations and definitions? The distinction between the two reflects the fundamental distinction between what we need to use something (an interface) and what we need for that something to do what it is supposed to do (an implementation). Also, the distinction allows us to split the program into many parts that can be compiled separately.

8.2.1 Kinds of declarations

We can define:

(These are the most interesting.)

8.2.2 Variable and constant declarations

Don't forget constants require an initialiser. (How could it be a constant if it didn't have a value?)

Again, it is almost always a good idea to initialise variables also; an unitialised variable is a recipe for obscure bugs.

We have preference for the { } initialiser syntax. It is the most general and most explicitly says 'initialiser'. (Except we use ( ) for specifying the number of elements in a vector.)

8.2.3 Default initialization

The mechanism for guaranteeing default initialisation is called a default constructor.

8.3 Header files

A header is a collection of declarations, typically defined in a file, so a header is also called a header file. We then #include these headers in our source files.

For example for our calculator we could have:


// declarations
class Token { /*...*/ };
class Token_stream { /*...*/ };


#include "token.h"
void Token_stream::putback(Token t)
    // ...
// etc. ...


#include "token.h"
// uses
Token_stream ts;
// ...
// etc. ...

Since includes happen before anything else a compiler does, handling them is part of what is called preprocessing.

A header will typically be included in many source files. That means that a header should only include declarations that can be duplicated in several files (such as function declarations, class definitions, and definitions of numeric constants).

8.4 Scope

A scope is a region of program text. A name is declared in a scope and is valid (is "in scope") from the point of its declaration until the end of the scope in which it was declared.

An arithmetic if or conditional expression:

int greater = (a>b) ? a : b;
// is a greater than b? return a. (else b)

With the notable exception of global scope, a scope keeps names local. For most purposes, locality is good, so keep names as local as possible.

The larger the scope of a name is, the longer and more descriptive its name shoud be.

The main reason for avoiding global variables it that it is hard to know which functions modify them.

Most C++ constructs that define scopes nest:

Remember, hard to read code usually hides bugs.

8.5 Function call and return

Functions are the way we represent actions and computations. Whenever we want to do something that is worthy of a name, we write a function.

8.5.1 Declaring arguments and return type

double f(int a, double d);                // declaration
double f(int a, double d) { return a*d; } // definition

void g(int level);  // 'void' doesn't return a value

In declarations, formal arguments are not logically necessary, just very useful for writing good commments.

int my_f(vector<string> vs, string s, int hint);

The compiler will accept the less descriptive:

int my_f(vector<string, string, int); // not preferred

If later we realise that callers of a function aren't using a feature that relies on the last argument(s) like 'hint' in this find function, we can just leave that/those arguments unused

int my_f(vector<string> vs, string s, int hint)
                                // 3rd argument unused
    // ... find implementation but don't implement hint

8.5.2 Returning a value

A function declared to return a value must return a value. (In particular it is an error to fall through the end of a function.)

8.5.3 Pass-by-value

Passes a copy.

int f(int x) {...}

8.5.4 Pass-by-const-reference

But what if the value is large? Say an image or a long string? Copying then can be costly. (We should not be obsessed by cost but more we should express our ideas succinctly.)

void print(const vector<double>& v) {...}

We do not copy v here but pass an immutable reference to the original v, on to our function print().

8.5.5 Pass-by-reference

void init(vector<double>& v)
    // ... initialise vector directly

References can also be useful as shorthand:

vector< vector<double> > v;     // 2D vector
// ...
double val = v[f(x)][g(y)];

What if we needed to both read from and write to v[f(x)][g(y)]?

double& var = v[f(x)][g(y)];
var = var/2+sqrt(var);

Pass-by-reference is clearly a very powerful tool: we can have a function operate directly on any object to which we pass a reference.

8.5.6 Pass-by-value vs. pass-by-reference

Our rule of thumb is:

  1. Use pass-by-value to pass very small objects i.e. a couple of integers or doubles
  2. Use pass-by-const-reference to pass large objects that you don't need to modify
  3. Return a result instead of modifying an object through a reference
  4. Use pass-by-reference only when you have to

Why ever use pass-by-reference?

When we see a pass-by-reference argument, we assume that the function changes its value, that is, not only that it can change the argument's value but that it will.

8.5.7 Argument checking and conversion

The call f(y) is legal whenever the initialisation T x = y; is i.e. y doesn't have to be type T it just has to either be type T or implicitly convert to type T.

Conversions are often useful, but occasionally they give surprising results so we have to be careful e.g. passing a double to an function that requires an integer is rarely a good idea.

8.5.8 Function call implementation

When a function is called, the language implementation sets aside a data structure containing a copy of all its parameters and local variables

> Call of expression()  ts
                        (implementation stuff)

This is a function activation record. expression() then calls term() and the stack grows "downward" (in our diagram)

> Call of expression()  ts
                        (implementation stuff)
> Call of term()        ts
                        d       // only if we divide
                        (implementation stuff)

Now term() calls primary(), which calls expression

> Call of expression()  ts
                        (implementation stuff)
> Call of term()        ts
                        d       // only if we divide
                        (implementation stuff)
> Call of primary()     ts
                        d       // only if we divide
                        (implementation stuff)
> Call of expression()  ts
                        (implementation stuff)

Last expression() gets own activation record separate from the initial one.

Each time we call a function the stack of activation records, call stack or just, stack grows by one record.

When the functions finish, the stack shrinks by the rule, last-in-first-out (LIFO).

8.5.9 constexpr functions

A function represents a calculation and sometimes we want to do a calculation at compile time.

constexpr double xscale = 10;
constexpr double yscale = 0.8;

constexpr Point scale(Point p)
    return {xscale*p.x,yscale*p.y};

It must be simple: C++11 a single return statement, C++14 simple loops allowed.

8.6 Order of evaluation

When this "thread of execution" reaches the definition of a variable, the variable is constructed; that is, memory is set aside for the object and the object is initialised. When the variable goes out of scope, the variable is destroyed; that is, the object it refers to is in principle removed and the compiler can use its memory for something else.

8.6.1 Expression evaluation

If you change the value of a variable in an expression, don't read or write it twice in that same expression.

v[i] = ++i;     // don't!
v[++i] = i;     // order of evaluation undefined

Unfortunately not all compilers warn about this!

8.6.2 Global initialization

Using a global variable in anything but the most limited circumstances is usually not a good idea.


const Date& default_date()
    static const Date dd(1970,1,1);
    return dd;

static initialises only the first time the function is called so there is no initialisation overhead for each subsequent call.

8.7 Namespaces

Blocks organise within a function. Classes organise functions, data and types into a type. They both:

To organise classes, functions, data and types into a named part of a program we use a namespace.

namespace Graph_lib {
    struct Color {...};
    struct Shape {...};
    struct Line : Shape {...};
    struct Text : Shape {...};
    // ...
    int gui_main() {...}

This allows people to create and use libraries with less chance of name clashing.

We use fully qualified names to refer to the functions and types e.g. Graph_lib::Shape, Graph_lib::gui_main() etc.

8.7.1 using declarations and using directives

Include standard library facilities:


Use shorthand name instead of fully qualified:

using std::string;
using std::cout;

Use shorthand names for full namespaces:

using namespace std;

We usually see:

using namespaces std;

It is usually a good idea to avoid using directives for any namespace except for a namespace such as std which is extremely well known in an application area.

9 Technicalities: Classes, etc.

9.1 User-defined types

The standard library types can be considered user-defined types as they are built from the same primitives as are available to us.

Types are good for directly representing ideas in code as a data structure plus a set of functions.

C++ provides two kinds of user-defined types: classes and enumerations (classes being the most general and important).

9.2 Classes and members

A class is a user-defined type. It is composed of built-in types, other user-defined types, and functions. The parts used to define the class are called members (a class has zero or more members).

We use the object.member notation.

X var;
var.m = 7;
int x = var.f(9);

Read as "var's m" etc.

9.3 Interface and implementation

class X {
    // public members (interface)
    // private members: (implementation)

Remember the trailing ;

Class members are private by default.

Remember if we're dealing with just data, "plain old data" (e.g. a collection of integers for which any integer value is valid), then there's no need to separate public and private. We use struct:

struct X {
    int a;
    int b;
    int c;
    // ...

struct's are used when we can't define any meaningful invariant. (JF: The data can take on any value that the types allow.)

9.4 Evolving a class

9.4.1 struct and functions

Whenever we define a type, we want some operations for it so we ask, "which operations?"

9.4.2 Member functions and constructors

Our simple struct effort leads to functions such as add_day() that generate bad data such as the 32nd day of a month. We need an initialisation function that can't be forgotten and operations that are less likely to be overlooked.

A member function with the same name as the class is special: a constructor. Used for initialisation of objects of the class.

We can initialise like this:

Date last {2000,12,31};         // most succinct
Date next = {2014,2,14};
Date xmas = Date{1976,12,25};
Date ninetyeight(1998,1,1);     // C++ 98 style

9.4.3 Keep details private

As long as we leave the representation (data) accessible to everone, someone—by design or accident—will do something that produces invalid state, which leads to a run-time error or—usually worse—a bad result.

We try to design our types so that values are guaranteed valid:

A rule for what constitutes a valid value is called an invariant.

(If we can't think of a good invariant, we're probably dealing with plain-ol'-data.)

9.4.4 Defining member functions

class Date {
    Date(int y, int m, int d);
    void add_day(int n);
    int y, m, d;

// constructor
Date::Date(int yy, int mm, int dd)
    :y{yy}, m{mm}, d{dd}

// member function
void Date::add_day(int n)

We prefer defining outside of class declaration to keep interfaces clean and clear.

A member can refer to a function or data member independantly of where it was declared (rule of declaration before use is relaxed within class scope).

We can define inside the class declaration—or inline—if a function contains only one or two expressions.

Inline functions:

Rule of thumb: Don't put member function bodies in the class declaration unless you know that you need the performance boost.

9.4.5 Referring to the current object

How does Date::month() know to return the value of d1.m versus d2.m? A class member function has an implicit argument which it uses to identify the object for which it is called.

9.4.6 Reporting errors

    class Invalid {};   // used as exception

We put testing of validity into a separate is_valid() function because this is a separate logical action (also facilitates multiple constructors).

9.5 Enumerations

enum class also known as scoped enumerations (introduced in C++11):

enum class Month {
    jan=1, feb, mar, apr, may, jun,
    jul, aug, sep, oct, nov, dec

Month m = Month::feb;

If we don't initialise first enumerator, the count starts at 0.

Month is separate from its "underlying type" int.

We cannot define a constructor to check initialiser values for enumerations. We can write a simple check function:

Month int_to_month(int x)
    if (x<int(Month::jan) || int(Month::dec)<x)
        error("bad month");
    return Month(x);

Month mm = int_to_month(y);

An enumeration is useful for sets of related named integer constants e.g. up/down, yes/no/maybe, on/off, n/s/e/w, stop/go etc.

JF: Enum trick where you need a total amount, put it last:

enum class Params {
    // 0      1      2       3      total=4
    gain, drive, shape, bypass, totalParams

9.5.1 "Plain" enumerations

enum Month {
    jan=1, feb, mar, apr, may, jun,
    jul, aug, sep, oct, nov, dec

"Plain" enums are less strict than enum classes, they can pollute the scope which can be convenient but mostly lead to surprises.

Prefer simpler and safer enum classes.

9.6 Operator overloading

You can only overload operators provided by C++.

An overloaded operator must have at least one user-defined type as operand.

It is a good idea not to overload operators unless you are really certain it makes a positive change to the code.

Define operators only with their conventional meaning.

The most interesting operators to overload aren't +, -, * and / but =, ==, !=, <, [] (subscript) and () (call).

9.7 Class interfaces

Keep the interface as small as possible, but no smaller.

9.7.1 Argument types

Use :: after the name of a class, enumeration or namespace and . after an object name.

When we have a choice we catch errors at compile time rather than run time. Prevents from having to figure out where in the code the problem occured, also doesn't require checking code to be compiled and executed.

When we program we have to ask ourselves what is good enough for a given application. We usually don't have the luxury of searching for the "perfect" solution after we have found one that is good enough. Doing so we might come up with something so elaborate that it's actually worse than the original solution...

This is one meaning of the saying, "The best is the enemy of the good" (Voltaire).

9.7.2 Copying

The default case for copying is just to copy all data members.

cout << Date{1978, Month::dec, 24};

Using a constructor like this allows us to use our user-defined types as "literals".

If we don't want this default behaviour we can define our own copy behaviour or delete the copy constructor and copy assignment.

9.7.3 Default constructors

Repeat: Uninitialised variables can be a serious source of errors.

For a type T, T{} is the notation for a default value, as defined by the default constructor. These are equivalent:

string s = string{};    // verbose
string s;               // preferred

Default values in constructor:

    :y{2001}, m{Month::jan}, d{1}

Or default values as initialised data members:

class Date {
    int   y {2001};
    Month m {Month::jan};
    int   d {1};

This way the default values are available to every constructor.

Or we could also set up a constant default date using a helper function and a constructor:

const Date& default_date()
    static Date dd {2001,Month::jan,1};
    return dd;


Remember for vector we use () to specify element counts rather than {} initiliser list notation.

9.7.4 const member functions

Classify operations on classes as modifying or non-modifying and use const to denote non-modifying.

class Date {
    int   day()   const;    // don't modify data members
    Month month() const;
    int   year()  const;

    void add_day(int n);    // modify data members
    void add_month(int n);
    void add_year(int n);

9.7.5 Members and “helper functions”

When we design our interfaces to be minimal but complete, we have to leave out lots of operations that are merely useful.

Helper functions are also called convenience functions, auxiliary functions etc.

Helper functions don't directly access the representation.

If we can easily implement a function freestanding and outside of the class then it probably should be.

We often group helper functions in a namespace.

== and != operator overloads are typical helper functions.

9.8 The Date class


namespace Chrono {

enum class Month {
    jan=1, feb, mar, apr, may, jun,
    jul, aug, sep, oct, nov, dec

class Date {
    class Invalid { };

    Date(int y, Month m, int d);
    // default copy operations are fine

    int   day()   const;
    Month month() const;
    int   year()  const;

    void add_day(int n);
    void add_month(int n);
    void add_year(int n);
    int y;
    Month m;
    int d;

bool is_date(int y, Month m, int d);
bool leapyear(int y);

bool operator==(const Date& a, const Date& b);
bool operator!=(const Date& a, const Date& b);

ostream& operator<<(ostream& os, const Date& d);
istream& operator>>(istream& is, Date& dd);

}   // Chrono


namespace Chrono {

// member function definitions:

Date::Date(int yy, Month mm, int dd)
    : y(yy), m(mm), d(dd)
    if (!is_date(yy,mm,dd)) throw Invalid();

Date& default_date()
    static Date dd(2001,Date::jan,1);
    return dd;

void Date::add_day(int n)

void Date::add_month(int n)
void Date::add_year(int n)
    if (m==feb && d==29 && |leapyear(y+n) {
        m = mar;   // use March 1 instead of February 29
        d = 1;

// helper functions:
bool is_date(int y, Date::Month m, int d)
    // assume that y is valid
    if (d<=O) return false; // d must be positive
    int days_in_month = 31; // most months have 31 days

    switch (m) {
    case Date::feb:     // the length of February varies
        days_in_month = (leapyear(y))? 29 :28;
    case Date::apr: case Date::jun:
    case Date::sep: case Date::nov:
        days_in_month = 30;     // the rest have 30 days
    if (days_in_month<d) return false;

    return true;

bool leapyear(int y)
    // see exercise 10

bool operator==(const Date& a, const Date& b)
    return a.year()==b.year()
        && a.month()==b.month()

bool operator!=(const Date& a, const Date& b)
    return !(a==b);     // elegant use of prec function

ostream& operator<<(ostream& os, const Date& d)
return os<<'('<< d.year()
         <<','<< d.month()
         <<','<< <<')';

istream& operator>>(istream& is, Date& dd)
    int y, m, d;
    char chl, ch2, ch3, ch4;
    is >> ch1 >> y >> ch2 >> m >> ch3 >> d >> ch4;
    if (!is) return is;
    if (ch1!='(' || ch2!=',' || ch3!=',' || ch4!=')') {
        return is;

    return is;

enum Day {
    sunday, monday, tuesday, wednesday,
    thursday, friday, saturday
Day day_of_week(const Date& d) {
Date next_Sunday(const Date& d) {
Date next_weekday(const Date& d) {

} // Chrono

Part II Input and Output

10 Input and Output Streams

10.1 Input and output

10.2 The I/O stream model



10.3 Files

To read a file we must

  1. Know its name
  2. Open it (for reading)
  3. Read in the characters
  4. Close it (though typically done implicitly)

To write a file we must

  1. Name it
  2. Open it (for writing) or create a new file of that name
  3. Write out our objects
  4. Close it (though typically done implicitly)

10.4 Opening a file

An ifstream is an istream for reading a file, an ofstream is an ostream for writing a file.

When a file stream goes out of scope its associated file is closed. When a file is closed its associated buffer is "flushed"; that is, the characters from the buffer are written to the file.

It's usually best to open files early in a program before any serious computation takes place.

Opening the file implicitly as part of the creation of an ostream or istream and relying on the scope of the stream to take care of closing the file is the ideal.

Don't forget to test a stream after opening it.

10.5 Reading and writing a file

10.6 I/O error handling

Stream states

The distinction between fail() and bad() is not precisely defined.

In general, if its a simple format error the stream fail()s, and possibly recoverable. If something nasty like a bad disk read happens, the stream goes bad() and it's assumed nothing can be done except abandon the stream.

Don't forget EOF character:

To recover we explicitly take the stream out of fail() so that we can look at characters again, using clear() (which returns the state to good()).

clear() and ios_base::failbit

if ( {
    ist.clear()     // clear stream state

    char c;
    if (c != terminator) {
        ist.unget();    // put that char back
                        // set stream state to fail

clear() on its own clears the state but with an argument it sets the any mentioned flags and clears all others.

Since we have cleared the state to be able to examine the character, we then need to set back to fail() using ist.clear(ios_base::failbit).

We can handle all cases of bad() (throw exception when bad()) by using one line of code for that istream:

ist.exceptions(ist.exceptions() | ios_base::badbit);

Meaning from that statement ist will throw an exception if it goes bad(). Allowing us to simplify loops by ignoring bad.

10.7 Reading a single value

10.7.1 Breaking the problem into manageable parts

The way to make code clearer is often to separate logically distinct concerns into separate functions.

10.7.2 Separating dialog from function

"Utility functions" that we use in many parts of the program shouldn't have messages "hardwired" into them.

Further, library functions shouldn't write to the user at all.

10.8 User-defined output operators

Even though no single output format is good enough for all uses, it is often a good idea to define << for a user-defined type (to ease early development and debugging by trivially writing out objects).

10.9 User-defined input operators

Defining input operator >> is basically an exercise in error handling and can be quite tricky.

Leaving the target Date unchanged in case of falure to read is the ideal; it tends to lead to cleaner code.

10.10 A standard input loop

10.11 Reading a structured file

We can rarely control the input format of the files we need to read. They are what they are and we just get on with it.

10.11.1 In-memory representation

Peculiar initialisation requirement:

const int not_a_reading = -1;
vector<double> hour {vector<double>(24,not_a_reading)};


vector<double> hour {24,not_a_reading};

...would produce a vector of 2 integer elements, 24 and -1.

When we want to specify the number of elements for a vector for which an integer can be converted to the element type (int to double in this case), we have to use the ( ) initialiser syntax.

10.11.2 Reading structured values

// Example code from Ch10.11.2 "Reading structured
// values"
// "Programming -- Principles and Practice Using C++"
// by Bjarne Stroustrup

#include "std_lib_facilities.h"


const int not_a_reading = -7777;
                            // less than absolute zero
const int not_a_month = -1;


struct Day {
    vector<double> hour;
    Day();    // initialize hours to "not a reading"


Day::Day() : hour(24)
    for (int i = 0; i<hour.size(); ++i)


struct Month {        // a month of temperature readings
    int month;        // [0:11] January is 0
    vector<Day> day;  // [1:31] one set readings per day
    Month()           // (day[0] wasted)
        :month(not_a_month), day(32) { }


struct Year {             // a year of temperature
                          // readings, sorted by month
    int year;               // positive == A.D.
    vector<Month> month;    // [0:11] January is 0
    Year() :month(12) { }   // 12 months in a year


struct Reading {
    int day;
    int hour;
    double temperature;


int month_to_int(string s);
bool is_valid(const Reading& r);
void end_of_loop(istream& ist, char term,
                 const string& message);


istream& operator>>(istream& is, Reading& r)
// read a temperature reading from is into r
// format: ( 3 4 9.7 )
// check format, but don't bother with data validity
    char ch1;
    if (is>>ch1 && ch1!='(') {
        return is;

    char ch2;
    int d;
    int h;
    double t;
    is >> d >> h >> t >> ch2;
    if (!is || ch2!=')') error("bad reading");
                                    // messed up reading = d;
    r.hour = h;
    r.temperature = t;
    return is;


istream& operator>>(istream& is, Month& m)
// read a month from is into m
// format: { month feb ... }
    char ch = 0;
    if (is >> ch && ch!='{') {
                            // we failed to read a Month
        return is;

    string month_marker;
    string mm;
    is >> month_marker >> mm;
    if (!is || month_marker!="month")
        error("bad start of month");
    m.month = month_to_int(mm);

    Reading r;
    int no_of_duplicate_readings = 0;
    int no_invalid_readings = 0;

    while (is >> r)
        if (is_valid(r)) {
            if ([].hour[r.hour]
                != not_a_reading)
  [].hour[r.hour] = r.temperature;
    end_of_loop(is,'}',"bad end of month");
    return is;


const int implausible_min = -200;
const int implausible_max = 200;

bool is_valid(const Reading& r)
// a rough rest
    if (<1 || 31< return false;
    if (r.hour<0 || 23<r.hour) return false;
    if (r.temperature<implausible_min
        || implausible_max<r.temperature)
        return false;
    return true;


istream& operator>>(istream& is, Year& y)
// read a year from is into y
// format: { year 1972 ... }
    char ch;
    is >> ch;
    if (ch!='{') {
        return is;

    string year_marker;
    int yy;
    is >> year_marker >> yy;
    if (!is || year_marker!="year")
        error("bad start of year");
    y.year = yy;

    while(true) {
        Month m;    // get a clean m each time around
        if(!(is >> m)) break;
        y.month[m.month] = m;

    end_of_loop(is,'}',"bad end of year");
    return is;


void end_of_loop(istream& ist,
                 char term,
                 const string& message)
    if ( { // use terminator and/or separator
        char ch;
        if (ist>>ch && ch==term) return;  // all is fine


vector<string> month_input_tbl; // ...[0]=="jan"

void init_input_tbl(vector<string>& tbl)
// initialize vector of input representations


int month_to_int(string s)
// is s the name of a month?
// If so return its index [0:11] otherwise -1
    for (int i=0; i<12; ++i)
        if (month_input_tbl[i]==s) return i;
    return -1;


vector<string> month_print_tbl;    // ...[0]=="January"

void init_print_tbl(vector<string>& tbl)
// initialize vector of output representations


string int_to_month(int i)
// months [0:11]
    if (i<0 || 12<=i) error("bad month index");
    return month_print_tbl[i];


void print_year(ostream& ost, const Year& y)
    ost << y.year << ' ';


int main()
    // first initialize representation tables:

    // open an input file:
    cout << "Please enter input file name\n";
    string name;
    cin >> name;
    ifstream ifs(name.c_str());
    if (!ifs) error("can't open input file",name);

                                      // throw for bad()

    // open an output file:
    cout << "Please enter output file name\n";
    cin >> name;
    ofstream ofs(name.c_str());
    if (!ofs) error("can't open output file",name);

    // read an arbitrary number of years:
    vector<Year> ys;
    while(true) {
        Year y;         // get a freshly initialized
                        // Year each time around
        if (!(ifs>>y)) break;
    cout << "read " << ys.size()
        << " years of readings\n";

    for (int i = 0; i<ys.size(); ++i)
catch (exception& e) {
    cerr << "error: " << e.what() << '\n';
    return 1;
catch (...) {
    cerr << "Oops: unknown exception!\n";
    return 2;


10.11.3 Changing representations

C++ standard library provides a simpler way to implement the month symbol table:


11 Customizing Input and Output

11.1 Regularity and irregularity

As programmers we prefer regularity, imposing a single standard on the way we represent objects, giving the simplest, cleanest, most maintainable code.

However, humans have strong preferences which often we must accommodate.

11.2 Output formatting


cout << 1234 << '\t'        // remember: '\t' is a tab
    << hex << 1234 << '\t'
    << oct << 1234 << '\n';
cout << 1234 << '\n';

// produces: 1234    4d2     2322
//         : 2322

Some manipulators persist or are "sticky" such as above.

oct         use base 8
dec         use base 10
hex         use base 16
showbase    prefix 0 for oct and 0x for hex
noshowbase  don't use prefixes

11.2.1 Integer output

11.2.2 Integer input

11.2.3 Floating-point output

fixed           use fixed point
scientific      use mantissa [1:9] and exponent
defaultfloat    chose either to give most accurate
                representation within current precision

11.2.4 Precision

By default a floating-point value is printed using six total digits.

cout << setprecision(12) << 10.0/3;

11.2.5 Fields

cout << setw(10) << 123456 << "fwd" << '\n';
cout << setw(10) << 654321 << "bwd" << '\n';
// 123456    fwd
// 654321    bwd

setw() is not sticky.

11.3 File opening and positioning

11.3.1 File open modes

ios_base::app       append to end of file
ios_base::ate       open and seek to end ("at end")
ios_base::binary    binary mode (system specific!)
ios_base::in        for reading
ios_base::out       for writing
ios_base::trunc     truncate file to 0 length

Typically, an OS will create a new file if you try to open an non-existent file for output (but fortunately not for input).

Try not to be clever with file open modes. Operating systems don't handle them consistently.

When you can, stick to istreams and ostreams.

11.3.2 Binary files

It's possible to request istream and ostream to simply copy bytes to and from files: binary I/O

// This is example code from Chapter 11.3.2
// "Binary Files" of
// "Programming -- Principles and Practice Using C++"
// by Bjarne Stroustrup

#include "std_lib_facilities.h"


template<class T>
char* as_bytes(T& i)
                // treat a T as a sequence of bytes
    void* addr = &i;
                // get the address of the first byte
                // of memory used to store the object
    return static_cast<char*>(addr);
                // treat that memory as bytes


int main()
    // open an istream for binary input from a file:
    cout << "Please enter input file name\n";
    string name;
    cin >> name;
    ifstream ifs(name.c_str(),ios_base::binary);
                // note: stream mode
                // "binary" tells the stream not to
                // try anything clever with the bytes
    if (!ifs) error("can't open input file ", name);

    // open an ostream for binary output from a file:
    cout << "Please enter output file name\n";
    cin >> name;
    ofstream ofs(name.c_str(),ios_base::binary);
                // note: stream mode
                // "binary" tells the stream not to
                // try anything clever with the bytes
    if (!ofs) error("can't open output file ",name);

    vector<int> v;

    // read from binary file:
    int i;
    while (,sizeof(int)))
        v.push_back(i);         // note: reading bytes

    // ... do something with v ...

    // write to binary file:
    for(int i=0; i<v.size(); ++i)
                                // note: writing bytes
    return 0;
catch (exception& e) {
    cerr << "error: " << e.what() << '\n';
    return 1;
catch (...) {
    cerr << "Oops: unknown exception!\n";
    return 2;


There is no usual << >> operators for binary I/O compared to character I/O.

Binary I/O is messy, somewhat complicated and error-prone. But photos, sound etc. are usually represented as non-character binary so we need to be familiar.

The character I/O provided by default by the iostream library is portable, human readable, and reasonably supported by the type system. Use it when possible and don't mess with binary I/O unless you really have to.

11.3.3 Positioning in files

When you can, read and write files from beginning to end. That's the easiest and least error-prone way. Many times when you have to make a change to a file, the better solution is to produce a new file containing the change.

Use seekg() "seek get" or seekp() "seek put" for reading/writing a specific position.

Be careful, no run-time error checking for positioning.

11.4 String streams

(JF: Think about file streams but strings are used instead of files.)

Access the string like this:

// str() returns string
// c_str() makes it a C-style string required by many
// interfaces

String streams are generally used for tailoring I/O to special needs and tastes.

We usually initialise an istringstream with a string then read characters from that string using input operations.

We usually initialise an ostringstream with an empty string then fill it using output operations.

11.5 Line-oriented input

Remember >> read a certain type until it encounters a different type. Except for strings: reads until whitespace encountered.

To read a full line including whitespace use:

string name;
cout << name << '\n';   // Out: Xaviar Charles Synge III

Again, try to stick to >>, parsing a full line can be error-prone.

11.6 Character classification

if (isdigit(ch)) //...

isspace(c)  whitespace?
isalpha(c)  a letter?
isdigit(c)  decimal digit?
isxdigit(c) hex digit?
isupper(c)  uppercase letter?
islower(c)  lowercase letter?
isalnum(c)  letter or decimal digit?
iscntrl(c)  control character? (ASCII 0-31 & 127)
ispunct(c)  not a letter/digit/whitespace/control?
isprint(c)  printable? (ASCII ' '..'~')
isgraph(c)  isalpha or isdigit or ispunct? (not space)

toupper(c)  returns c's uppercase equivalent
tolower(c)  returns c's lowercase equivalent

Prefer tolower() as some natural languages e.g. German don't have an uppercase equivalent for every letter.

11.7 Using nonstandard separators

Dealing with stream state is always messy and it is often the source of subtle errors that require tedious debugging.

Punct_stream below, behaves like an istream in many ways but it is not a full istream! (We don't yet have the skills!)

// This is example code from Chapter 11.7
// "Using non-standard separators" of
// "Programming -- Principles and Practice Using C++"
// by Bjarne Stroustrup

#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;


class Punct_stream {    // like an istream,
                        // but the user can add to
                        // the set of whitespace
                        // characters
    Punct_stream(istream& is)
        : source(is), sensitive(true) { }

    void whitespace(const string& s)
        { white = s; }  // make s the whitespace set
    void add_white(char c)
        { white += c; } // add to the whitespace set
    bool is_whitespace(char c);
                        // is c in the whitespace set?

    void case_sensitive(bool b) { sensitive = b; }
    bool is_case_sensitive() { return sensitive; }

    Punct_stream& operator>>(string& s);
    operator bool();

    istream& source;    // character source
    istringstream buffer;
                        // let buffer do our formatting
    string white;       // characters considered
                        // "whitespace"
    bool sensitive;     // is the stream case sensitive?


Punct_stream& Punct_stream::operator>>(string& s)
    while (!(buffer>>s)) {    // try to read from buffer
        if (buffer.bad() || !source.good())
            return *this;

        string line;
        getline(source,line); // get a line from source

        // do character replacement as needed:
        for (int i=0; i<line.size(); ++i)
            if (is_whitespace(line[i]))
                line[i]= ' ';
            else if (!sensitive)
                line[i] = tolower(line[i]);

        buffer.str(line);     // put string into stream
    return *this;


bool Punct_stream::is_whitespace(char c)
    for (int i = 0; i<white.size(); ++i)
        if (c==white[i]) return true;
    return false;


Punct_stream::operator bool()
    return !( || source.bad())
           && source.good();


int main()
// given text input, produce a sorted list
// of all words in that text
// ignore punctuation and case differences
// eliminate duplicates from the output
    Punct_stream ps(cin);
        // note \" means " in string (escape char)

    cout << "please enter words\n";
    vector<string> vs;
    string word;
    while (ps>>word) vs.push_back(word);   // read words

                        // sort in lexicographical order
    for (int i=0; i<vs.size(); ++i)
                        // write dictionary
        if (i==0 || vs[i]!=vs[i-1])
            cout << vs[i] << endl;


To become a programmer you need to read code. Not just carefully polished solutions to educational problems either!

11.8 And there is so much more

12 A Display Model

12.1 Why graphics?

12.2 A display model

12.3 A first example

12.4 Using a GUI library

12.5 Coordinates

Remember, y coordinates grow "downward" (origin is top-left of screen).

12.6 Shapes

12.7 Using Shape primitives

12.7.1 Graphics headers and main

12.7.2 An almost blank window

12.7.3 Axis

We usually represent height and width by symbolic constants so that we can refer to things relatively e.g. y_max - bottom_margin (rather than by a magic constant such as 300).

12.7.4 Graphing a function

12.7.5 Polygons

12.7.6 Rectangles

We provide our Rectangle class separate from the Polygon class.

It is important for our reasoning about code that a Rectangle doesn't just happen to look like a rectangle on screen, it maintains the fundamental guarantees of a rectangle as we know them from geometry.

12.7.7 Fill

12.7.8 Text

12.7.9 Images

12.7.10 And much more

// This is example code from Chapter 12.7.10
// "And much more" of
// "Programming -- Principles and Practice Using C++"
// by Bjarne Stroustrup

#include "Simple_window.h"     // for that "Next" button
#include "Graph.h"
#include "std_lib_facilities.h"

using namespace Graph_lib;


int main ()
    Point tl(100,100);  // top-left corner of our window

    Simple_window win(tl,600,400,"Canvas");
    // screen coordinate tl for top-left corner
    // window size(600*400)
    // title: Canvas

    Axis xa(Axis::x, Point(20,300), 280, 10, "x axis");
    // make an Axis
    // an axis is a kind of Shape
    // Axis::x means horizontal
    // starting at (20,300)
    // 280 pixels long
    // 10 "notches"
    // label the axis "x axis"

    win.attach(xa);      // attach xa to the window, win

    Axis ya(Axis::y, Point(20,300), 280, 10, "y axis");


    Function sine(sin,0,100,Point(20,150),1000,50,50);
    // sine curve
    // plot sin() in the range [0:100)
    // with (0,0) at (20,150)
    // using 1000 points;
    // scale x values *50, scale y values *50


    Polygon poly;
            // a polygon, a Polygon is a kind of Shape
            // three points makes a triangle


    Rectangle r(Point(200,200), 100, 50);
                    // top-left corner, width, height

    Closed_polyline poly_rect;


    Text t(Point(150,150), "Hello, graphical world! ");

    Image ii(Point(100,50),"image.jpg"); // 400*212 jpg

    Circle c(Point(100,200),50);
    Ellipse e(Point(100,200), 75,25);
    Mark m(Point(100,200),'x');

    // nice use of a string stream to format the output
    ostringstream oss;
    oss << "screen size: "
        << x_max() << "*" << y_max()
        << "; window size: "
        << win.x_max() << "*" << win.y_max();
    Text sizes(Point(100,20),oss.str());

    Image cal(Point(225,225),"snow_cpp.gif");
                        // 320*240 pixel gif
                        // display center part of image



    win.set_label("Canvas #12");
    win.wait_for_button();               // Display!
catch(exception& e) {
    // some error reporting
    return 1;
catch(...) {
    // some more error reporting
    return 2;


For this main() to compile we need to have exception defined. We get that if we include std_lib_facilities.h or directly with the standard headers and include <stdexcept>.

12.8 Getting this to run

12.8.1 Source files

13 Graphics Classes

13.1 Overview of graphics classes

13.2 Point and Line

Remember, y-coordinates start from 0 at the top of the screen.

struct Line : Shape {...}

Line is a kind of shape or shape is the base class or just, base of line.

13.3 Lines

13.4 Color

13.5 Line_style

Why hide the fact that FLTK uses plain ints to represent line styles? Because this is exactly the kind of detail that might change as the library evolves. (Also, it saves our code from being littered with plain ints.)

Setting defaults is one of the things constructors are good for, and good defaults significantly help users of a class.

13.6 Open_polyline

'Poly' is the Greek word for 'many'. (So there.)

struct Open_polyline : Shape {
    using Shape::Shape; // using Shape's constructors
    void add(Point p) { Shape::add(p); }

The using declaration here allows Open_polyline to use Shape's constructors (remember Shape is an abstract class and it's constructors aren't used directly, but in this case we don't override we just use the constructors provided by Shape with no additional steps).

13.7 Closed_polyline

We only have to do the little detail where Closed differs from Open_polyline. This is important and sometimes called 'programming by difference'.

13.8 Polygon

A polygon is a closed polyline where the lines do not cross.

We implement a check in add() so that with each new point we confirm that the new line doesn't intersect any others (this code is arguably the most complicated in the whole library!).

13.9 Rectangle

Apart from conceptual, a reason why most graphics libraries provide a separate rectangle is the algorithm for determining which pixels are inside is much quicker than for other shapes.

13.10 Managing unnamed objects

A vector type that can hold named and unnamed objects.

template<class T> class Vector_ref {
    // ...
    void push_back(T&); // add a named object
    void push_back(T*); // add an unnamed object

    T& operator[](int i);   // read/write operations
    const T& operator[](int i) const;

    int size() const;

So that you can do both of these:

Point a {10,10};
Point b {90,60};
Rectangle x {a,b};

rect.push_back(x);                      // add named

rect.push_back(new Rectangle {a,b});    // add unnamed

13.11 Text

We provide the initialisers as member initialisers, rather than as part of the constructors' initialiser lists, because the initialisers do not depend on the constructor arguments.

13.12 Circle

13.13 Ellipse

When we design classes we have to be careful not to be too clever and be deceived by our intuition into designing classes that don't make sense as classes in code.

Conversely, we have to make sure our classes represent a fundamental concept and aren't just collections of data members and function members.

Remember, just throwing code together without thinking about the ideas/concepts is "hacking", and leads to code that we can't explain and that others can't maintain.

Again. Remember:

"Others" might be you in a few months time.

13.14 Marked_polyline

13.15 Marks

13.16 Mark

char ch = 'x';
string{1,ch};   // initialise string to contain
                // single character 'ch'

13.17 Images

bool can_open(const string& s)
// check if a file named s exists and can be opened
    ifstream ff(s);
    return ff;

Opening a file and closing it again is a fairly clumsy way of portably separating errors related to "can't open the file" from errors related to the format of the data in the file.

14 Graphics Class Design

14.1 Design principles

14.1.1 Types

Our ideal of program design is to represent the concepts of the application domain directly in code.

We are not defining a set of unrelated classes, so we can't make design decisions for each class in isolation.

So, as ever, we ask what is important to us.

A good library directly and cleanly models its application domain from a particular perspective, emphasising some aspects and deemphasising others.

Rather than have a single, very flexible Shape class, we thing that using many small classes most closely and most usefully models our domain of graphics.

14.1.2 Operations

Our ideal is the minimal interface that allows us to do what we want.

Where we want greater convenience, we can always add nonmember functions, or yet another class.

We want the interfaces of our classes to show a common style.

Logically identical operations across classes have the same name.

This helps us design new classes by "just doing the usual". This is code that is generic.

Getting such details consistent makes surprisingly large difference to the ease of use and the reduction of runtime errors.

14.1.3 Naming

14.1.4 Mutability

When designing a class think, "Who can modify the data?" and "How?".

14.2 Shape

class Shape  {  // deals with color and style,
                // and holds sequence of lines
    Shape() { }
    Shape(initializer_list<Point> lst);
                // add() the Points to this Shape

    void add(Point p){ points.push_back(p); }
    void set_point(int i, Point p) { points[i] = p; }
    void draw() const; // deal with color and draw_lines
    virtual void draw_lines() const;
                    // simply draw the appropriate lines
    virtual void move(int dx, int dy);
                    // move the shape +=dx and +=dy

    void set_color(Color col) { lcolor = col; }
    Color color() const { return lcolor; }

    void set_style(Line_style sty) { ls = sty; }
    Line_style style() const { return ls; }

    void set_fill_color(Color col) { fcolor = col; }
    Color fill_color() const { return fcolor; }

    Point point(int i) const { return points[i]; }
    int number_of_points() const {
        return int(points.size());

    virtual ~Shape() { }    // virtual destructor

    Shape(const Shape&) = delete;   // prevent copying
    Shape& operator=(const Shape&) = delete;
    vector<Point> points;   // not used by all shapes
    Color lcolor {fl_color()};
    Line_style ls {0};
    Color fcolor {Color::invisible};

14.2.1 An abstract class

The constructors are protected which means they can only be used directly from classes derived from Shape (using the : Shape notation).

There purpose here is to make sure we don't make Shape objects directly.

A class is abstract if it can only be used as a base class. Another way to achieve this is called a pure virtual function.

(The opposite of this is called a concrete class.)

14.2.2 Access control

vector<Point> points;
Color lcolor {fl_color()};
Line_style ls {0};

The initialisers for the data members don't depend on the constructor arguments so they are specified in the data member declarations.

x();        // get access function
set_s();    // set access function

The main inconvenience of this style is you can't give the member variable the same name as the function.

As always, chose the most convenient name for the function because this is part of the public interface.

To some, making any data member public is a bad design. To others, this seems overly restrictive because we don't allow direct write access to all members of derived classes.

You might worry about these trivial access functions but they will be "inlined" by the compiler and be just as efficient as direct calls.

14.2.3 Drawing shapes

Defining a function in a derived class so that it can be used through the interfaces provided by a base is called overriding.

14.2.4 Copying and mutability

Prevent copying:

Shape(const Shape&) =delete;
Shape& operator=(const Shape&) =delete;

A Circle has Shape's data members plus a radius. If you used any operation that copies expecting a Shape and passed it a circle the radius would be sliced. Slicing is like narrowing for objects.

Vector's push_back() puts a copy into the vector.

Basically, class hierarchies plus pass-by-reference and default copying do not mix.

When you design a class that is meant to be used as a base class in a hierarchy, disable its copy constructor and copy assignment using =delete as was done here.

(If we then want to copy objects we can write a clone() if this makes sense.)

14.3 Base and derived classes

The use of inheritance, run-time polymorphism and encapsulation is the most common definition of object oriented programming.

14.3.1 Object layout

In memory objects are laid out by their data members and if there's a virtual function call we add a vtbl (for 'virtual table' or 'virtual function table') and its address which is a vptr (for 'virtual pointer').

Basically, code generated for a virtual function call finds its vptr, uses that to get to the right vtbl and calls the appropriate function there (remember this is all at runtime).

The cost is about two memory accesses plus an ordinary function call. Simple and fast.

Virtual functions are not expensive, this is a myth.

14.3.2 Deriving classes and defining virtual functions

struct Circle : Shape {...};    // these are the same
class Circle : public Shape { public: ... };

// but this is probably a mistake, watch for it
class Circle : Shape { public: ... };

A virtual function must be declared virtual in its class declaration.

The definition, if outside of the class (as usual), must not have the keyword virtual.

virtual void Shape::draw_lines() const {...}  // Error!

14.3.3 Overriding

You must use exactly the same name and type in the virtual function for it to override (including const).

We can (and should) explicitly declare that a function is meant to override:

void f() const override { ... }

14.3.4 Access

If a member is:

We ignore the concept of "friend" which is beyond the scope of this book.

14.3.5 Pure virtual functions

Another more common way to make a class abstract is to make one or more of its virtual functions "pure", that is make explicit that they need to be overridden in some derived class:

virtual void f() =0;    // pure virtual function

This means that the function not only can but must be overridden in some derived class.

Unless all pure virtual functions are overridden, the resulting class is still abstract.

Classes with pure virtual functions tend to be pure interfaces: that is, they tend to have no data members (usually found in the derived classes) and consequently have no constructors (so we can't protect: the constructor to make it abstract using the other method).

14.4 Benefits of object-oriented programming

A direct result here is we can add new Shapes to the program without modifying existing code. This is a holy grail of software design/development/maintenance: extension of a system without modifying it.

Interface inheritance is one of the most powerful techniques for designing and implementing systems that are robust in the face of change.

Remember any change to the interface of Shape or change to the layout of its data members neccessitates a recompilation of all derived classes and their users. (For a widely used library such a recompilation can sometimes be infeasible.)

15 Graphing Functions and Data

15.1 Introduction

One part of a programmer's art is to know when to stop and use the time saved on something better (such as new techniques or sleep).

Remember: The best is the enemy of the good (Voltaire).

15.2 Graphing simple functions

15.3 Function

Function is a Shape with a constructor that generates a lot of line segments and stores them in its Shape part.

Fct is a variant of a standard library type std::function (that can 'remember' a function to be called later).

15.3.1 Default arguments

Function(Fct f, double r1, double r2, Point orig,
    int count=100, double xscale=25, double yscale=25);

This is an example of using default arguments and a shortcut against making multiple constructors.

This only works for trailing parameters.

If you find it hard to think of good default arguments, just leave them out and let the user specify.

15.3.2 More examples

15.3.3 Lambda expressions

C++ offers a notation for defining something that acts as a function in the argument position where it is needed. A lambda expression:

Function s5 {[](double x) { return cos(x)+slope(x); },
             r_min, r_max, orig, 400, 30, 30};

(Saving having to name a function then use it.)

The [] is called a lambda introducer, we specify the argument list and the function body. The return type is deduced from the lambda body although if we want we can be explicit about the return type:

Function s5 {
    [](double x) -> double { return cos(x)+slope(x); },
    r_min, r_max, orig, 400, 30, 30

We can allow access to local variables by putting them in the lambda introducer.

for (int n=0; n<50; ++n) {
    Function e {[n](double x) { return expe(x,n); },
        r_min, r_max, orig, 200, x_scale, y_scale};

15.4 Axis

15.5 Approximation

Remember a computer's arithmetic is not pure maths. Floating point numbers are simple as good an approximation to real numbers as we can get with a fixed number of bits.

Actually it was fac() that was producing values that couldn't be stored in an int. Modifying fac() to produce a double solved this problem.

Again: Before giving a program to someone else to use, test it beyond what at first seems reasonable. (Unless you know better, running a progam slightly longer or with slightly different data could lead to a real mess.)

15.6 Graphing data

Note how we read into a temp Distribution and then copy to the actual Distribution after all checks have taken place:

istream& operator>>(istream& is, Distribution& d)
// assume format: ( year : young middle old )
    char ch1 = 0;
    char ch2 = 0;
    char ch3 = 0;
    Distribution dd;

    if (is >> ch1 >> dd.year
        >> ch2 >> dd.young >> dd.middle >> dd.old
        >> ch3) {
            if (ch1!= '(' || ch2!=':' || ch3!=')') {
                return is;
        return is;
    d = dd;
    return is;

Don't be shy about introducing types "just to make code clearer".

15.6.1 Reading a file

15.6.2 General layout

15.6.3 Scaling data

15.6.4 Building the graph

16 Graphical User Interfaces

16.1 User interface alternatives

We feel that GUI is a form of I/O, and separation of the main logic of an application from I/O is among our major ideals for software.

16.2 The “Next” button

When your program wants an action it must:

16.3 A simple window

Basically, "the system" (which is a combination of a GUI library and the operating system) continuously tracks where the mouse is and whether its buttons are pressed or not.

We can ask the system to call one of our functions, a "callback function", when the mouse is clicked "on our button". To do that we must:

Simple window contains a member next_button:

struct Simple_window : Window {
    Simple_window(Point xy,
                  int w,
                  int h,
                  const string& title )
        : Window{xy,w,h,title},

    void wait_for_button()
    // modified event loop
    // handle all events (as per default),
    // but quit when button_pushed becomes true
    // this allows graphics without control inversion
        while (!button_pushed) Fl::wait();
        button_pushed = false;

    Button next_button;

    bool button_pushed;     // implementation detail

    static void cb_next(Address, Address addr)
    // callback for next_button
    //  { reference_to<Simple_window>(addr).next(); }

    void next() { button_pushed = true; }

16.3.1 A callback function

cb_next() is the interesting bit. This is the function that we want the GUI system to call when it detects a click on our button. Commonly called a callback function.

We pass the address of cb_next() and the address of our Simple_window down through the layers of software; some code "down there" then calls cb_next() when the button is pressed.

static void cb_next(Address, Address addr);

The keyword static here makes sure that cb_next() can be called as an ordinary function, that is, not as a C++ member function invoked for a specific object.

(Remember from P.294: static can make sure a local variable is only initialised once, the first time it is called, for re-use on further calls.)

"The system" will invoke a callback function with the first argument being the address of the GUI entity or "Widget" for which the callback was triggered. The second argument is the address of the window containing that "Widget".

We separate the low-level stuff into cb_next() (allows the system to call next()) while next() does what we want to be done.

To recap:

16.3.2 A wait loop

16.3.3 A lambda expression as a callback

For each action on a widget we have to define two functions, the callback and the desired action function.

Consider this constructor:

Simple_window(Point xy,
              int w,
              int h,
              const string& title )
    : Window{xy,w,h,title},
                      [](Address,Address pw) {

16.4 Button and other Widgets

16.4.1 Widgets

16.4.2 Buttons

16.4.3 In_box and Out_box

We didn't bother to provide get_floating_point() or get_complex() etc., because you can just take a string, stick it in a stringstream and do any input formatting you need that way.

16.5 An example

16.6 Control inversion

We have moved the control of the order of execution from the program to the widgets: whichever widget the user activates, runs.

For example, click on a button and its callback runs. When the callback returns, the program settles back, waiting for the user to do something else. Basically, wait() tells "the system" to look out for the widgets and invoke the appropriate callbacks.

A conventional program is organised like this:

Application --Call-> Input function --Prompt-> User responds

A "GUI program" is organised like this:

Application <-Callback-- System <-"Clicks"-- User invokes action

One implication of "control inversion" is that the order of execution is completely determined by the actions of the user.

This complicates both program organisation and debugging. The techniques for dealing with this are beyond the scope of this book but we encourage you to be extra careful with code driven by users through callbacks!

To minimise hassle, it is essential to keep the GUI portion of a program simple and to build a GUI program incrementally, testing at each stage.

When working with a GUI program it is almost essential to draw little diagrams of the objects and their interactions.

16.7 Adding a menu

Basically the Window class is the program.

Note that the initialisers are in the same order as the data member definitions, that's the proper order in which to write initialisers.

16.8 Debugging GUI code

How do you find errors in such a program?

You will find it hard to trace the execution of the code. If you have learned to use the debugger, you have a chance, but just inserting "output statements" will not work in this case (the problem is no output appears).

Even debuggers will have problems because there are several things going on at once ("multi-threading"). Your code is not the only code trying to interact with the screem.

Simplification of the code and a systematic approach to understanding the code is key.

Another common problem is to put one window exactly on top of another (or one shape on another).

Also Shapes and Widgets can sometimes not show because they have gone out of scope and have been destroyed. Use new if you want the object to persist past the scope.

Note: Exceptions don't always work as we would like them to when we use a GUI library. Since our code is managed by the library an exception may never reach the handler.

Part III Data and Algorithms

17 Vector and Free Store

17.1 Introduction

Unless we are content to believe in magic, we must examine the lowest level of memory management.

Also, we need to be able to understand the huge amount of C++ code that directly uses memory.

17.2 vector basics

A pointer is a data type that can hold a memory address.

17.3 Memory, addresses, and pointers

int var = 17;
int* ptr = &var;    // an 'int pointer'
                    // initialised with address of var
                    // (pointing to var)

& is the "address of" operator, unary &.

cout << *ptr << "\n";   // "contents of" ptr

* is the "contents of" or "dereference" operator, unary *.

Our aim is always to work at the highest level of abstraction that is possible given a problem and the constraints on its solution.

17.3.1 The sizeof operator

17.4 Free store and pointers

When you start a C++ program the compiler sets aside memory for:

The remaining memory is potentially available to the program too in the form of:

The "free store" is available through the operator new:

double* p = new double[4];  // array of 4 doubles on
                            // the free store

The new operator returns a pointer to the object it creates. (If it created several it returns a pointer to the first.)

17.4.1 Free-store allocation

Pointers to objects of different types are different types (they do not mix/convert).

17.4.2 Access through pointers

As well as the the * operator we can use the subscript operator [ ]:

double* p = new double[4];
double x = *p;
double y = p[2];
double z = *p[2];   // error. not what you meant?

We can write too with *[]:

*p = 8.8;
p[3] = 3.3;

17.4.3 Ranges

But, continuing our example:

p[10] = 4.4;    // ??? but p only had 4 elements?!
p[-3] = 234.0;  // ??? surely not what we meant?!

The compiler doesn't know that these are silly, we will simple access memory as if we had allocated enough memory.

Remember: An out-of-range write can put some object into an "impossible" state or simply give it a totally unexpected and wrong value. (Such writes typically aren't noticed until long after they occurred making them particularly hard to find.)

We have to ensure out-of-range access doesn't happen. (Prefer vector when you can.)

However, understanding pointers is essential for understanding lots of real world code.

17.4.4 Initialization

As ever, we prefer to initialise an object with a value before we use it.

With pointers, we initialise our pointers and also the objects they point to.

A scary percentage of "old-style C++" programs have serious problems caused by uninitialised pointers and out-of-range access.

Beware compilers debug mode. Ofter variables will be initialised to a predictable value (like 0) in this mode but turning that off, or simply compiling on another system, a program with uninitialised variables can suddenly run differently

17.4.5 The null pointer

If you have no other pointer to use for initialising then use the null pointer: nullptr

double* p0 = nullptr;

We can check for validity using the null pointer:

if (p0 != nullptr)

Or simply:

if (p0)     // same as "if (p0 != nullptr)"

Why the null pointer?

We need to use the null pointer when we have a pointer that sometimes points to an object and sometimes not (e.g. the links in a linked list).

nullptr is new for C++11. Be prepared to see 0 or NULL, but prefer the less error-prone nullptr.

17.4.6 Free-store deallocation

It is usually a good idea to return memory to the free store once we are finished using it.

The operator for returning memory to the free store is called delete.

double* p1 = new double {2.2};
// ...
delete p1;      // notation for individual object

double* p2 = new double[var];
// ...
delete[] p2;    // square brackets delete[] for arrays

Deleting an object twice is a bad mistake (remember we are dealing with memory addresses here, the memory may be in use by something else now).

Deleting the null pointer doesn't do anything and is harmless (because the null pointer doesn't point to anything).

This all can be automated by automatic garbage collection or just garbage collection.

When is it important not to leak memory? A program that needs to run "forever" can't afford any memory leaks e.g. an operating system, some embedded systems etc.

17.5 Destructors

    { delete[] elem; }

Destructors are great for handling resources that we first must acquire and later give back: files, threads, locks, etc.

Every class that "owns" a resource needs a destructor.

17.5.1 Generated destructors

Destructors are called when the object is destroyed (by going out of scope, by delete etc.)

17.5.2 Destructors and free store

Remember Shape had a virtual destructor:

virtual ~Shape() {}

If you have a class with a virtual function, it needs a virtual destructor:

  1. If a class has a virtual function it is likely to be used as a base class and
  2. If it is a base class its derived class is likely to be allocated using new, and
  3. If a derived class object is allocated using new and manipulated through a pointer to its base, then
  4. It is likely to be deleted through a pointer to its base

17.6 Access to elements

Remember: We aim to start small and simple, then grow our programs step by step, testing along the way.

17.7 Pointers to class objects

Because delete invokes destructors (for types that have one) delete is often said to destroy objects, not just deallocate them.

Remember: A naked new outside a constructor is an opportunity to forget to delete the object that new created.

Unless you have a good (i.e. really simple) strategy for deleting objects, try to keep news in constructors and deletes in destructors.

All classes support the operator -> "arrow" for accessing members, given a pointer to an object:

vector* p = new vector(4);  // vector v(4);
int x = p->size();          // int x = v.size();
double d = p->get(3);       // double d = v.get(3);

Similar to . this is also called a member access operator.

17.8 Messing with types: void* and casts

When we are forced to interface with old code that wasn't designed with static type safety in mind we need:

void* means "pointer to some memory that the compiler doesn't know the type of".

A static_cast can be used to explicitly convert between related pointer types such as void* and double*. The name static_cast is a deliberately ugly name for an ugly and dangerous operation.

const_cast can "cast away" const.

Is there a way to write the code without the cast? Unless interfacing with old/awkward code, there usually is a way. If not expect subtle and nasty bugs.

17.9 Pointers and references

A reference can be thought of as an automatically dereference and immutable pointer, or as an alternative name for an object.

Note the last example r = &y2; there is no way to get a reference to refer to a different object after initialisation. If you need to point to something different, use a pointer.

A reference and a pointer are both implemented using a memory address, they just provide different facilities.

17.9.1 Pointer and reference parameters

Consider changing a variable pass into a function:

int incr_v(int x) { return x+1; }
void incr_p(int* p) { ++*p; }
void incr_r(int& r) { ++r; }

We prefer to just return a value (least error-prone), for small objects like ints. If a "large object" has a move constructor (Ch.18) we can efficiently pass it back and forth this way too.

Like references, using a pointer argument indicates something will probably be changed.

If you use a pointer as an argument, the function has to beware that someone might call it with a null pointer.

if (p==nullptr) error("null pointer argument to f()");

So the real rule of thumb:

(Also, remember our other rule of thumb from Ch.8 on pass-by-value vs. pass-by-reference)

17.9.2 Pointers, references, and inheritance

In Ch.14 we have seen how a derived class such as Circle could be used where an object of its public base class Shape was required. We can express that idea in terms of pointers or references: a Circle* can be implicitly converted to a Shape* because Shape is a public base of Circle:

void rotate(Shape* s, int n);

Shape* p = new Circle{Point{100,100},40};
Circle c {Point{200,200{,50};


Similarly for references:

void rotate(Shape& s, int n);

Shape& r = c;


This is crucial for most object-oriented programming techniques.

(JF: Nothing said about "slicing" here. Presumably rotate only alters the Shape attributes of Circle?)

17.9.3 An example: lists

Given a link for a doubly linked list we can find both its predecessor and its successor. A singly linked list has links only to its successor.

We use doubly linked lists when we want to make it easy to remove an element.

When thinking about pointers and linked structures, we invariably draw little box-and-arrow diagrams on paper to verify that our code works for small examples. Please don't be too proud to rely on this effective low-tech design technique. (JF: Do this every time!)

Pointer fiddling is tedious and error-prone, and should be hidden in well-written and well-tested functions.

Many errors in particular come from forgetting to test pointers against nullptr.

Always test for a null pointer.

17.9.4 List operations

17.9.5 List use

17.10 The this pointer

In every member function, the identifier this is a pointer to the object for which the member function was called.

if (this->prev) this->prev->succ = n;

This is a bit verbose, we don't need to mention this to access a member:

if (prev) prev->succ = n;   // equivalent to above

In other words, we have been using this implicitly every time we accessed a member.

It is only when we need to refer to the whole object that we need to mention it explicitly.

18 Vectors and Arrays

18.1 Introduction

We will present the five essential operations that must be considered for every type:

And if a container:

If we want types that provide exactly the properties we want based on logical needs we need to overcome the following basic properties of the hardware (via C):

18.2 Initialisation

A {} delimited list of elements of type T is an object of the standard library type initializer_list<T>, a list of Ts:

vector(initializer_list<double> lst)
    :sz{lst.size()}, elem{new double[sz]}
    copy(lst.begin(),lst.end(),elem)    // std::copy()

Remember how we use () for an element count and {} for element lists.

18.2 Copying

The default meaning of copying for a class is "Copy all the data members". That often makes perfect sense.

But for a pointer member just copying the members causes problems.

(Our first try at copying a vector leaves us with two vectors pointing to the same set of element data. When a destructor is called, badness happens!)

18.2.1 Copy constructors

We provide a copy operation that copies the elements and make sure that this gets called when we initialise one vector with another.

A copy constructor takes as its argument a reference to the object from which to copy:

vector(const vector&);

This constructor will be called when we try to initialise one vector with another.

vector::vector(const vector& arg)
// allocate elements, then initialise them by copying
    :sz{}, elem{new double[]}
    copy(arg,arg+sz,elem)           // std::copy()

(Now this try will give us two vectors each pointing to its own copy of the element data.)

The destructor can now do the right thing, each set of elements is correctly freed.

18.2.2 Copy assignments

As with copy initilisation, the default meaning of copy assignment is a memberwise copy, so we have the same double deletion problem as before, plus a memory leak (the destination vector's old element data doesn't get deleted).

This is a bit more complicated than initialisation because we have to deal with the old elements:

vector& vector::operator=(const vector& a)
    double* p = new double[];
    copy(a.elem,,p);     // mistake in book?
    delete[] elem;
    elem = p;
    sz =;
    return *this;

As demonstrated here, we could have simplified the code by freeing the memory for the old elements before creating the copy, but it is usually a very good idea not to throw away information before you know that you can replace it. (Also, if you did that, strange things would happen if you assigned a vector to itself.)

18.2.3 Copy terminology

The basic distinction is whether you copy a pointer/reference or copy the information pointed/referred to.

Knowing this, we can say that the problem with our original vector attempt was that it did a shallow copy.

Types that provide shallow copy are said to have pointer semantics. Types that provide deep copy are said to have value semantics.

18.3.4 Moving


vector fill(istream& is)
    vector res;
    for (double x; is>>x; ) res.push_back(x);
    return res;
    vector vec = fill(cin)

At the end of fill() res is copied out. But why copy? Surely we just want to return the original res.

We would like vec to refer to res without any copy. After moving res's element pointer and element count to vec, res holds no elements (and the 'original data' is now belonging to vec). Now res can be destroyed simply and efficiently without undesirable side effects.

To do this, we define move operations to complement the copy operations:

    vector(vector&& a);             // move constructor
    vector& operator=(vector&&);    // move assignment

The && notation is an "rvalue reference". We use it for defining move operations.

Note: Move operations do not take const arguments (vector&& not const vector&&). Part of the purpose of the move operation is to modify the source, to make it "empty".

vector::vector(vector&& a);
    :sz{}, elem{a.elem}
{ = 0;
    a.elem = nullptr;

vector& vector::operator=(vector&& a)
    delete[] elem;
    elem = a.elem;
    sz =;
    a.elem = nullptr; = 0;
    return *this;

By defining a move constructor we make it easy and cheap to move around large amounts of information.

The move constructor is implicitly used to implement the return. The compiler knows that the local value returned from the function res is about to go out of scope, so it can move it, rather than copying it.

The importance of move constructors is that we do not have to deal with pointers or references to get large amounts of information out of a function.

18.3 Essential operations

What constructors/destructors/etc. etc. should a class have?

Usually we use a constructor to establish an invariant.

If we can't find a good invariant we probably have a poorly designed class or just a plain data structure.

What to choose:

(JF: See 'Rule of five')

18.3.1 Explicit constructors

A constructor that takes a single argument defines a conversion from its argument type to its class.

    complex(double);        // conversion

However, implicit conversions should be used sparingly and with caution, beccause they can cause unexpected and undesirable results.

A constructor defined explicit provides only the usual construction semantics and no implicit conversions:

class vector {
    explicit vector(int);

If in doubt, make any constructor that can be invoked with a single argument explicit.

18.3.2 Debugging constructors and destructors

Remember there is not just a single syntax that triggers a constructor, it is simpler to think of constructors/destructors this way:

A destructor is called whenever an object of its class is destroyed i.e. goes out of scope, the program terminates or delete is used on a pointer to an object.

A constructor (some appropriate constructor) is invoked whenever an object of its class is created i.e. when a variable is initialised, when an object is created using new (except for built-in types), and whenever an object is copied.

A good way to get a feel for this is to print statements to constructors, assignment operations and destructors and just try.

One way to determine whether you have a memory leak is to see if the number of constructions equals the number of destructions.

Forgetting to define copy constructors and copy assignments for classes that allocate memory or hold pointers to objects is a common, and easily avoidable source of problems.

If your problems get too big to handle by using simple means like printing statements, there are professional tools called "leak detectors". The ideal is of course, not to have any leaks in the first place, by using techniques that avoid such leaks.

18.4 Access to vector elements

// allows reading but not writing
double operator[](int n) { return elem[n]; }
// allows both, but use requires dereference e.g. *v[i]
double* operator[](int n) { return &elem[n]; }

Returning a reference from the subscript operator solves this problem

double& operator[](int n) { return elem[n]; }

// now can use as normal
v[i] = i;       // write
cout << v[i];   // read

18.4.1 Overloading on const

Although we cannot invoke operator[]() for a const vector:

// error, but should be fine we're only reading
double d = some_const_vector[1];

The reason being our operator[]() as it is now could potentially change the vector (it doesn't but the compiler doesn't know that because we "forgot" to tell it).

double& operator[](int n);      // non-const (pass ref)
double operator[](int n) const; // const (pass value)

We could equally have returned a const double& but since a double is a small object we chose pass-by-value here.

Since vectors are often passed by const reference this const version of operator[]() is an essential addition.

18.5 Arrays

We have seen arrays allocated on the free store. We can also allocate them elsewhere as named variables:

Again we show our bias towards using vector. Use std::vector where you have a choice (which is most of the time).

An array is a homogeneous sequence of objects allocated in contiguous memory; that is all elements have the same type and there are no gaps between the objects of the sequence

Different to free store arrays, we can't have the number of elements be a variable; the number of elements must be known at compile time.

Once more, there is no range checking with arrays.

18.5.1 Pointers to array elements

A pointer can point to an element of an array:

double ad[10];
double* p = &ad[5];

We can subscript both positive and negative numbers:

cout << p[2];
cout << p[-3];

Again, note how dangerous this could be.

We can move the pointer using pointer arithmetic:

p += 2;     // forward 2
p -= 5;     // back 5
p++;        // forward 1 (most common)
p--;        // back 1 (most common)

We have to take great care to make sure we don't point outside the array.

The best policy is usually to simply avoid pointer arithmetic.

Why does C++ allow pointer arithmetic at all? Mainly historical and backwards compatibility reasons.

18.5.2 Pointers and arrays

The name of an array refers to all the elements of the array:

char ch[100];
cout << sizeof(ch);             // 100

However the name of a an array turns into a pointer (to the array's first element) at the slightest excuse:

char* p = ch;

This can be useful, but often the cause of unexpected behaviour.

One reason for having array names convert to pointers is to avoid accidentally passing large amounts of data by value.

Note this behaviour is an exception, and should surprise you, every other time you don't explicitly declare a pass-by-reference argument, the object is copied (not so here).

Also, the pointer to the first element that you get here is a value and not a variable, so you cannot assign it.

As a consequence of this implicit array-name-to-pointer conversion is you can't even copy arrays by assignment:

arr_a = arr_b;      // error

So if you need to copy an array you must write elaborate code to do so (for loops etc.)

C does not support anything like vector so arrays are used extensively in C code and a lot of C++ code, written in C style.

18.5.3 Array initialization

An array of chars can be initialised with a string literal:

char ac[] = "Beorn";    // 'B''e''o''r''n' 0

This will actually become an array of six characters, terminated by the numeric value 0 (not the character 0).

We call such a zero-terminated array a C-style string (used widely).

But this is for string literal initialisations only:

char chars[] = {'a','b','c'};   // 3 chars 'a''b''c'
                                // no 0 at end

18.5.4 Pointer problems

In particular, all serious problems with pointers involve trying to access something that isn't an object of the expected type, and many of the problems involve access outside the bounds of an array.

Here we will consider:

Don't access through the null pointer:

int* p = nullptr;
*p = 7;     // ouch!

We prefer not to pass null pointers around, but if you have to: Test for a null pointer before use.

Using references and using exceptions to signal errors are the main tools for avoiding null pointers.

Do initialise your pointers:

int* p;
*p = 9;     // ouch! where?!

In particular, don't forget to initialise pointers that are class members.

Don't access nonexistent array elements:

int a[10];
int* p = &a[10];
*p = 11;
a[10] = 12;     // ouch all over!

Be careful with the first and last elements of a loop and try not to pass arrays around as pointers to their first elements. Instead use vectors. If you really must use an array in more than one function (passing it as an argument) then be extra careful to pass its size too.

Don't access through a deleted pointer:

int* p = new int{7};
delete p;
*p = 13;    // ouch!

Of all the problems we consider this the hardest to systematically avoid.

The most effective defense is not to have naked news that require naked deletes: use new and delete in constructors/destructors (or use a container such as Vector_ref to handle deletes).

Don't return a pointer to a local variable:

int* f()
    int x = 7;
    return &x;
}                   // x is gone!

int* p = f();
*p = 15;            // ouch!

Remember, local variables are allocated (on the stack) upon entry to the function and deallocated again at the exit from the function (in particular destructors are called for local variables of classes with destructors).

It is common for programmers to underestimate these problems.

The solution is not to litter your code with pointers, arrays, news and deletes. If you do, "being careful" simply isn't enough in realistically sized programs. Instead, rely on vectors, RAII ("Resource Acquisition Is Initialisation" Ch.19), and other systematic approaches to the management of memory and other resources.

18.6 Examples: palindrome

18.6.1 Palindromes using string

18.6.2 Palindromes using arrays

We consider this "array solution" significantly messier than the string solution (and it gets much worse if we consider the possibility of long strings).

18.6.3 Palindromes using pointers

19 Vector, Templates, and Exceptions

19.1 The problems

19.2 Changing size

v = v2;

19.2.1 Representation

In practice if we change size once we usually do so many times.

Implementations keep track of a "free space" reserved for "future expansion".

class vector {
    int sz;
    double* elem;
    int space;

When first constructed, vector has no free space.

When size changes we allocate extra free space.

19.2.2 reserve and capacity

void vector::reserve(int newalloc)
    if (newalloc<=space) return;      // dont decrease alloc
    double* p = new double[newalloc]; // allocate new space
    for (int i=0; i<sz; ++i) p[i] = elem[i]; // copy old
    delete[ ] elem;                   // deallocate old
    elem = p;
    space = newalloc;

int vector::capacity() const { return space; }

19.2.3 resize

resize(): Situations to handle


void vector::resize(int newsize)
    // make the vector have newsize elements
    // initialize new elements with default value 0.0
    for (int i=sz; i<newsize; ++i) elem[i] = 0.0;
    sz = newsize;

19.2.4 push_back

void vector::push_back(double d)
    // increase vector size by one
    // initialize the new element with d
    if (space==0)       // no more free space: get more
    if (space==sz)

    elem[sz] = d;       // add d at end
    ++sz;               // increase the size

19.2.5 Assignment

Like this:

vector& vector::operator=(const vector& a)
    // like copy constructor, but we must deal with
    // old elements
    double* p = new double[];  // allocate new space
    for (int i = 0; i<; ++i)
        p[i] = a.elem[i];          // copy elements
    delete[ ] elem;                // deallocate old
    space = sz =;             // set new size
    elem = p;                      // set new elements
    return *this;                  // return self-refer

What if target vector size > source? What if target vector size == source? (Very common)

vector& vector::operator=(const vector& a)
    if (this==&a) return *this;    // self-assignment,
                                   // no work needed

    if (<=space) {             // enough space
        for (int i = 0; i<; ++i)
            elem[i] = a.elem[i];   // just copy elems
        sz =;
        return *this;

    // or we do as previous and allocate/deallocate
    double* p = new double[];
    for (int i = 0; i<; ++i)
        p[i] = a.elem[i];
    delete[ ] elem;
    space = sz =;
    elem = p;
    return *this;

This shows a common use of the this pointer: Checking if we're dealing with the same object as the current. (Argument a is the same object for which the member function operator=() was called).

19.2.6 Our vector so far

// an almost real vector of doubles:
class vector {
        for 0<=n<sz elem[n] is element n
        if sz<space there is space for
        (space-sz) doubles after elem[sz-1]
    int sz;           // the size
    double* elem;     // pointer to the elements (or 0)
    int space;        // num elems plus num free slots
    vector() : sz(0), elem(0), space(0) { }
    vector(int s) :sz(s), elem(new double[s]), space(s)
        for (int i=0; i<sz; ++i)
            elem[i] = 0.0;

    vector(const vector&);            // copy xtor
    vector& operator=(const vector&); // copy assignment

    ~vector() { delete[ ] elem; }     // destructor

    double& operator[ ](int n)
        { return elem[n]; }
    const double& operator[ ](int n) const
        { return elem[n]; }

    int size() const { return sz; }
    int capacity() const { return space; }

    void resize(int newsize);         // growth
    void push_back(double d);
    void reserve(int newalloc);

//... (Member definitions as above)

19.3 Templates

A template is a mechanism that allows a programmer to use types as parameters for a class or a function.

19.3.1 Types as template parameters

// an almost real vector of Ts:
// read "for all types T" (just like maths)

template<class T> class vector {
    int sz;                           // the size
    T* elem;                          // pointer to elem
    int space;                        // size+free_space

    vector() : sz(0), elem(0), space(0) { }
    vector(int s);

    vector(const vector&);            // copy xtor
    vector& operator=(const vector&); // copy assignment

    ~vector() { delete[ ] elem; }     // destructor

    T& operator[ ] (int n) // access: return reference
        { return elem[n]; }
    const T& operator[ ] (int n) const
        { return elem[n]; }

    int size() const { return sz; }   // current size
    int capacity() const { return space; }

    void resize(int newsize);         // growth
    void push_back(const T& d);
    void reserve(int newalloc);

Sometimes we call a class template a type generator and we call the process of generating types from a class template specialization or template instantiation.

You will see template<typename T> or template<class T>.

19.3.2 Generic programming

Templates are the basis for generic programming in C++.

Generic programming: Writing code that works for a variety of types presented as arguments (as long as those argument types meet specific syntactic and semantic requirements).

Parameterising a class gives a class template, also known as a parameterised type or parameterised class.

Parameterising a function gives a function template, also known as a parameterised function or sometimes an algorithm. Thus generic programming is sometimes referred to as algorithm oriented programming.

Often called parametric polymorphism (as opposed to ad hoc polymorphism used in object-oriented programming).

Use templates where performance is essential e.g. numerics, hard-realtime.

Use templates where flexibility in combining several different types is essential.

19.3.3 Concepts

Templates can have a poor separation between its interface and implementation (often resulting in spectaculary poor error messages, sometimes coming much later in compilation).

Place definition of any template that is to be used in more than one translation unit in a header file.

Initially write very simple templates and proceed carefully to gain experience.

First develop and test a class using specific types then replace the types with template parameters and test with a variety of arguments.

C++14: A set of requirements on a template argument is a concept.

template<typename T>        // for all types T
    requires Element<T>()   // such that T is an Element
class vector {


template<Element T>
class vector {

If not using C++14 specify in comments

template<typename Elem> // requires Element<Elem>()

Common and useful concepts:

Element<E>(): E can be an element in a container
Container<C>(): Container C can hold Elements
Forward_iterator<For>(): For can traverse a sequence
Input_iterator<In>(): In can read a sequence once only
Output_iterator<Out>(): Seq can be output using Out
Allocator<A>(): A can acquire and release memory
Number<N>(): N behaves like a number supporting +-*/
//... see p.685-686 for full list

19.3.4 Containers and inheritance

19.3.5 Integers as template parameters

19.3.6 Template argument deduction

19.3.7 Generalizing vector

19.4 Range checking and exceptions

19.4.1 An aside: design considerations

19.4.2 A confession: macros

19.5 Resources and exceptions

19.5.1 Potential resource management problems

19.5.2 Resource acquisition is initialization

19.5.3 Guarantees

19.5.4 auto_ptr

19.5.5 RAII for vector

20 Containers and Iterators

20.1 Storing and processing data

20.1.1 Working with data

20.1.2 Generalizing code

20.2 STL ideals

20.3 Sequences and iterators

20.3.1 Back to the example

20.4 Linked lists

20.4.1 List operations

20.4.2 Iteration

20.5 Generalizing vector yet again

20.6 An example: a simple text editor

20.6.1 Lines

20.6.2 Iteration

20.7 vector, list, and string

20.7.1 insert and erase

20.8 Adapting our vector to the STL

20.9 Adapting built-in arrays to the STL

20.10 Container overview

20.10.1 Iterator categories

21 Algorithms and Maps

21.1 Standard library algorithms

21.2 The simplest algorithm: find()

21.2.1 Some generic uses

21.3 The general search: find_if()

21.4 Function objects

21.4.1 An abstract view of function objects

21.4.2 Predicates on class members

21.5 Numerical algorithms

21.5.1 Accumulate

21.5.2 Generalizing accumulate()

21.5.3 Inner product

21.5.4 Generalizing inner_product()

21.6 Associative containers

21.6.1 Maps

21.6.2 map overview

21.6.3 Another map example

21.6.4 unordered_map

21.6.5 Sets

21.7 Copying

21.7.1 Copy

21.7.2 Stream iterators

21.7.3 Using a set to keep order

21.7.4 copy_if

21.8 Sorting and searching

Part IV Broadening the View

22 Ideals and History

22.1 History, ideals, and professionalism

22.1.1 Programming language aims and philosophies

22.1.2 Programming ideals

22.1.3 Styles/paradigms

22.2 Programming language history overview

22.2.1 The earliest languages

22.2.2 The roots of modern languages

22.2.3 The Algol family

22.2.4 Simula

22.2.5 C

22.2.6 C++

22.2.7 Today

22.2.8 Information sources

23 Text Manipulation

23.1 Text

23.2 Strings

23.3 I/O streams

23.4 Maps

23.4.1 Implementation details

23.5 A problem

23.6 The idea of regular expressions

23.7 Searching with regular expressions

23.8 Regular expression syntax

23.8.1 Characters and special characters

23.8.2 Character classes

23.8.3 Repeats

23.8.4 Grouping

23.8.5 Alternation

23.8.6 Character sets and ranges

23.8.7 Regular expression errors

23.9 Matching with regular expressions

23.10 References

24 Numerics

24.1 Introduction

24.2 Size, precision, and overflow

24.2.1 Numeric limits

24.3 Arrays

24.4 C-style multidimensional arrays

24.5 The Matrix library

24.5.1 Dimensions and access

24.5.2 1D Matrix

24.5.3 2D Matrix

24.5.4 Matrix I/O

24.5.5 3D Matrix

24.6 An example: solving linear equations

24.6.1 Classical Gaussian elimination

24.6.2 Pivoting

24.6.3 Testing

24.7 Random numbers

24.8 The standard mathematical functions

24.9 Complex numbers

24.10 References

25 Embedded Systems Programming

25.1 Embedded systems

25.2 Basic concepts

25.2.1 Predictability

25.2.2 Ideals

25.2.3 Living with failure

25.3 Memory management

25.3.1 Free-store problems

25.3.2 Alternatives to general free store

25.3.3 Pool example

25.3.4 Stack example

25.4 Addresses, pointers, and arrays

25.4.1 Unchecked conversions

25.4.2 A problem: dysfunctional interfaces

25.4.3 A solution: an interface class

25.4.4 Inheritance and containers

25.5 Bits, bytes, and words

25.5.1 Bits and bit operations

25.5.2 bitset

25.5.3 Signed and unsigned

25.5.4 Bit manipulation

25.5.5 Bitfields

25.5.6 An example: simple encryption

25.6 Coding standards

25.6.1 What should a coding standard be?

25.6.2 Sample rules

25.6.3 Real coding standards

26 Testing

26.1 What we want

26.1.1 Caveat

26.2 Proofs

26.3 Testing

26.3.1 Regression tests

26.3.2 Unit tests

26.3.3 Algorithms and non-algorithms

26.3.4 System tests

26.3.5 Testing classes

26.3.6 Finding assumptions that do not hold

26.4 Design for testing

26.5 Debugging

26.6 Performance

26.6.1 Timing

26.7 References

27 The C Programming Language

27.1 C and C++: siblings

27.1.1 C/C++ compatibility

27.1.2 C++ features missing from C

27.1.3 The C standard library

27.2 Functions

27.2.1 No function name overloading

27.2.2 Function argument type checking

27.2.3 Function definitions

27.2.4 Calling C from C++ and C++ from C

27.2.5 Pointers to functions

27.3 Minor language differences

27.3.1 struct tag namespace

27.3.2 Keywords

27.3.3 Definitions

27.3.4 C-style casts

27.3.5 Conversion of void*

27.3.6 enum

27.3.7 Namespaces

27.4 Free store

27.5 C-style strings

27.5.1 C-style strings and const

27.5.2 Byte operations

27.5.3 An example: strcpy()

27.5.4 A style issue

27.6 Input/output: stdio

27.6.1 Output

27.6.2 Input

27.6.3 Files

27.7 Constants and macros

27.8 Macros

27.8.1 Function-like macros

27.8.2 Syntax macros

27.8.3 Conditional compilation

27.9 An example: intrusive containers

Part V Appendices

Appendix A Language Summary

A.1 General

A.1.1 Terminology

A.1.2 Program start and termination

A.1.3 Comments

A.2 Literals

A.2.1 Integer literals

A.2.2 Floating-point-literals

A.2.3 Boolean literals

A.2.4 Character literals

A.2.5 String literals

A.2.6 The pointer literal

A.3 Identifiers

A.3.1 Keywords

A.4 Scope, storage class, and lifetime

A.4.1 Scope

A.4.2 Storage class

A.4.3 Lifetime

A.5 Expressions

A.5.1 User-defined operators

A.5.2 Implicit type conversion

A.5.3 Constant expressions

A.5.4 sizeof

A.5.5 Logical expressions

A.5.6 new and delete

A.5.7 Casts

A.6 Statements

A.7 Declarations

A.7.1 Definitions

A.8 Built-in types

A.8.1 Pointers

A.8.2 Arrays

A.8.3 References

A.9 Functions

A.9.1 Overload resolution

A.9.2 Default arguments

A.9.3 Unspecified arguments

A.9.4 Linkage specifications

A.10 User-defined types

A.10.1 Operator overloading

A.11 Enumerations

A.12 Classes

A.12.1 Member access

A.12.2 Class member definitions

A.12.3 Construction, destruction, and copy

A.12.4 Derived classes

A.12.5 Bitfields

A.12.6 Unions

A.13 Templates

A.13.1 Template arguments

A.13.2 Template instantiation

A.13.3 Template member types

A.14 Exceptions

A.15 Namespaces

A.16 Aliases

A.17 Preprocessor directives

A.17.1 #include

A.17.2 #define

Appendix B Standard Library Summary

B.1 Overview

B.1.1 Header files

B.1.2 Namespace std

B.1.3 Description style

B.2 Error handling

B.2.1 Exceptions

B.3 Iterators

B.3.1 Iterator model

B.3.2 Iterator categories

B.4 Containers

B.4.1 Overview

B.4.2 Member types

B.4.3 Constructors, destructors, and assignments

B.4.4 Iterators

B.4.5 Element access

B.4.6 Stack and queue operations

B.4.7 List operations

B.4.8 Size and capacity

B.4.9 Other operations

B.4.10 Associative container operations

B.5 Algorithms

B.5.1 Nonmodifying sequence algorithms

B.5.2 Modifying sequence algorithms

B.5.3 Utility algorithms

B.5.4 Sorting and searching

B.5.5 Set algorithms

B.5.6 Heaps

B.5.7 Permutations

B.5.8 min and max

B.6 STL utilities

B.6.1 Inserters

B.6.2 Function objects

B.6.3 pair

B.7 I/O streams

B.7.1 I/O streams hierarchy

B.7.2 Error handling

B.7.3 Input operations

B.7.4 Output operations

B.7.5 Formatting

B.7.6 Standard manipulators

B.8 String manipulation

B.8.1 Character classification

B.8.2 String

B.8.3 Regular expression matching

B.9 Numerics

B.9.1 Numerical limits

B.9.2 Standard mathematical functions

B.9.3 Complex

B.9.4 valarray

B.9.5 Generalized numerical algorithms

B.10 C standard library functions

B.10.1 Files

B.10.2 The printf() family

B.10.3 C-style strings

B.10.4 Memory

B.10.5 Date and time

B.10.6 Etc.

B.11 Other libraries

Appendix C Getting Started with Visual Studio

C.1 Getting a program to run

C.2 Installing Visual Studio

C.3 Creating and running a program

C.3.1 Create a new project

C.3.2 Use the std_lib_facilities.h header file

C.3.3 Add a C++ source file to the project

C.3.4 Enter your source code

C.3.5 Build an executable program

C.3.6 Execute the program

C.3.7 Save the program

C.4 Later

Appendix D Installing FLTK

D.1 Introduction

D.2 Downloading FLTK

D.3 Installing FLTK

D.4 Using FLTK in Visual Studio

D.5 Testing if it all worked

Appendix E GUI Implementation

E.1 Callback implementation

E.2 Widget implementation

E.3 Window implementation

E.4 Vector_ref

E.5 An example: manipulating Widgets

So cried Ahab, once more hailing a ship showing English colours, bearing down under the stern. Trumpet to mouth, the old man was standing in his hoisted quarter-boat, his ivory leg plainly revealed to the stranger captain, who was carelessly reclining in his own boat's bow. He was a darkly-tanned, burly, good-natured, fine-looking man, of sixty or thereabouts, dressed in a spacious roundabout, that hung round him in festoons of blue pilot-cloth; and one empty arm of this jacket streamed behind him like the broidered arm of a hussar's surcoat.

qwertyuiopasdf ghjklzxcvbnm qwertyuiopasdf ghjklzxcvbnm qwertyuiopasdf ghjklzxcvbnm

So cried Ahab, once more hailing a ship showing English colours, bearing down under the stern. Trumpet to mouth, the old man was standing in his hoisted quarter-boat, his ivory leg plainly revealed to the stranger captain.

In less than a minute, without quitting his little craft, he and his crew were dropped to the water, and were soon alongside of the stranger. But here a curious difficulty presented itself.

In the excitement of the moment, Ahab had forgotten that since the loss of his leg he had never once stepped on board of any vessel at sea but his own, and then it was always by an ingenious and very handy mechanical contrivance peculiar to the Pequod, and a thing not to be rigged and shipped in any other vessel at a moment's warning.

Now, it is no very easy matter for anybody—except those who are almost hourly used to it, like whalemen—to clamber up a ship's side from a boat on the open sea; for the great swells now lift the boat high up towards the bulwarks, and then instantaneously drop it half way down to the kelson. So, deprived of one leg, and the strange ship of course being altogether unsupplied with the kindly invention, Ahab now found himself abjectly reduced to a clumsy landsman again; hopelessly eyeing the uncertain changeful height he could hardly hope to attain.