.. highlight:: c++

Chapter 2 Notes
===============

Please read chapter 2 of the textbook.


Variables
---------

a variable holds a value

a variable has a type

lets look at some of the basic numeric variable types

::

    // num_bars.cpp

    #include "cmpt_error.h"
    #include <iostream>
    #include <string>

    using namespace std;

    int main() {
        int num_bars = 0;
        cout << "How many chocolate bars do you want to buy? ";
        cin >> num_bars;

        double bar_cost = 0.0; 
        cout << "How much does one bar cost? ";
        cin >> bar_cost;

        double total_cost = num_bars * bar_cost;
        cout << "It will cost you $" << total_cost 
             << " to buy " << num_bars << " bars.\n";
    }

to compile and run this program type the following

::

    $ make num_bars
    $ ./num_bars 
    ...

remember to put both ``cmpt_error.h`` and ``makefile`` (get them from Pages on
Canvas_) in the same folder as your ``.cpp`` file


Names
-----

C++ variable names must follow a few rules

they must consist of numbers, letters (upper and lower case), and the ``_``
character; most other characters are not permitted

however, the **first** character of name **cannot** be a number

you cannot create a variable that is the same as C++ keyword, such as ``int``
or ``double``

for example, these are **legal** C++ variable names: ``x``, ``S_FLAG``, ``_``,
``sec15``, ...

for example, these are **illegal** C++ variable names: ``3x``, ``S-FLAG``,
``double``, ``sec+15``, ...


Variable Declarations
---------------------

you must declare variables in C++ before you start using them, e.g.

::

    int num_bars = 0;
    double cost;              // careful: cost has an unknown value 
    double x = 0.0, y = 0.0;  // note the comma

notice that the variable type comes first, followed by a list of variables

the ``int`` type represents whole numbers (integers), such as 583, 0, and
-99332

the ``double`` type represents decimal numbers, such as 3.14, -2.0094, and 5.0

always try to use the data type that best matches the values you want


Variable Declarations
---------------------

the C++ compiler uses variable declarations to help determine how much memory
is needed to store a value in that variable

it also uses them to determine what operations are legal on the variables


Assignment Statements
---------------------

assignment statements are used to assign values to variables

::

    int x = 4;
    int y = 2;
    int z;

    z = 6;      // assigns 6 to z
    z = x + y;  // assigns the sum of x and y to z

the ``=`` means "assign", in C++, not "equals" like in math

assignment statements like this are legal and useful in C++

::

    z = z + 1;  // adds 1 to z
    z = z * z;  // triples z

these are not algebraic equations, because in C++ ``=`` does **not** mean
"equals"

in C++, ``=`` means "assignment"


Literals
--------

consider this variable declaration

::

    double temp = 4.0;

``temp`` is a variable of type ``double``, while 4.0 is a **literal** of type
``double``

informally we often call both ``temp`` and 4.0 doubles, but sometimes it is
important to distinguish them

note that 4 is an ``int`` literal, while 4.0 is a ``double`` literal


Choosing Good Names
-------------------

generally, **variable names should describe their purpose**

in other words, they should be self-descriptive

consider this version of the above program where the variables names have been
replaced by ``a``, ``b``, and ``c``

::

    int main() {
        int a = 0;
        cout << "How many chocolate bars do you want to buy? ";
        cin >> a;

        double b = 0.0; 
        cout << "How much does one bar cost? ";
        cin >> b;

        double c = a * b;
        cout << "It will cost you $" << c 
             << " to buy " << a << " bars.\n";
    }

it's harder to read and understand this code because the variables names don't
give you much hint as to their purpose


Input and Output
----------------

as we've seen, C++ uses ``cin`` to get input from the keyboard, and ``cout``
to print output to the screen

in contrast, C uses functions like ``scanf`` to get input, and ``printf`` to
print output 

we may see how to use ``scanf`` and ``printf`` a later in the course

``scanf`` is trickier and more error-prone than ``cin``

``printf`` is often easier then ``cout`` for "fancy" formatting 


String Literals
---------------

consider this statement

::

    cout << "Fido loves to bark\n";

``"Fido loves to bark\n"`` is a string literal

``\n`` represents the newline character, and causes the cursor to go to the
next line when you print it with ``cout``

``\n`` is an example of an **escape character**


Escape Characters
-----------------

an escape character in a string always starts with a ``\``

the ``\`` means the next character should be interpreted specially

here are  a few common escape characters

``\n`` newline

``\t`` horizontal tab

``\\`` backslash

``\"`` double quote

what do these print?

::

    cout << "\"\\\" is my favourite string";
    // "\" is my favourite string

    cout << "use \\\\ for a backslash";
    // use \\ for a backslash


Raw String Literals
-------------------

C++11 (i.e. versions of C++ since 2011) allows raw string literals

::

    cout << R"("\" is my favourite string)";
    // "\" is my favourite string

    cout << "\n";

    cout << R"(use \\ for a backslash)";
    // use \\ for a backslash

in a raw string literal, escape characters have no special meaning

raw string literals can be very useful for strings that have a lot of escape
characters


ints
----

an ``int`` is a whole number like -45489 or 93

it is represented internally in C++ using a fixed number of buts, e.g. 32 bits
or 64 bits (C++ does explicitly say how many bits are in an ``int``)

thus, there is a max ``int`` and a min ``int``

you must always be careful to never allow ``int`` calculations to go outside
the ``int`` min/max!

this program shows how to determine the size of an ``int``

::

    #include "cmpt_error.h"
    #include <iostream>
    #include <climits>

    using namespace std;

    int main() {
        cout << "number of bytes in an int: " << sizeof(int) << '\n'
             << "              minimum int: " << INT_MIN << '\n'
             << "              maximum int: " << INT_MAX << '\n';
    }

remember, there is no guarantee in general about any of these values!

they could be different on different computers, or with particular compiler
options set


doubles
-------

a ``double`` is a number with a decimal, like -657.86433 or -53.00

they are **much** trickier to deal with than ``int``\ s

e.g. round-off errors are a serious issue in many calculations involving
``double``\ s

::

    #include "cmpt_error.h"
    #include <iostream>
    #include <cfloat>

    using namespace std;

    int main() {
        cout << "number of bytes in a double: " << sizeof(double) << '\n'
             << "             minimum double: " << DBL_MIN << '\n'
             << "             maximum double: " << DBL_MAX << '\n';
    }


Other Numeric Types
-------------------

C++ has many other numeric types

``short``

``short int``

``long``

``long int``

``float``

``long double``

``int8_t``

``long long``

they are generally used in cases where numbers with different ranges are
needed

for example, ``long int`` allows much large that plain ``int``\ s, but use
more memory

for example, a ``float`` usually uses less memory than a ``double``, but it
has a smaller range and less precision

see the tables on p. 63 and p. 64 of the text


The char Type
-------------

the type ``char`` is used for storing a single character

it stores a character using it's ASCII/Unicode code number

thus, a ``char`` type often acts like a small integer

here's an example

::

    char op = '+';  // note use of ' instead of "

    cout << op 
         << '\n';

``'+'`` and ``'\n'`` are examples of ``char`` literals

note the use of ``'`` instead of ``"``

``'+'`` is a ``char`` literal, while ``"+"`` is a string literal --- they are
not the same!


The char Type
-------------

::

    // chars.cpp

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    int main() {
        char a, b, c;
        cout << "What is the first character? ";
        cin >> a;
        cout << "What is the second character? ";
        cin >> b;
        cout << "What is the third character? ";
        cin >> c;

        cout << "Here they are in reverse: "
             << c << b << a
             << '\n';
    }


The bool Type
-------------

the ``bool`` type has only two values: ``true`` and ``false``

::

    bool flag = true;

later we will see that ``bool`` types are fundamental parts of if-statements
and loops


The string Type
---------------

C++ has a very powerful and easy-to-use ``string`` type

it's one of the major distinctions between C++ and C --- strings in C are
notoriously tricky and error-prone

::

    // strings.cpp

    #include "cmpt_error.h"
    #include <iostream>
    #include <string>

    using namespace std;

    int main() {
        string first_name; // initialized to "" by default
        string last_name;

        cout << "What is your name? ";
        cin >> first_name;

        cout << "What is your last name? ";
        cin >> last_name;

        string full_name = first_name + " " + last_name;

        cout << "Hi " << full_name << "!\n";
    }

note the use of ``#include <string>`` to get access to the ``string`` type

if you don't give a ``string`` and initial value when you initialize it, it is
assign the empty string ``""``


Mixing Types
------------

C++, for good and bad, lets you mix types

it can get extremely complex at times, but in many simple cases it is not too
hard to understand

consider this example

::

    double x = 4;

``x`` is a variable of type ``double``, and 4 is an ``int`` literal

C++ lets you assign an ``int`` to a ``double``

C++ automatically converts the 4 to a ``double`` because the internal
representation of ``int``\ s and ``double``\ s is different

that's okay because ``double`` includes all the integers


Mixing Types
------------

consider this example

::

    int y = 4.9;
    cout << y;  // prints 4 (not 5!)

``y`` is a variable of type ``int``, and 4.9 is an ``double`` literal

C++ lets you assign a ``double`` to an ``int``

C++ automatically converts the 4.9 to an ``int`` because the internal
representation of ``int``\ s and ``double``\ s is different

the major issue here is that the .9 is truncated, i.e. just chopped off

no rounding is done!

this might seem like a minor issue, but it is a significant source of serious
errors in many C++ programs

other languages simply don't allow assignments where information might be lost


Mixing Types
------------

sometimes it's okay to convert a ``double`` to an ``int``

::

    int y = 4.0;
    cout << y;  // prints 4 

no information is lost in converting 4.0 to an ``int``

you can get the code number for ``char`` by converting it to an ``int``

::

    char c = 'a';
    int i = c;
    cout << c     // prints a
         << '\n'
         << i     // prints 97 (code number for 'a')
         << '\n';


Basic Arithmetic
----------------

``+``, ``-``, ``*``, ``\``, and ``%`` are the basic arithmetic operators

brackets, ``(`` and ``)``, are used to change the order of evaluation (just
like in regular arithmetic)

::

    int a = 2;
    int b = 5;
    cout << a + b  // 7
         << '\n'
         << a - b  // -3
         << '\n'
         << a * b  // 10
         << '\n'
         << a / b  // 0
         << '\n'
         << b / a  // 2
         << '\n'
         << a % b  // 2
         << '\n'
         << b % a  // 1
         << '\n';


Basic Arithmetic
----------------

when you divide two ``int``\ s, the result is always an ``int``

::

   cout << 5 / 2      // 2    
        << 99 / 100;  // 0

any digits after the decimal point are truncated (i.e. chopped off) --- no
rounding is done!

this can be the source of many subtle and hard-to-find errors!


Basic Arithmetic
----------------

``%`` is the **mod operator**, or the **remainder operator**

``10 % 3`` evaluates to the remainder you get when you divide 3 into 10

``10 % 3`` is 1, because 3 goes into 10 3 times with **1 left over**

::

    cout << 5 % 1   // 0
         << 5 % 2   // 1
         << 5 % 3   // 2
         << 5 % 4   // 1
         << 5 % 5   // 0
         << 5 % 6   // 5
         << 5 % 7;  // 5

    cout << 0 % 5   // 0
         << 1 % 5   // 1
         << 2 % 5   // 2
         << 3 % 5   // 3
         << 4 % 5   // 4
         << 5 % 5   // 0
         << 6 % 5   // 1; 


Other Kinds of Assignment Statements
------------------------------------

::

    int x = 3;
    x += 2;  // adds 2 to x; now x is 5
    x -= 3;  // subtracts 3 from x; now x is 2
    x *= 2;  // multiplies x by 2; now x is 4
    x /= 2;  // divides x by 2; now x is 2
    ++x;     // adds 1 to x; now x is 3
    x++;     // adds 1 to x; now x is 4
    --x;     // subtracts 1 from x; now x is 3
    x--;     // subtracts 1 from x; now x is 2


if Statements
-------------

C++ programs make decision using if-else statements

::

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    int main() {
        cout << "How old are you? ";
        int age = 0;
        cin >> age;

        if (age < 18) {
            cout << "Sorry, you are too young to vote.\n";
        } else {
            cout << "You're old enough to vote.\n";     
        }
    }

an if-statement in C++ always checks a boolean expression, such as ``age <
18``

``age < 18`` is a boolean expression, because it evaluates either to ``true``
or ``false``


if Statements
-------------

::

    if (boolean_condition) {
        // code to run when boolean_condition is true
    } else {
        // code to run when boolean_condition is false
    }

you can also have an if-statement without the else part

::

    cout << "How old are you? ";
    int age = 0;
    cin >> age;

    if (age <= 0) {
        error("age must be > 0");
    }

    if (age < 18) {
        cout << "Sorry, you are too young to vote.\n";
    } else {
        cout << "You're old enough to vote.\n";     
    }

note the use of the ``error`` function here

it comes from the ``cmpt_error.h`` file we are using in this course

when ``error("age must be > 0")`` is executed it immediately ends the program
and prints the message ``"age must be > 0"``


Boolean Expressions
-------------------

boolean expressions are expressions that return ``true`` or ``false``

we often construct them with relational operators

assuming ``x`` and ``y`` are numeric variable, then ...

``x < y`` is ``true`` just when ``x`` is less than ``y``

``x <= y`` is ``true`` just when ``x`` is less than, or equal to, ``y``

``x > y`` is ``true`` just when ``x`` is greater than ``y``

``x >= y`` is ``true`` just when ``x`` is greater than, or equal to, ``y``

``x == y`` is ``true`` just when ``x`` equals ``y``

``x != y`` is ``true`` just when ``x`` doesn't equal ``y``

note that equality is ``==``, not ``=`` (which means assignment)


Boolean Expressions
-------------------

we also logical connectives to create boolean expressions

``&&`` means "and"

``||`` means "or"

``!`` means "not"

suppose ``a`` and ``b`` are both boolean expressions, then ...

``a && b`` is ``true`` just when both ``a`` is ``true``, and ``b`` is
``true``; otherwise it's ``false``

``a || b`` is ``true`` just when either ``a`` is ``true``, or ``b`` is
``true``, or both ``a`` and ``b`` are ``true``; otherwise it's ``false``

``!a`` is ``true`` just when ``a`` is false; otherwise it's ``false``


Boolean Expressions
-------------------

::

    int main() {
        cout << "How wide is your rectangle? ";
        double width = 0.0;
        cin >> width;

        cout << "How high is your rectangle? ";
        double height = 0.0;
        cin >> height;

        if (width > 0.0 && height > 0.0) {
            double area = width * height;
            double perim = 2 * (width + height);
            cout << "It's area is " << area
                 << " and it's perimeter is " << perim << ".\n";
        } else {
            cout << "That's not a valid rectangle!\n";
        }
    }

we could have written the if-statement condtion like this

::

    if (!(width <= 0.0 || height <= 0.0)) {
        // ... same as before ...
    } else {
        // ... same as before ...
    }

in English, the boolean expression ``!(width <= 0.0 || height <= 0.0)`` says
"if it's not the case that either width <= 0.0 or height <= 0.0"

this second form seems more complicated and is harder to read, so you probably
shouldn't write it this way


Nested if-statements
--------------------

you can put if-statements within if-statements when necessary

::

    int main() {
        cout << "Is your shape a square or a circle? ";
        string shape;
        cin >> shape;

        if (shape == "circle") {
            cout << "What is it's radius? ";
            double radius = 0.0;
            cin >> radius;

            if (radius <= 0) {
                cout << "That's not a valid radius!\n";
            } else {
                double area = 3.14 * radius * radius;
                cout << "area = " << area << "\n";
            }
        }

        if (shape == "square") {
            cout << "What is it's side length? ";
            double side = 0.0;
            cin >> side;

            if (side <= 0) {
                cout << "That's not a valid side length!\n";
            } else {
                double area = side * side;
                cout << "area = " << area << "\n";
            }
        }
    }

this program has a bug: if you type in something other than "circle" or
"square", then it just ends

to fix that, lets try to understand what the program is doing by looking just
at its essential logical structure


Pseudocode
----------

::

    get the name of the shape

    if shape is a circle then
        calculate and display area of circle
    end if

    if shape is a square then
        calculate and display area of square
    end if

we call this pseudocode --- it's a high-level English version of a program
that ignores many small details

we can see in this pseudocode that if the entered shape is, say, a triangle,
then neither of the if-statements is executed and so the program ends with
doing nothing


Pseudocode
----------

one way to fix it is to add a third if-statement

::

    get the name of the shape

    if shape is a circle then
        calculate and display area of circle
    end if

    if shape is a square then
        calculate and display area of square
    end if

    if shape is neither a circle nor a square then
        unknown shape!
    end if


Pseudocode
----------

a nicer solution is to use a multi-branch if-statement

::

    if shape is a circle then
        calculate and display area of circle
    else if shape is a square then
        calculate and display area of square
    else
        unknown shape!
    end if

this is one big if statement

the else part doesn't need a condition

it is executed just when the both the previous two if-conditions are false

so we can rewrite our program like this

::

    int main() {
        cout << "Is your shape a square or a circle? ";
        string shape;
        cin >> shape;

        if (shape == "circle") {
            cout << "What is it's radius? ";
            double radius = 0.0;
            cin >> radius;

            if (radius <= 0) {
                cout << "That's not a valid radius!\n";
            } else {
                double area = 3.14 * radius * radius;
                cout << "area = " << area << "\n";
            }
        } else if (shape == "square") {
            cout << "What is it's side length? ";
            double side = 0.0;
            cin >> side;

            if (side <= 0) {
                cout << "That's not a valid side length!\n";
            } else {
                double area = side * side;
                cout << "area = " << area << "\n";
            }
        } else {
            cout << "Sorry, I don't know what a " << shape << " is.\n";
        }
    }


Loops
-----

a loop lets you repeat a block of code

here's a program that prints "Hello!" 5 times

::

    // hello5.cpp

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    int main() {
        int i = 0;  // i is the loop's index variable

        while (i < 5) {
            cout << "Hello!\n";
            ++i;  // ++ adds 1 to i
        }

        cout << "Goodbye!\n";
    }

the boolean expression ``i < 5`` is called the loop's **condition**

the body of the loop is only executed if the condition is true

if the condition is false, the body of the loop is not executed

if you change the 5 to a 10, then ``Hello!`` is printed 10 times


Loops
-----

many loops use a variable to control how many times the body is executed

here we use ``i``

``i`` is an example of a loop-control variable

notice ``i`` is initialized to 0, and then incremented by 1 in the body


Loops
-----

here's a variation of the loop program that numbers each line

::

    int main() {
        int i = 0;  // i is the loop's index variable

        while (i < 5) {
            cout << (i + 1) << ". "
                 << "Hello!\n";
            ++i;  // ++ adds 1 to i
        }

        cout << "Goodbye!\n";
    }

this prints:

::

    1. Hello!
    2. Hello!
    3. Hello!
    4. Hello!
    5. Hello!
    Goodbye!


Counting Words and Characters
-----------------------------

this program shows a useful loop idiom where we use a ``cin`` expression in
the loop condition

::

    // count_words.cpp

    #include "cmpt_error.h"
    #include <iostream>
    #include <cmath>

    using namespace std;


    int main() {
        cout << "Please enter some words (ctrl-d to quit): ";

        string word;
        int word_count = 0;
        int char_count = 0;
        while (cin >> word) {  // cin >> word returns false when EOF character read
            word_count++;
            char_count += word.size();
        }
        cout << "     Word count: " << word_count << "\n";
        cout << "Character count: " << char_count << "\n";
    } // main

a ``while (cin >> word)`` style loops keeps reading words from ``cin`` until
an end-of-file (EOF) character is reached

in Linux, type ctrl-d to get an EOF character

note that in Linux it is easy to use re-direction to process files

for example, ``bill_complete.txt`` is a 5.4 megabyte text file containing the
complete works of Shakespeare

::

    $ ./word_count < bill_complete.txt 
    Please enter some words (ctrl-d to quit): 
         Word count: 904087
    Character count: 4054638

if you can measure the running-time of a program using the ``time`` command

::

    $ time ./word_count < bill_complete.txt 
    Please enter some words (ctrl-d to quit): 
         Word count: 904087
    Character count: 4054638

    real    0m0.236s
    user    0m0.236s
    sys 0m0.000s


Case Study: Calculating the Square Root of a Number
---------------------------------------------------

the easiest way to calculate the square root of a number is to use the
standard ``sqrt`` function

::

    #include "cmpt_error.h"
    #include <iostream>
    #include <cmath>

    using namespace std;

    int main() {
        cout << sqrt(200) << "\n";
    } // main

but what if that function didn't exist?

or what if you wanted to implement it yourself?


Case Study: Calculating the Square Root of a Number
---------------------------------------------------

there's a standard method for calculating square roots that works as follows

to find an approximation, :math:`x_n`, of the square root of of :math:`a`,
repeat the following as many times as needed

.. math::

    x_{n+1} = \frac{1}{2}(x_n + \frac{a}{x_n})

to use this, suppose we want to calculate the square root of :math:`a=5`

first, set :math:`x_1=\frac{5}{2}=2.5` (we could use almost any starting
value, but :math:`x_1=\frac{a}{2}` is reasonably close to the true square
root)

then calculate :math:`x_2`

.. math::

    x_2 &= \frac{1}{2}(x_1 + \frac{a}{x_1}) \\
        &= \frac{1}{2}(2.5 + \frac{5}{2.5}) \\
        &= 2.25

then calculate :math:`x_3`

.. math::

    x_3 &= \frac{1}{2}(x_2 + \frac{a}{x_2}) \\
        &= \frac{1}{2}(2.25 + \frac{5}{2.25}) \\
        &= 2.236

the actual square root of 5 is about 2.23606797749979, and so this value is
correct to 3 decimal places


Case Study: Calculating the Square Root of a Number
---------------------------------------------------

::

    cout << "Please enter a number: ";
    double a = 0.0;
    cin >> a;

    int i = 0;
    double x = a / 2.0;  // x is the estimate of a's square root

    // always does exactly 10 iterations of the loop
    while (i < 10) {
        cout << "x = " << x << "\n";
        x = (x + a / x) / 2.0;
        ++i;
    }
    cout << "square root of " << a << ": " << x << "\n";

the loop in this code always iterates exactly 10 times

::

    Please enter a number: 2
    x = 1
    x = 1.5
    x = 1.41667
    x = 1.41422
    x = 1.41421
    x = 1.41421
    x = 1.41421
    x = 1.41421
    x = 1.41421
    x = 1.41421
    square root of 2: 1.41421

we usually onl need the first few decimal places of the result to be accurate

so this does some unnecessary calculations

and in some cases it doesn't do enough!

::

    Please enter a number: 1234567
    x = 617284
    x = 308643
    x = 154323
    x = 77165.7
    x = 38590.8
    x = 19311.4
    x = 9687.67
    x = 4907.56
    x = 2579.56
    x = 1529.08
    square root of 1.23457e+06: 1168.24

correct answer is 1111.1107


Case Study: Calculating the Square Root of a Number
---------------------------------------------------

a better way to apply this method is to make the loop stop when x is accurate
enough

::

    cout << "Please enter a number: ";
    double a = 0.0;
    cin >> a;

    double prev_x = a;
    double x = a / 2.0;  // x is the estimate of a's square root
    
    // loop repeats until the difference between two approximations is small
    // enough
    while (abs(x - prev_x) > 0.0001) {
        cout << "x = " << x << "\n";
        prev_x = x;
        x = (x + a / x) / 2.0;
    }
    cout << "square root of " << a << ": " << x << "\n";

the loop stops when thedifference between two consecutive values of x is
small enough

in this case, we take "small enough" to mean "less than, or equal to, 0.0001"

this avoids extra work

and doesn't stop too soon

::

    Please enter a number: 2
    x = 1
    x = 1.5
    x = 1.41667
    x = 1.41422
    square root of 2: 1.41421

    Please enter a number: 1234567
    x = 617284
    x = 308643
    x = 154323
    x = 77165.7
    x = 38590.8
    x = 19311.4
    x = 9687.67
    x = 4907.56
    x = 2579.56
    x = 1529.08
    x = 1168.24
    x = 1112.51
    x = 1111.11
    x = 1111.11
    square root of 1.23457e+06: 1111.11