Chapter map

Where this sits in CS 300. Chapter 1 is the runway. Every later chapter (linked lists, stacks/queues, trees, hash tables, heaps, graphs) assumes you already reach for std::vector without thinking, know when indexing is O(1) and when it isn’t, and can trace a loop by hand. If any of that is shaky, the rest of the course compounds the confusion.

What you add to your toolkit here:

A sharp mental model of contiguous storage — arrays and std::vector — including what’s fast (back-end ops, random access) and what’s slow (insert/erase in the middle).
A library of iteration patterns: running best, counter, in-place transform, paired scan — these come back in every later chapter disguised as “traverse the list/tree/graph.”
Value semantics in C++: copying, comparing, passing by reference, and the cost of accidentally making a deep copy.
C-string survival so you can read legacy code without panicking, plus the std::string / cctype upgrades.

Mastery checklist — you should be able to, without references:

Write a for loop that scans a vector<int> keeping a running max and the index where it occurred, in one pass.
State the Big-O of push_back, pop_back, insert(begin(), x), erase(it), and at(i), and say why.
Explain why resize(n) and a loop of push_back produce the same end state but differ in initial values and in performance.
Swap two elements of a vector correctly with and without std::swap, and point out why a = b; b = a; fails.
Convert a small parallel-vectors design into a vector<Struct> and explain the tradeoff.
Reverse a vector in place correctly on the first try (loop bound $n/2$ , swap by temp).
Read a C-string character-by-character, classify with cctype, and explain why strcmp returns an int, not a bool.

Looking ahead. Chapter 2 formalizes problem-solving strategies (recursion, greedy, DP); chapter 3 formalizes the cost analysis (Big-O) that you’re using intuitively here; chapter 4 introduces the linked-list alternative to vectors, and every performance comparison in that chapter is a comparison against what you learned here.

1.1 Arrays and Vectors (general concept)

The motivation: one name, many values

A regular variable holds one value. That is fine when you have a handful of distinct things to track (a wage and a salary), but it falls apart the moment you need a list: the four quarter scores of a basketball game, 365 daily temperature readings, every bid in an auction. Nobody wants to declare score1, score2, score3, score4 — and declaring temperature_001 through temperature_365 is absurd.

A useful analogy: a normal variable is a truck with one cargo bay; an array is a train whose cars are all coupled together and numbered, but which you still call by one name.

Indexing

The essential feature of an array is direct access: given an index, you can read or write the element at that position in constant time, without scanning from the front. You write this with bracket notation in most languages:

myArray[2]       // element at index 2

Zero-based indexing

In C, C++, Java, Python, and most languages you will meet, the first element is at index 0, not 1. An array with 4 elements has valid indices 0, 1, 2, 3 — not 1, 2, 3, 4.

This is not a pointless quirk. The index is the offset from the start of the array. Element 0 is 0 slots from the start; element 3 is 3 slots from the start. The math in the box above works out cleanly because of it.

Arrays vs. vectors

Some languages distinguish between arrays (fixed size, set at creation) and vectors (resizable, can grow or shrink). Coral uses the word array loosely; C++ gives you both:

1.2 Vectors (in C++)

This is where the course drops the Coral training wheels and starts writing real C++. A std::vector is the C++ workhorse container — the one you reach for by default when you need an ordered list — and essentially every CS 300 project uses it.

Declaring a vector

Two things have to happen before you can use a vector in a source file:

#include <vector>     // bring in the vector type
std::vector<int> gameScores(4);   // declare a vector of 4 ints

The piece in angle brackets is the element type — the kind of value every element will hold. The number in parentheses is the initial size.

Accessing elements

You have two ways to read or write an element:

v.at(i)   // bounds-checked: throws std::out_of_range if i is invalid
v[i]      // not bounds-checked: undefined behaviour if i is invalid

Indices start at 0, same as arrays. A vector with 4 elements has valid indices 0, 1, 2, 3. The index can be any non-negative integer expression — a literal, a variable, the result of arithmetic. It cannot be a floating-point value (v.at(1.0) will not compile).

Nth-oldest lookup

std::vector<int> oldestPeople = {122, 119, 117, 117, 116};
int n;                          // user's 1-based pick
std::cin >> n;
if (n >= 1 && n <= 5) {
    std::cout << oldestPeople.at(n - 1);  // translate 1-based -> 0-based
}

Note the n - 1: the user thinks “the 1st oldest person,” but internally that is index 0. This is one of the most common places off-by-one bugs sneak in.

Size, looping, and `size_t`

Every vector knows its current length via v.size(). The classic indexed loop over every element:

for (std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v.at(i);
}

For read-only traversals, the modern and much cleaner form is the range-based for loop:

for (int value : v) {
    std::cout << value;
}

No index, no bounds to worry about. Use this whenever you do not actually need i.

Initialisation

Four common patterns:

std::vector<int> a(5);               // 5 elements, each 0
std::vector<int> b(5, -1);           // 5 elements, each -1
std::vector<int> c = {3, 1, 4};      // 3 elements, listed explicitly
std::vector<int> d;                  // empty; push_back later

Pattern d is by far the most common in the projects — you start empty and push_back each bid as you read the CSV.

Common errors

Missing #include <vector> — the compiler does not know what vector is, and the error message is spectacularly unhelpful (“ISO C++ forbids declaration of vector with no type”).
Missing std:: or using namespace std; — same error, same fix.
Out-of-range access with [] — no crash, no diagnostic, wrong data. If you cannot reproduce a bug, suspect this first.
Signed/unsigned comparison in the loop — warning, not error, but occasionally causes an infinite loop if i goes negative.

1.3 Array / Vector Iteration Drill

The textbook presents this section as three interactive drills with no textual content:

find the maximum value,
count the negatives,
bubble the largest value to the end.

Each drill is a specific instance of a general pattern. Writing those patterns out once makes the drills easier — and more importantly, every iterative algorithm later in the course is a remix of them.

Pattern 1 — Linear scan with a running “best”

Find the maximum.

int maxVal = v.at(0);                // seed with the first element
for (std::size_t i = 1; i < v.size(); ++i) {
    if (v.at(i) > maxVal) {
        maxVal = v.at(i);
    }
}

Find the minimum.

Same pattern, flip the comparison: if (v.at(i) < minVal).

Find the index of the maximum.

When you need the position (e.g., for sorting), track i instead of the value:

std::size_t maxIdx = 0;
for (std::size_t i = 1; i < v.size(); ++i) {
    if (v.at(i) > v.at(maxIdx)) {
        maxIdx = i;
    }
}

Pattern 2 — Linear scan with a running counter

Count the negatives.

int negCount = 0;
for (std::size_t i = 0; i < v.size(); ++i) {
    if (v.at(i) < 0) {
        ++negCount;
    }
}

The same shape solves “how many even numbers,” “how many bids above $100,” “how many strings start with A.” The condition changes; the structure does not.

Running sum / running product.

A tiny variation: instead of incrementing by 1, accumulate the element itself. sum += v.at(i) gives a total; product *= v.at(i) gives a product (seed with 1, not 0).

Pattern 3 — One selection-sort pass

The third drill asks you to move the largest value to the last position of the array. This is exactly one pass of selection sort, and it combines Patterns 1 (find the max index) with a swap:

// After this loop, the largest value sits at v.back().
std::size_t maxIdx = 0;
for (std::size_t i = 1; i < v.size(); ++i) {
    if (v.at(i) > v.at(maxIdx)) {
        maxIdx = i;
    }
}
std::swap(v.at(maxIdx), v.at(v.size() - 1));

Range-based form

When you do not need the index, the same three patterns read much more cleanly:

int maxVal = v.at(0);
for (int x : v) { if (x > maxVal) maxVal = x; }

int negCount = 0;
for (int x : v) { if (x < 0) ++negCount; }

Use the indexed form when you need i (e.g., for the swap in Pattern 3) and the range-based form otherwise.

1.4 Iterating Through Vectors

Section 1.3 covered the patterns (running best, counter, scan-plus-swap). This section is about the loop idiom those patterns are built on, and about the standard-library tools that often replace the loop entirely.

Anatomy of the canonical loop

The loop shape you will type thousands of times in C++:

for (std::size_t i = 0; i < v.size(); ++i) {
    // work with v.at(i) or v[i]
}

Three pieces, each doing one job:

Init: std::size_t i = 0.
Declares the loop counter inside the for header so it does not leak into the surrounding scope. size_t is the type v.size() returns; matching it silences the “signed/unsigned comparison” warning. Start at 0 because indices are zero-based.
Condition: i < v.size().
Continue while i is a valid index. Valid indices for a vector of length $n$ are $0, 1, \ldots, n{-}1$ . The last valid index is v.size() - 1, not v.size(), which is why the condition is strict less-than.
Update: ++i.
Advance to the next index. Prefer ++i to i++; see the aside below.

< vs.\ <=

Writing i <= v.size() runs the loop one too many times and calls v.at(v.size()), which throws std::out_of_range. The error looks like:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check

Fix: use <, not <=. Every time.

Empty loops and infinite loops

Two classic mistakes with the for header:

Missing condition — for (i = 0; ; ++i). With no condition the loop never exits on its own. It will eventually walk off the end of the vector and crash.
Condition that never becomes false — for (i = 0; i < 99; ++i) over a vector of 365 elements visits only the first 99; a condition referring to something that is not the vector’s size is nearly always a bug. Use v.size() so the loop adapts to whatever the vector actually is.

Reverse iteration with size_t

It is tempting to iterate backwards with for (std::size_t i = v.size() - 1; i >= 0; –i). This is an infinite loop. size_t is unsigned — it cannot go negative. After i == 0, –i wraps around to a gigantic positive number. Safe patterns:

// Loop while i > 0, then handle 0 separately:
for (std::size_t i = v.size(); i-- > 0; ) {
    // i now takes values size-1, size-2, ..., 0
}

or use a signed counter when the index arithmetic needs to go negative.

Common errors

Out-of-range access with .at() throws std::out_of_range (program aborts unless you catch it). With [] it is silent undefined behaviour. Bounds-check the index whenever it came from the user.
Seeding maxVal or minVal with 0. Covered in 1.3. Seed with v.at(0) instead.
Mixing signed and unsigned in the comparison. int i vs. v.size() produces warnings and can surprise you if i ever goes negative. Use size_t.

The standard-library alternative

Most of the loops in 1.3 and this section have a one-liner equivalent in <algorithm> and <numeric>. Knowing these saves a surprising amount of noise in your code:

#include <algorithm>
#include <numeric>

// Sum of all elements
int total = std::accumulate(v.begin(), v.end(), 0);

// Maximum element (returns an iterator; dereference with *)
int maxVal = *std::max_element(v.begin(), v.end());

// Count elements matching a condition
int negCount = std::count_if(v.begin(), v.end(),
                             [](int x) { return x < 0; });

1.5 Multiple Vectors

The parallel-vectors technique

Sometimes the thing you need to store has more than one field per “row.” A standard example pairs country names with the average minutes of TV watched per day in each country:

std::vector<std::string> ctryNames(5);
std::vector<int>         ctryMins(5);

ctryNames.at(0) = "China";   ctryMins.at(0) = 155;
ctryNames.at(1) = "Sweden";  ctryMins.at(1) = 154;
ctryNames.at(2) = "Russia";  ctryMins.at(2) = 246;
ctryNames.at(3) = "UK";      ctryMins.at(3) = 216;
ctryNames.at(4) = "USA";     ctryMins.at(4) = 274;

The convention: same index, same row. Index 3 means “UK, 216 minutes,” no matter which vector you look in. To search, you scan one vector for the key and read the matching index in the other:

for (std::size_t i = 0; i < ctryNames.size(); ++i) {
    if (ctryNames.at(i) == userCountry) {
        std::cout << ctryMins.at(i) << '\n';
        break;              // early exit once we find it
    }
}

Short-circuiting the search

The textbook uses a flag variable to stop the loop early:

bool foundCountry = false;
for (i = 0; (i < ctryNames.size()) && (!foundCountry); ++i) {
    if (ctryNames.at(i) == userCountry) {
        foundCountry = true;
        /* ... */
    }
}

This works, but it is not the cleanest form. Two better options:

break out of the loop directly — no flag, one less variable to reason about.

std::find from <algorithm> expresses “scan for a value” in one line:

auto it = std::find(ctryNames.begin(), ctryNames.end(), userCountry);
if (it != ctryNames.end()) {
    std::size_t i = it - ctryNames.begin();  // index from iterator
    std::cout << ctryMins.at(i) << '\n';
}

Why parallel vectors are a smell

Parallel vectors are a reasonable starting technique, but they are fragile. Two specific ways they go wrong:

They drift out of sync. Insert into one vector and forget the other; now index 3 means “UK, 246 minutes” instead of “UK, 216.” The compiler will not warn you.
They do not scale past two or three fields. When a “row” has ten fields you end up with ten vectors you have to keep in lockstep — and every operation (sort, delete, filter) has to touch all of them.

The real answer: a vector of structs

In practice you group related fields into a single struct (or class) and keep one vector of those. The TV example rewritten the right way:

struct Country {
    std::string name;
    int         minutesTV;
};

std::vector<Country> countries = {
    {"China",  155},
    {"Sweden", 154},
    {"Russia", 246},
    {"UK",     216},
    {"USA",    274},
};

for (const Country& c : countries) {
    if (c.name == userCountry) {
        std::cout << c.minutesTV << '\n';
        break;
    }
}

One collection, fields that cannot drift apart, a single sort will move names and minutes together. This is the form the CS 300 projects use: a Bid struct with bidId, title, fund, amount, stored in a std::vector<Bid>. Parallel vectors appear in intro material because structs have not yet been introduced; you will almost never write them outside an intro exercise.

When parallel vectors are actually okay

Two niches:

Temporary scratch data — e.g., during sorting you sometimes need a parallel “order of original indices” vector.
Performance-critical numerical code — storing each field contiguously (“struct of arrays” layout) can make SIMD and cache behaviour better. This is a microoptimisation you will not need in CS 300.

1.6 Vector Resize

Declaring without a size

The size given in the declaration is not mandatory:

std::vector<int> carSales;   // empty: size 0, no elements yet

At this point any access — carSales.at(0), carSales[0], carSales.front() — is invalid, because there is nothing there. You have to grow the vector first.

`resize(n)`

resize(n) sets the vector’s size to exactly n.

If n is larger than the current size, new elements are appended at the end. They are default-initialised: 0 for numeric types, empty string for std::string, default-constructed for your own structs/classes.
If n is smaller, the extra elements at the end are destroyed. Anything stored past index n-1 is gone — no warning, no recycle bin.
If n equals the current size, resize does nothing.

std::vector<int> v;
v.resize(3);     // v is now {0, 0, 0}
v.at(0) = 122;
v.at(1) = 11;
v.at(2) = 7;     // v is {122, 11, 7}

v.resize(2);     // v is {122, 11}; the 7 is gone
v.at(2);         // throws std::out_of_range

`resize()` vs. `push_back()` — which one?

Two different grow-the-vector strategies, and it is worth knowing when each fits.

Two ways to read $n$ user values

Resize first (the textbook’s preferred style):

int n;
std::cin >> n;
v.resize(n);
for (std::size_t i = 0; i < v.size(); ++i) {
    std::cin >> v.at(i);
}

Push-back as you go:

int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    v.push_back(x);
}

Both leave v with n elements. The difference is who knows the count up front. When the count is known in advance, either works. When the count is not known — “read bids until end-of-file” — push_back is the only sensible choice, because you cannot call resize with a number you do not have yet.

Size, capacity, and `reserve()` (what intro texts omit)

A vector tracks two numbers, not one:

When you push_back and size is about to exceed capacity, the vector allocates a bigger internal buffer (typically $1.5\times$ or $2\times$ the old capacity), copies everything over, and frees the old buffer. That reallocation is $O(n)$ — but because it happens geometrically less often as the vector grows, the amortised cost of push_back is $O(1)$ .

If you know ahead of time roughly how big the vector will get, you can skip the intermediate reallocations with reserve:

std::vector<Bid> bids;
bids.reserve(10000);         // capacity -> 10000, size still 0
for (/* each CSV row */) {
    bids.push_back(parseRow(row));  // no reallocations
}

v.clear() — empty the vector (size becomes 0; capacity usually untouched).
v.pop_back() — remove the last element; shrinks size by 1.
v.empty() — returns true when size is 0. Prefer v.empty() to v.size() == 0 because on some containers (not vector, but good habit) size() is not $O(1)$ .

shrink_to_fit() and the no-auto-shrink policy

std::vector grows automatically but never shrinks automatically. If you push 10 000 items then pop 9 999, the vector’s size is 1 but its capacity is still $\geq 10\,000$ — the unused buffer sits there. v.shrink_to_fit() requests a release, but the standard explicitly allows the implementation to ignore it (non-binding). To force the buffer down, swap with an empty vector:

std::vector<int>().swap(v);   // capacity collapses to 0 (or near it)

This contrasts with Python’s list (and some Java ArrayList settings), which actively shrink the backing buffer when too empty. The C++ default prioritizes reusing already-allocated memory over reclaiming it — usually what you want, occasionally not.

1.7 Vector push_back, back, and pop_back

Section 1.6 already introduced push_back as a way to grow a vector one element at a time. The real value of this section is that it completes the “back of the vector” interface — push_back, back, pop_back — which, taken together, turn a plain vector into a perfectly good stack.

The three back-end operations

pop_back() returns void

A classic beginner mistake:

std::cout << v.pop_back();   // ERROR: pop_back returns void

The textbook flags this but does not explain it, so here it is: pop_back separates “give me the last value” from “remove the last value.” If you want both, call back() first, then pop_back():

int last = v.back();   // read the value
v.pop_back();          // then drop it
std::cout << last;

The reason the standard library splits them is exception safety: if returning the value could throw (copy-constructor of a heavy object, out-of-memory), a “pop-and-return” would have to somehow unwind a successful removal. Splitting the operations sidesteps the problem — and happens to be faster too, since back() returns a reference without copying.

Vector as a stack

In fact the C++ standard library’s std::stack is a thin wrapper around exactly this pattern. You will meet it formally in Chapter 4.

Why the back is fast, the front is slow

A common question: why is there no push_front in the headline interface?

This asymmetry is the reason std::vector makes a great stack but a poor queue. A queue needs $O(1)$ on both ends; a vector does not offer that.

Worked example: building a list by reading input

The CS 300 pattern

Almost every project in this course builds a vector by reading an unknown number of rows from a file. The shape is:

std::vector<Bid> bids;
std::string line;
while (std::getline(file, line)) {
    bids.push_back(parseBid(line));
}

Because you do not know up front how many rows the CSV has, you cannot resize in advance — push_back in a loop is the natural fit. After the loop, bids.size() tells you how many rows were read.

Small gotchas

back() on an empty vector is undefined behaviour — the reference it returns refers to nothing. Always test !v.empty() first when you are not sure.
pop_back() on an empty vector is also undefined behaviour.
A reference from back() is invalidated by a later push_back if the push triggers a reallocation. Read the value, use it, then push — do not hold a reference across a push.

1.8 Modifying, Copying, and Comparing Vectors

Three distinct topics in one source-text section. The unifying idea, and the thing to walk away with, is that a std::vector has value semantics: assignment copies the data, equality compares the data, and two vectors that were equal a moment ago can diverge without affecting each other.

Modifying elements in a loop

You read an element with v.at(i); you write one with v.at(i) = newValue. There is nothing special about writing during a loop — the same index works for both directions:

// Clamp every negative value to 0.
for (std::size_t i = 0; i < v.size(); ++i) {
    if (v.at(i) < 0) {
        v.at(i) = 0;
    }
}

The range-based form

is just as happy — but the loop variable has to be a reference or you will be modifying a copy:

for (int& x : v) {        // note the &
    if (x < 0) x = 0;
}

Shifting patterns — the direction matters

The two superficially similar left/right shifts in the textbook exercises produce very different results because of the order the writes happen:

Left shift -- overwrites ahead of the read

for (i = 0; i < 3; ++i) {
    v.at(i) = v.at(i + 1);
}
// {-55, -1, 0, 9}  ->  {-1, 0, 9, 9}

Each write happens before its source is read, so the shift works correctly from left to right. The last element is duplicated because nothing is to its right to pull from.

Right shift -- clobbers the data it is about to read

for (i = 0; i < 3; ++i) {
    v.at(i + 1) = v.at(i);
}
// {-55, -1, 0, 9}  ->  {-55, -55, -55, -55}

Here each iteration writes into the slot the next iteration needs to read. The original data gets smeared across the vector. To right-shift correctly you have to walk from the end backwards.

Vector copy with `=`

Assigning one vector to another copies every element:

std::vector<int> origPrices = {10, 20, 30, 40};
std::vector<int> salePrices;

salePrices = origPrices;     // deep copy: salePrices is now {10, 20, 30, 40}
salePrices.at(2) = 27;       // does NOT affect origPrices

Vector comparison with `==`

== compares two vectors element-by-element: true if they have the same size and every element pair is equal.

std::vector<int> x = {3, 4};
std::vector<int> y = {3, 4, 0, 7, 8};
std::vector<int> z = {3, 4, 0, 6, 8};

x == y;   // false: different sizes
y == z;   // false: same size, but index 3 differs
y == y;   // true

Worth knowing, since 1.6 introduced capacity:

a = b always at minimum resets a’s size. If b is larger than a’s capacity, the internal buffer is reallocated.
A push_back that crosses the capacity threshold reallocates — any references or iterators you were holding into the vector are now stale.
Capacity grows but does not shrink on its own; see the shrink_to_fit warnbox in .

1.9 Swapping Two Variables

Swapping looks trivial until you write it. The instinct x = y; y = x; overwrites x before its original value is ever used, so both variables end up holding y’s value and the old x is gone. The fix is to save it somewhere first.

Why the naïve version fails

The broken swap

int x = 33, y = 55;
x = y;   // x is now 55 -- the old 33 is GONE
y = x;   // y is now 55 (the new x), not 33

After the first line there is no copy of 33 left anywhere in the program. The second line cannot recover what was just overwritten.

The temp-variable pattern

Correct swap with a temporary

int x = 33, y = 55;
int temp = x;   // save x
x = y;          // clobber x -- fine, it's saved
y = temp;       // restore the saved value into y

Three lines, one extra variable, always correct. The order matters: save first, then do the overwrite, then use the saved copy.

C++ shortcut: `std::swap`

C++ gives you the pattern for free in <utility> (or <algorithm> in older standards), and you should almost always use it instead of writing the temp-variable version by hand.

std::swap

#include <utility>

int x = 33, y = 55;
std::swap(x, y);   // x == 55, y == 33

It works on any type that supports move (or copy) assignment: int, std::string, std::vector, your own classes. For vector and string, std::swap is O(1) — it swaps the internal pointers, not the elements.

Swapping list elements

Most real swaps are between two positions in a vector, not between two free-standing variables. Reversing a vector is the canonical example: swap index 0 with n-1, index 1 with n-2, and so on, stopping at the middle.

Reverse a vector in place

#include <vector>
#include <utility>

std::vector<int> v = {10, 20, 30, 40, 50};
for (size_t i = 0; i < v.size() / 2; ++i) {
    std::swap(v[i], v[v.size() - 1 - i]);
}
// v is now {50, 40, 30, 20, 10}

The loop runs n/2 times; integer division handles the odd-length case correctly because the middle element swaps with itself and can be skipped.

1.10 Debugging Example: Reversing a Vector

The previous section gave the finished, correct reversal loop. This section walks through the three bugs a first attempt typically hits, in the order they surface, because the debugging process is the real lesson. Loop-plus-vector code is where most early C++ bugs live, and the tracing technique used here works for everything later in the course.

The buggy starting point

Imagine writing this without thinking too hard:

Attempt 0 -- two bugs in three lines

for (size_t i = 0; i < v.size(); ++i) {
    v.at(i) = v.at(v.size() - i);   // "swap"
}

There are at least three things wrong here. Each one only becomes visible after you fix the previous one, which is why tracing matters more than guessing.

Bug 1: off-by-one on the mirror index

Bug 2: assignment is not a swap

After fixing the index, the loop runs without crashing but produces the wrong output — values appear duplicated and others disappear:

Tracing attempt 1

Input 10 20 30 40 50 60 70 80, loop body v.at(i) = v.at(v.size() - 1 - i);

i=0: v[0] = v[7]  ->  80 20 30 40 50 60 70 80
i=1: v[1] = v[6]  ->  80 70 30 40 50 60 70 80
i=2: v[2] = v[5]  ->  80 70 60 40 50 60 70 80
i=3: v[3] = v[4]  ->  80 70 60 50 50 60 70 80   // 40 is gone
i=4: v[4] = v[3]  ->  80 70 60 50 50 60 70 80

The original value at v[0] was overwritten before it was copied anywhere. This is the same bug as the naïve two-line swap from : assignment copies one way only.

The fix is the temp-variable swap (or std::swap):

int tmp = v.at(i);
v.at(i) = v.at(v.size() - 1 - i);
v.at(v.size() - 1 - i) = tmp;

Bug 3: the loop runs twice as long as it should

After fixing the swap, the output comes out identical to the input. The swap is correct this time; the loop just runs too many iterations:

Tracing attempt 2

i=0: swap v[0] and v[7]  ->  80 20 30 40 50 60 70 10
i=1: swap v[1] and v[6]  ->  80 70 30 40 50 60 20 10
i=2: swap v[2] and v[5]  ->  80 70 60 40 50 30 20 10
i=3: swap v[3] and v[4]  ->  80 70 60 50 40 30 20 10  // reversed
i=4: swap v[4] and v[3]  ->  80 70 60 40 50 30 20 10  // un-reversed
i=5: swap v[5] and v[2]  ->  ...                      // etc.

Once the midpoint is crossed, every further swap un-does an earlier one. The loop bound must be i < v.size() / 2.

The debugging methodology, not the answer

The final correct version was already given in . What matters here is the technique:

Read the error. out_of_range pointed straight at an index expression. Don’t skip the stack trace.
Trace by hand. Write out the vector contents after each iteration on paper or in a comment. Bugs 2 and 3 are invisible from the source but obvious after three lines of trace output.
Fix one bug at a time. Each fix exposes the next bug. Changing three things at once means you will not know which change did what.
Use .at() during development. Turn silent out-of-bounds into exceptions. Switch to [] later if you have measured that bounds checking is a bottleneck (it rarely is).

1.11 Arrays vs. Vectors

C++ inherits the raw C array and also provides std::vector. They look similar on the surface — indexed access, contiguous storage — but they have very different safety and feature profiles. For this course the rule is simple: use std::vector unless a concrete reason forces otherwise.

Syntax side-by-side

Declaration and access

// C-style array: fixed size at compile time
int a[5];                 // 5 ints, uninitialized!
a[0] = 42;
int x = a[0];

// std::vector: size known at runtime, grows if needed
#include <vector>
std::vector<int> v(5);    // 5 ints, all zero-initialized
v.at(0) = 42;             // bounds-checked
int y = v.at(0);
int z = v[0];             // also works, NOT bounds-checked

Why arrays are dangerous

An out-of-range write to a C array does not throw, does not warn, does not even necessarily crash. It just scribbles over whatever happens to live at that memory address.

The classic memory-corruption bug

int weights[3];
int age = 44;

weights[0] = 122;
weights[1] = 119;
weights[2] = 117;
weights[3] = 199;   // out of range -- writes into age!

std::cout << age;   // prints 199 (on many compilers)

The compiler lays weights and age next to each other in memory. Writing weights[3] lands on age’s bytes. Nothing stops it. The program appears correct until something later reads age and gets a nonsense value — possibly hours of debugging away from the real bug.

With std::vector the same mistake using .at() throws std::out_of_range immediately, pointing at the exact line.

Feature comparison

::: center Feature C array std::vector

Size fixed at compile time^*^ runtime Can grow / shrink no yes Knows its own size no yes (.size()) Bounds checking available no yes (.at()) Copy with = no (decays to pointer) yes (deep copy) Pass to function as pointer + length as value or const& Compare with == no (pointer compare) yes (element-wise) :::

^*^C99 variable-length arrays exist but are a GCC extension in C++ and should be avoided.

When arrays still show up

You will not eliminate arrays from your C++ code — they appear in places you cannot avoid:

String literals are arrays: "hello" is a const char[6].
argv in main(int argc, char* argv[]) is a C-style array of C-style strings.
Legacy C APIs (POSIX, Win32, most game engines) take pointer-plus-length pairs.
Embedded / performance code sometimes needs the stack-only, zero-overhead guarantee of a raw array.

For the fixed-size cases where you would be tempted to use a C array, prefer std::array<T, N> — it has a compile-time size like a C array but carries .size(), .at(), iterators, and value semantics like a vector.

std::array as the safe fixed-size choice

#include <array>

std::array<int, 3> weights = {122, 119, 117};
weights.at(3) = 199;   // throws std::out_of_range
int n = weights.size();  // 3, known at compile time

1.12 Two-Dimensional Arrays

A 2D array is a table: R rows $\times$ C columns, for R * C elements total. The language lets you write a[r][c] and pretend you are indexing a grid, but underneath, memory is flat. Knowing how the rows are laid out explains cache performance, how to pass 2D data to functions, and why std::vector<std::vector<T>> is not actually a 2D array.

Declaring and using

Basic 2D array

int grid[2][3];              // 2 rows, 3 cols, 6 ints total

grid[0][0] = 55;
grid[1][2] = 99;

// Brace-initialization makes the shape visible:
int numVals[2][3] = {
    {22, 44, 66},   // row 0
    {97, 98, 99}    // row 1
};

Iterating: the loop order matters

The idiomatic nested loop walks the outer (row) index first, the inner (column) index second:

Passing a 2D array to a function

This is where raw 2D arrays bite. The compiler needs to know the row length to compute r * C + c, so all dimensions except the first must be spelled out in the parameter type:

Three equivalent signatures

void f(int a[2][3], int rows);   // literal dimensions
void f(int a[][3], int rows);    // first dim can be omitted
void f(int (*a)[3], int rows);   // pointer to row (same thing)

The C++ alternative: `std::vector` of `vector`

For runtime-sized 2D data the common idiom is a vector of vectors.

2D as a vector-of-vectors

#include <vector>

int R = 4, C = 5;
std::vector<std::vector<int>> grid(R, std::vector<int>(C, 0));

grid[1][2] = 99;          // same syntax as a 2D array
grid.size();              // R
grid[0].size();           // C

This is flexible — rows can even have different lengths — but the rows are not contiguous in memory. Each inner vector is a separate heap allocation, and cache behavior suffers accordingly.

Flat 1D storage is often better

For true matrix work the trick is to store one vector of R * C elements and compute the index yourself:

std::vector<int> grid(R * C);
auto at = [&](int r, int c) -> int& { return grid[r * C + c]; };
at(1, 2) = 99;

One allocation, contiguous memory, same big-O as a raw 2D array, plus .size() and bounds-checked iteration. This is how most numerical C++ code represents 2D data.

Higher dimensions

int a[2][3][5] declares 30 elements; int a[100][100][5][3] declares 150 000. Dimensions multiply, and stack-allocated arrays can blow the stack surprisingly fast. If any dimension is large, allocate with std::vector (heap) rather than a raw array.

1.13 Char Arrays / C Strings

Before std::string existed, a string in C was just an array of chars ending with a special sentinel byte. C++ still supports this representation — it’s what you get from string literals, command-line arguments, and every legacy C API you will ever link against — so it is worth understanding even though modern C++ code should use std::string.

Declaring a C string

Three equivalent declarations

char movie[20] = "Star Wars";  // explicit size, rest zero-filled
char name[] = "Hellen";        // size inferred: 7 ('H','e','l','l','e','n','\0')
char city[5] = {'A','l','a','n','\0'};  // character-by-character

In every case the compiler (or you) must make room for the trailing ’\0’. For the literal "Amy", char name[4] is the minimum — three letters plus the null.

Why printing “just works”

std::cout << some_c_string does not print 20 characters. It prints characters one at a time until it sees ’\0’. That convention runs through every C string API — printf, strlen, strcpy, file I/O — which is why a missing or overwritten null byte turns into a memory-corruption bug instead of a tidy error.

Three common bugs

1. Looping to the array size instead of to the null

char s[20] = "hello";
for (int i = 0; i < 20; ++i)  cout << s[i];   // WRONG

Prints hello then 14 bytes of whatever happens to sit after the visible text. Correct loop:

for (int i = 0; s[i] != '\0'; ++i)  cout << s[i];

2. Looping past the array entirely

for (int i = 0; i < 30; ++i)  cout << s[i];   // UB

Reads memory that is not part of s at all. May print garbage, may crash, may appear to work. This is undefined behavior.

3. Overwriting the null terminator

char name[5] = "Alan";   // {'A','l','a','n','\0'}
name[4] = '!';           // null is gone
cout << name;            // prints "Alan!" then keeps going...

The next cout walks off the end of the array looking for a ’\0’. It might hit one quickly (harmless-looking output) or run for a long time printing junk (obvious garbage) — the bug is nondeterministic.

You cannot assign to a C string

The assignment that doesn't assign

char title[20] = "Star Wars";
title = "Indiana Jones";   // ERROR: array name is not an lvalue

A C array’s name is not a variable you can reassign. To copy characters into an existing buffer, use strcpy or strncpy from <cstring>:

#include <cstring>
std::strcpy(title, "Indiana Jones");  // title must be big enough!

C strings vs. `std::string`

::: center C string (char[]) std::string

Header <cstring> <string> Stores length no (scan for \0) yes (.size()) Assignable with = no yes Concat with + no yes Resizes automatically no yes Bounds-checked access no .at() :::

std::string gives you a C string on demand

Every C++ string carries a null-terminated char buffer internally. Call s.c_str() to get a const char* suitable for passing to a legacy C API:

std::string path = "data.txt";
std::FILE* f = std::fopen(path.c_str(), "r");

This is how you bridge modern C++ code to C libraries.

1.14 String Library Functions

Because C strings do not know their own length and do not support = or ==, the standard library ships a family of free functions that take raw char* pointers and walk them looking for the null terminator. They all live in <cstring> (the C++ name) or <string.h> (the C name). You will recognize most of them from any C tutorial.

Modifying strings

::: center

strcpy(dst, src) Copy src (through null) into dst. strncpy(dst, src, n) Copy up to n chars. strcat(dst, src) Append src to the end of dst. strncat(dst, src, n) Append up to n chars, then a null.

:::

strcpy / strcat basics

#include <cstring>
char org[100] = "United Nations";
char user[20] = "UNICEF";
char target[10];

std::strcpy(target, user);   // target == "UNICEF"
std::strcat(org, user);      // org    == "United NationsUNICEF"

Destination comes first, source second — same order as target = source; in regular C++. Swapping the arguments is a classic beginner bug and the compiler cannot catch it.

strcpy does not check the destination size

char target[10];
std::strcpy(target, org);   // org is 14 chars -- writes 4 past the end!

No exception, no error — just silent memory corruption. This is the canonical buffer-overflow bug. Use strncpy(dst, src, sizeof dst) if you must, and note even strncpy does not guarantee a trailing null when the source is exactly n characters long.

Array-name assignment still does not copy

target = user;     // ERROR: array name is not an lvalue

The only place = copies a C string is in the declaration itself, because the compiler is initializing the array, not performing a real assignment:

char user[20] = "UNICEF";    // OK, compile-time initialization

Inspecting strings

::: center

strlen(s) Returns number of chars before the null (type size_t). strcmp(a, b) $<0$ if a < b, 0 if equal, $>0$ if a > b. strncmp(a, b, n) Same, limited to first n chars. strchr(s, ch) Pointer to first ch in s, or NULL. strstr(hay, needle) Pointer to first occurrence of needle, or NULL.

:::

Length, search, compare

size_t n = std::strlen("Alan Turing");     // 11

if (std::strchr(name, ' ') != nullptr) { /* has a space */ }

if (std::strcmp(s1, s2) == 0)  { /* equal */ }
if (std::strcmp(s1, s2) < 0)   { /* s1 comes first */ }

The three `strcmp` traps

These come up constantly and none of them are syntax errors — the compiler will not catch any of them.

1. Using == on C strings

if (s1 == s2) { ... }   // compares POINTER addresses, not content

Two character arrays will almost never share an address, so this branch is effectively dead. Silent logic bug.

2. Forgetting == 0

if (std::strcmp(s1, s2)) { ... }   // backwards!

strcmp returns 0 when equal. Treating the result as a boolean reads “truthy means equal,” which is the opposite of what it actually means. Always write == 0 explicitly — your future self, reading the code cold, should not have to remember the convention.

3. strlen on a buffer that has no null

char buf[10];             // no initializer
size_t n = std::strlen(buf);   // walks memory until it hits any 0 byte

Undefined behavior. If you declare a C-string buffer, either initialize it (char buf[10] = "";) or do not call string-library functions on it until you have written real content plus a terminator.

A common pattern: transform characters in place

Replace spaces with underscores

#include <cstring>
char name[15] = "Alan Turing";

for (size_t i = 0; i < std::strlen(name); ++i) {
    if (name[i] == ' ') name[i] = '_';
}

This loop re-scans the whole string every iteration because strlen is O(n). For long strings, hoist it:

size_t len = std::strlen(name);
for (size_t i = 0; i < len; ++i) { ... }

Or stop at the null byte directly, which is the idiomatic form:

for (size_t i = 0; name[i] != '\0'; ++i) { ... }

The modern C++ translation

Every function in this section has a cleaner std::string equivalent that does not buffer-overflow and knows its own size.

::: center C C++ (std::string)

strcpy(dst, src) dst = src; strcat(dst, src) dst += src; strlen(s) s.size() strcmp(a, b) == 0 a == b strcmp(a, b) < 0 a < b strchr(s, ch) s.find(ch) strstr(h, n) h.find(n) :::

1.15 Char Library Functions: `cctype`

<cctype> is the C++ header for classifying and converting individual char values — “is this letter a digit?” “convert this to uppercase.” It’s tiny, and every function takes an int, returns an int, and is named issomething or tosomething. Learn the short list and you have 95% of the character-manipulation toolbox.

Classification: “is this character a …?”

All of these return an int — nonzero for true, 0 for false. You will usually use them in an if condition directly.

::: center

isalpha(c) alphabetic: a—z or A—Z isdigit(c) decimal digit: 0—9 isalnum(c) isalpha or isdigit isspace(c) space, tab, newline, CR, vertical tab, form-feed isblank(c) just space or tab islower(c) / isupper(c) a—z / A—Z isxdigit(c) hex digit: 0—9, a—f, A—F ispunct(c) printable, not space, not alphanumeric isprint(c) printable (includes space) iscntrl(c) control char — the complement of isprint

:::

Classifying characters in a string

#include <cctype>
char s[] = "Hey9! Go";

std::isalpha(s[0]);  // 'H' -> nonzero (true)
std::isdigit(s[3]);  // '9' -> nonzero (true)
std::isspace(s[5]);  // ' ' -> nonzero (true)
std::ispunct(s[4]);  // '!' -> nonzero (true)

Conversion: `toupper` and `tolower`

Both take a character and return a (possibly different) character. If the input isn’t a letter of the relevant case, the function returns it unchanged — so you can apply it to every character in a string without branching.

Uppercase the whole string in place

#include <cctype>
char s[] = "Hey9! Go";

for (size_t i = 0; s[i] != '\0'; ++i) {
    s[i] = std::toupper(static_cast<unsigned char>(s[i]));
}
// s is now "HEY9! GO"

A concrete use case: case-insensitive compare

strcmp is case-sensitive. "Apple" and "apple" are not equal to it. The standard trick is to lowercase both sides and compare.

Case-insensitive equality for C strings

bool equal_ci(const char* a, const char* b) {
    while (*a && *b) {
        char ca = std::tolower(static_cast<unsigned char>(*a));
        char cb = std::tolower(static_cast<unsigned char>(*b));
        if (ca != cb) return false;
        ++a; ++b;
    }
    return *a == *b;   // both must now be '\0'
}

The C++20 alternative: ranges + lambdas

When you are already using std::string (and you should be), the loop gets shorter and the cast disappears into the algorithm.

Uppercase with std::transform

#include <algorithm>
#include <cctype>
#include <string>

std::string s = "Hey9! Go";
std::transform(s.begin(), s.end(), s.begin(),
    [](unsigned char c){ return std::toupper(c); });
// s == "HEY9! GO"

The lambda parameter is declared unsigned char so the cast happens automatically at the call site — cleaner than scattering static_cast through a loop body.

Parsing pattern: extract digits from a string

This pops up in every intro assignment that asks you to pull a phone number, zip code, or ID out of user input:

Keep only digits

#include <cctype>
#include <string>

std::string phone = "(603) 555-1212";
std::string digits;
for (unsigned char c : phone) {
    if (std::isdigit(c)) digits.push_back(c);
}
// digits == "6035551212"

Summary

Chapter 1 is a whirlwind review of the C++ building blocks every later data-structures topic assumes. The threads worth carrying forward:

Prefer safe abstractions. std::vector over raw arrays, std::string over char[], .at() over [] while debugging. Every C-flavored alternative has a silent-failure mode that costs more to debug than the bounds-checked version costs to run.
Indices are contracts. size_t is unsigned; v.size() - 1 underflows catastrophically on an empty vector; a 2D index is r * C + c under the hood. Treat every index expression as something to verify, not guess.
Copy is not free. Vector copy is O(n); passing a big container by value does a deep copy. Use const& when you only read, & when you mutate, and move semantics when ownership transfers. Value semantics are the reason all of this feels sane compared to C.
Algorithms over loops. accumulate, max_element, count_if, find, reverse, swap, transform — the <algorithm> header already has the loop you were about to write. Reach for it first.
Debug by tracing, not by staring. When a loop produces the wrong output, print the state after every iteration. Three bugs in a ten-line reversal loop were only findable that way.
Vectors are the runway for the whole course. Stacks, queues, hash tables, and heaps will all be built on top of std::vector or the indexing pattern it exposes. The habits you lock in here — correct sizing, bounds checking, pass-by-reference, reserve-before-loop — will carry through every remaining chapter.

What this connects to

Chapter 2 takes the loops and iteration patterns you learned here and reframes them as problem-solving strategies (recursion, greedy, DP). The loops don’t change; the way you decide which loop to write does.
Chapter 3 formalizes the cost analysis you’ve been doing intuitively (“push_back is cheap, insert at the front is not”). Big-O is the notation; the underlying mechanisms — shifting, reallocation, amortization — are exactly what you practiced here.
Chapter 4 introduces linked lists as the alternative to contiguous storage. Every performance argument in that chapter is phrased as “compared to a vector, $\ldots$ ” — so the more solid your vector intuitions are here, the faster ch. 4 lands.
Chapter 5+ (stacks, queues, deques) are built on top of vector and linked-list primitives. The push_back/pop_back pattern from 1.7 is the stack interface.

Companion materials. A two-page compact notes reference for this chapter lives at chapters/ch_1/notes.tex; twelve drill prompts you can paste into a fresh Claude session live at chapters/ch_1/practice.md. Use the notes to review, the prompts to test.

1.1 Arrays and Vectors (general concept)

The motivation: one name, many values

Indexing

Zero-based indexing

Arrays vs. vectors

1.2 Vectors (in C++)

Declaring a vector

Accessing elements

Size, looping, and size_t

Initialisation

Common errors

1.3 Array / Vector Iteration Drill

Pattern 1 — Linear scan with a running “best”

Find the maximum.

Find the minimum.

Find the index of the maximum.

Pattern 2 — Linear scan with a running counter

Count the negatives.

Running sum / running product.

Pattern 3 — One selection-sort pass

Range-based form

1.4 Iterating Through Vectors

Anatomy of the canonical loop

Empty loops and infinite loops

Common errors

The standard-library alternative

1.5 Multiple Vectors

The parallel-vectors technique

Short-circuiting the search

Why parallel vectors are a smell

When parallel vectors are actually okay

1.6 Vector Resize

Declaring without a size

resize(n)

resize() vs. push_back() — which one?

Size, capacity, and reserve() (what intro texts omit)

Related operations

1.7 Vector push_back, back, and pop_back

The three back-end operations

Vector as a stack

Why the back is fast, the front is slow

Worked example: building a list by reading input

Small gotchas

1.8 Modifying, Copying, and Comparing Vectors

Modifying elements in a loop

The range-based form

Shifting patterns — the direction matters

Vector copy with =

Vector comparison with ==

Related: does the vector’s backing memory move?

1.9 Swapping Two Variables

Why the naïve version fails

The temp-variable pattern

C++ shortcut: std::swap

Swapping list elements

1.10 Debugging Example: Reversing a Vector

The buggy starting point

Bug 1: off-by-one on the mirror index

Bug 2: assignment is not a swap

Bug 3: the loop runs twice as long as it should

The debugging methodology, not the answer

1.11 Arrays vs. Vectors

Syntax side-by-side

Why arrays are dangerous

Feature comparison

When arrays still show up

1.12 Two-Dimensional Arrays

Declaring and using

Iterating: the loop order matters

Passing a 2D array to a function

The C++ alternative: std::vector of vector

Higher dimensions

1.13 Char Arrays / C Strings

Declaring a C string

Why printing “just works”

Three common bugs

You cannot assign to a C string

C strings vs. std::string

1.14 String Library Functions

Modifying strings

Size, looping, and `size_t`

`resize(n)`

`resize()` vs. `push_back()` — which one?

Size, capacity, and `reserve()` (what intro texts omit)

Vector copy with `=`

Vector comparison with `==`

C++ shortcut: `std::swap`

The C++ alternative: `std::vector` of `vector`

C strings vs. `std::string`

The three `strcmp` traps

1.15 Char Library Functions: `cctype`

Conversion: `toupper` and `tolower`