C++ fundamentals

This week’s section exercises focuses on exploring some C++ quirks and learning about some basic data structures. Have fun!

Each week, we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter project

1) Program analysis: C++isms you should know

Topics: Types, References, range based loops, strings, stanford C++ library

In the following, we will analyze a simple program that filters last names whose end match a specific substring. Given an input string of format:

name1,name2, ... 

and a string suffix, the program returns all the names in the input string that ends with the suffix.

#include "SimpleTest.h"
#include "vector.h"
#include "strlib.h"

using namespace std;

/*
   @param input: input string whose last names will be filtered
   @param suffix: the substring which we will filter last names by
   Functionality: this function filters the input string and returns last names
        that end with 'suffix'
*/
Vector<string> filter(string input, string suffix)
{
    Vector<string> filteredNames;
    Vector<string> names = stringSplit(input, ',');

    for (string name: names) {
        // convert to lowercase so we can easily compare the strings
        if (endsWith(toLowerCase(name), toLowerCase(suffix))) {
            filteredNames.add(name);
        }
    }
    return filteredNames;
}

STUDENT_TEST("Filter names") {
    Vector<string> results = filter("Zelenski,Szumlanski,Kwarteng", "Ski");
    EXPECT_EQUAL(results, {"Zelenski","Szumlanski"});

    results = filter("AmbaTi,Szumlanski,Tadimeti", "TI");
    Vector<string> expected = {"AmbaTi", "Tadimeti"};
    EXPECT(results == expected);

    results = filter("Zelenski,Szumlanski,Kwarteng", "NnG");
    EXPECT_EQUAL(results, {});

    // what other tests could you add?
}

2) countNumbers (count.cpp)

Topics: Vectors, strings, file reading, while true, conditional statements, Stanford C+++ library

The function countNumbers reads a text file and prints the number of times a user entered number appears in that text file. A user can continually enter numbers until they hit "Enter" or "Return" on their keyboard. Here are some library functions that will be useful for this task:

• readLines, to read all lines from a file stream into a Vector
• stringSplit, to divide a string into tokens
• getLine, to read a line of text entered by the user
• stringIsInteger, to confirm a string of digits is valid integer

In particular you will be asked to write the following function

void countNumbers(string filename)

When given the following file, named numbers.txt, as input, your function should print 1 when a user enters 42. Similarly, when the user enters another number like 9, your function should print 2. Finally, the function ends when the user presses "Return".

42 is the Answer to the Ultimate Question of Life, the Universe, and Everything
This is a negative number: -9
Welcome to CS106B!
I want to own 9 cats and 9 dogs.

/*
 * Function: countNumbers
 * ----------------------
 * Write a program to read through a given file and count the
 * the number of times a user inputed number appears in that file. You  
 * can assume that numbers will be composed entirely of numerical digits, 
 * optionally preceded by a single negative sign.
 */
void countNumbers(string filepath) {
    ifstream in;
    if (!openFile(in, filepath)) {
        return;
    }

    Vector<string> lines = readLines(in);

    while (true) {
        string number = getLine("Enter a number to check (enter to quit): ");
        if (number == "") {
            break;
        }
        if (!stringIsInteger(number)) {
            cout << "Please enter a number" <<endl;
            continue;
        }
        int count = 0;
        for (string line : lines) {
            Vector<string> tokens = stringSplit(line, " ");
            for (string t : tokens) {
                if (t == number) {
                    count ++;
                }
            }
        }
        cout << "Number " << number << " appeared " << count << " times in the file." << endl;
    }
}

3) Debugging Deduplicating (deduplicate.cpp)

Topics: Vector, strings, debugging

Consider the following incorrect C++ function, which accepts as input a Vector<string> and tries to modify it by removing adjacent duplicate elements:

⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️

void deduplicate(Vector<string> vec) {
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == vec[i + 1]) { 
            vec.remove(i);
        }
    }
}

⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️

The intent behind this function is that we could do something like this:

Vector<string> hiddenFigures = {
    "Katherine Johnson",
    "Katherine Johnson",
    "Katherine Johnson",
    "Mary Jackson",
    "Dorothy Vaughan",
    "Dorothy Vaughan"
};

deduplicate(hiddenFigures);
// hiddenFigures = ["Katherine Johnson", "Mary Jackson", "Dorothy Vaughan”]

The problem is that the above implementation of deduplicate does not work correctly. In particular, it contains three bugs. First, find these bugs by writing test cases that pinpoint potentially erroneous situations in which the provided code might fail, then explain what the problems are, and finally fix those errors in code.

// solution 1
void deduplicate(Vector<string>& vec) {
    for (int i = 0; i < vec.size() - 1; ) {
        if (vec[i] == vec[i + 1]) {
            vec.remove(i);
        } else {
            i++;
        }
    }
}

// solution 2
void deduplicate(Vector<string>& vec) {
    for (int i = vec.size() - 1; i > 0; i--) {
        if (vec[i] == vec[i - 1]) {
            vec.remove(i);
        }
    }
}

4) Grid Basics (grid.cpp)

Topic: Grids

Write a function names maxRow that takes a grid of non-negative integers(numbers from 0 to infinity) and an in-bounds grid location and returns the maximum value in the row of that grid location.

// solution1 (manally loop through the row in the grid)
int maxRow(Grid<int>& grid, GridLocation loc) {
    int max = -1;
    for (int col = 0; col < grid.numCols(); col ++) {
        if (grid[loc.row][col] > max) {
            max = grid[loc.row][col];
        }
    }
    return max;
}

// solution2(use GridLocationRange)
int maxRow(Grid<int>& grid, GridLocation loc) {
    int max = -1;
    int endCol = grid.numCols() - 1;
    for (GridLocation cell : GridLocationRange(loc.row, 0, loc.row, endCol)) {
        if (grid[cell] > max) {
            max = grid[cell];
        }
    }
    return max;
}

5) Average Neighborhood

Topic: Grids

Write a function named avgNeighborhood that takes a grid and a grid location and returns the average of all the values in the neighborhood of the grid location. A neighborhood is defined as all cells in a grid that border the grid location in all four directions(N, S, E, W). If the average is not an integer, return a truncated average.

// solution1 (we put the 4 locations in a Vector and loop over them)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
    Vector<GridLocation> possibleLocations = {
        {loc.row - 1, loc.col}, // north
        {loc.row + 1, loc.col}, // south
        {loc.row, loc.col + 1}, // east
        {loc.row, loc.col - 1}  // west
    };

    int sum = 0;
    int numValidLocations = 0;
    for (GridLocation dir : possibleLocations) {
        if (grid.inBounds(dir)) {
            sum += grid[dir];
            numValidLocations += 1;
        }
    }
    return sum / numValidLocations;
}

// solution2 (Don't do this please!! We manually get all 4 locations and sum them up)
int avgNeighborhood(Grid<int>& grid, GridLocation loc) {
    int sum = 0;
    int numValidLocations = 0;

    GridLocation north {loc.row - 1, loc.col};
    if (grid.inBounds(north)) {
        sum += grid[north];
        numValidLocations += 1;
    }

    GridLocation south {loc.row + 1, loc.col};
    if (grid.inBounds(south)) {
        sum += grid[south];
        numValidLocations += 1;
    }

    GridLocation east {loc.row, loc.col + 1};
    if (grid.inBounds(east)) {
        sum += grid[east];
        numValidLocations += 1;
    }

    GridLocation west {loc.row, loc.col - 1};
    if (grid.inBounds(west)) {
        sum += grid[west];
        numValidLocations += 1;
    }

    return sum / numValidLocations;
}

*) Setting up your environment correctly

Topics: QT Creator

• Navigate to Recommended Qt settings and set all recommended settings suggested. You'll use Qt Creator for all assignments this quarter, so it's important that you use the best settings to make you more efficient.
• Make a CS106B folder in your home directory. You can do so by:
  • Opening your finder(if you use a Mac) or Windows Explorer (if you use Windows)
  • Click on MacintoshHD for Mac or Primary Drive (C:) for windows
  • Click on Users
  • Click your name
  • Right click and make new folder.
  • Name the folder with ordinary characters, no spaces, special characters or emojis When you download new assignments and section materials, be sure to store them here. This will make it so that Qt has all the permissions it needs to run your programs
• If you use a Mac
  • Right click on this section's .pro file
  • Select Get info
  • Check that Qt Creator has been set as the default program to open .pro files. If not, choose Qt Creator from the drop down, and click on Change All
• If you use Windows
  • Open File Explorer (open any folder).
  • Click the View tab.
  • Select "File name extension" This will make it so you can see which files end with .pro
• Helpful Qt Creator hot keys (if you use windows, replace Command with Ctrl):
  • Command + B to build your program
  • Command + R to run your program
  • Command + Y to run in debug mode