23 CSS 343 Introduction and C++ Review

24 CSS 343 Introduction and C++ Review

Week 1, Session 1. CSS 343.

24.1 Welcome back

CSS 342 ended with binary trees and an invitation to do more with them. This is the more. Over the next twenty chapters we will:

Build real BSTs, balanced trees, heaps, and hash tables — the things you used as STL containers, now from the inside.
Walk graphs with BFS, DFS, Dijkstra, and minimum spanning trees.
Learn the four big algorithm design paradigms: divide-and-conquer, greedy, dynamic programming, and (in spirit) backtracking.
Build OOP at scale with design patterns.
Wrap up with a tour of regular expressions, finite automata, and Turing machines — the theory that explains why some things are easy and some are impossible.

If you took 342 with me, you know how the warmup ritual works. If you took 342 elsewhere, the How to Use This Book chapter is two minutes long and worth your time.

24.2 Warmup

Find the Middle Index in Array (#1991). The same problem we solved at the start of 342, on purpose — to remind you what you can do.

class Solution {
 public:
  int findMiddleIndex(vector<int>& nums) {
    int total = 0;
    for (int n : nums) total += n;
    int leftSum = 0;
    for (int i = 0; i < (int)nums.size(); ++i) {
      if (leftSum == total - leftSum - nums[i]) return i;
      leftSum += nums[i];
    }
    return -1;
  }
};

If you can write that in under three minutes from memory, you are ready.

24.3 Learning objectives

Describe the course structure, grading breakdown, and assignment cadence.
Trace pointer arithmetic and explain stack vs. heap allocation from memory diagrams.
Use clang-tidy and AddressSanitizer in a Makefile to catch C++ bugs.
Iterate over STL containers using both index and range-based for loops.
Explain why iterator objects decouple traversal logic from container internals.

24.4 What you should already know

Before chapter 22, you need to be comfortable with:

Pointers, new/delete, the Rule of Three (chapters 4, 5, 7).
Templates (chapter 8).
Recursion (chapter 9).
BST insert, search, and the basic traversals (chapter 17).
Big-O analysis (chapter 13).

If any of these are fuzzy, re-read the relevant 342 chapter now. The pace from chapter 22 onward assumes them.

24.5 A real Makefile

In 342 we got away with one-line g++ commands. In 343, we use proper Makefiles. Here is the minimum:

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++17 -g
SAN = -fsanitize=address,undefined -fno-omit-frame-pointer

SRCS = main.cpp BST.cpp Node.cpp
OBJS = $(SRCS:.cpp=.o)
TARGET = bst

all: $(TARGET)

$(TARGET): $(OBJS)
    $(CXX) $(CXXFLAGS) $(SAN) $(OBJS) -o $(TARGET)

%.o: %.cpp
    $(CXX) $(CXXFLAGS) $(SAN) -c $< -o $@

clean:
    rm -f $(OBJS) $(TARGET)

Then make builds. make clean resets. Adding a new file means adding it to SRCS and rerunning make.

There are many Makefile styles. Mine is intentionally minimal. By P3 you should be modifying this Makefile without thinking. Real engineers spend a lot of time fighting build systems. Start now.

24.6 clang-tidy and AddressSanitizer

We will use these on every assignment. If your code passes -Wall -Wextra and clang-tidy and AddressSanitizer with zero issues, it is in good shape.

# AddressSanitizer (find memory bugs at runtime)
g++ -fsanitize=address -fno-omit-frame-pointer ...

# clang-tidy (static analysis)
clang-tidy main.cpp -- -std=c++17

# clang-format (style enforcement)
clang-format -i main.cpp

The 7-step validation pipeline (from my standards-first teaching philosophy):

Compiles with no warnings (-Wall -Wextra).
Runs and produces correct output on the sample input.
clang-tidy finds no issues.
clang-format finds no issues.
No memory leaks (AddressSanitizer).
No memory leaks (valgrind, second opinion).
Tests have full coverage.

If your code fails any of these, fix it before declaring “done.”

24.7 Iterators — a first peek

Every STL container exposes .begin() and .end() returning iterator objects. An iterator behaves like a pointer:

vector<int> v = {10, 20, 30};
auto it = v.begin();
cout << *it << endl;    // 10
++it;
cout << *it << endl;    // 20

The container itself decides what an iterator is. For vector, it is essentially a pointer into the array. For list, it is a pointer to the next node. For map, it is a pointer to a tree node. The user does not care — the interface is the same.

This is the Iterator pattern (a design pattern we will name in Chapter 35): the data structure exposes a uniform way to walk over its contents without revealing how it stores them.

template <typename T>
class MyContainer {
 public:
  class Iterator {
   public:
    Iterator(T* p) : p_(p) {}
    T& operator*() { return *p_; }
    Iterator& operator++() { ++p_; return *this; }
    bool operator!=(const Iterator& o) const { return p_ != o.p_; }
   private:
    T* p_;
  };

  Iterator begin() { return Iterator(data_); }
  Iterator end() { return Iterator(data_ + size_); }
  // ...
};

Implement those four (operator*, operator++, operator!=, plus begin/end) and range-based for works on your class. C++ asks for very little to be a “range.”

24.8 Try it

Set up a Makefile for a project with three files: main.cpp, BST.cpp, BST.h. The BST can be empty/stub. Build it with make. Confirm AddressSanitizer is enabled by adding a deliberate memory leak (int* leak = new int(5); and no delete) and running. ASan should print the leak.

24.9 Self-check

1. Why use a Makefile instead of one-line g++ commands?

a. Makefiles compile faster than g++.
b. Only changed files need to recompile; build steps are reproducible and documented.
c. Makefiles are required by C++.
d. They give you better stack traces.

b. Incremental compilation and reproducibility — the same reason every real project uses one.

2. The minimum operations a class must implement to support range-based for are:

a. size(), get(int)
b. operator[], operator=
c. begin(), end(), and the iterator's *, ++, !=
d. Multiple inheritance from iterator

c. Range-based for desugars to for (auto it = c.begin(); it != c.end(); ++it).

24.10 Challenges

Write a generic Counter<T> class that wraps an array and supports range-based for. Iterate with for (auto x : counter).
Design Circular Queue (#622) — class design exercise.
Set up your environment for the quarter: Makefile, .clang-format, .clang-tidy, valgrind/ASan working. This is P1 prep.

24.11 Where this fits

The on-ramp. Next chapter dives into binary trees — the territory we ended 342 on, now with rigor.

You are here	Coming up
343 logistics, dev environment, iterator pattern preview	Chapter 22: trees and BST operations, deeper