std::vector: The Array Done Right

RAII, applied to a growable array

Lesson 6-2 introduced RAII wrappers like unique_ptr, which free heap memory automatically in their destructor when the owning object's scope ends. The release is tied to the destructor, and the destructor runs on every path out of scope.

std::vector, this lesson's subject, is exactly that idea applied to a growable heap array. It allocates, resizes, and frees its own storage, so you never write new[] or delete[] yourself.

The STL (Standard Template Library) is a big reason experienced engineers pick C++ for interviews: professionally implemented containers and algorithms, with known performance guarantees, one #include away. Without it you would be hand-writing (and hand-debugging) the IntArray class from lesson 7-2 before every problem. This unit covers the two containers you will touch in almost every program.

The container you will use most

std::vector<T> (from <vector>) is a growable array of T, the C++ equivalent of a Python list, except every element has the same type:

#include <vector>

std::vector<int> v;          // empty
v.push_back(10);             // append, like Python's .append
v.push_back(20);
std::vector<int> w = {1, 2, 3};   // initialize with values

v[0]        // element access, no bounds check
v.at(0)     // element access, throws if out of range
v.size()    // number of elements
v.back()    // last element
v.pop_back()  // remove last element
v.empty()   // true if size is 0

Under the hood it is a heap array managed with RAII: when the vector grows past its current capacity it allocates a bigger block (roughly double) and moves the elements over. Appending at the end is therefore fast on average, and everything is freed automatically when the vector dies.

The angle brackets are a template parameter: std::vector<double>, std::vector<std::string>, even std::vector<std::vector<int>> for a grid.

A tour of vector: build, index, grow, shrink

One vector taken through the operations you will use most often, with the size printed after each change.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};

    v.push_back(40);
    std::cout << "size: " << v.size() << "\n";
    std::cout << "first: " << v[0] << " last: " << v.back() << "\n";

    v.pop_back();
    std::cout << "after pop, size: " << v.size() << "\n";

    for (int i = 0; i < (int)v.size(); i++) {
        std::cout << v[i] << "\n";
    }
    return 0;
}

Output

size: 4
first: 10 last: 40
after pop, size: 3
10
20
30

Both push_back and pop_back work at the end of the vector, and that is not an arbitrary limitation. Appending or removing at the end leaves every other element where it is, while inserting at the front would have to shift all of them.

pop_back returns nothing, unlike Python's list.pop(), so reading the last value means calling v.back() before removing it. The cast in (int)v.size() is there because size() is unsigned, which the next block explains.

Reading input into a vector

The pattern from lesson 3-3, upgraded to keep the values:

int n;
std::cin >> n;
std::vector<int> v(n);        // n elements, all 0
for (int i = 0; i < n; i++) {
    std::cin >> v[i];
}

std::vector<int> v(n) pre-sizes the vector, parentheses not braces (v{n} would be a one-element vector containing n). Alternatively start empty and push_back each value.

One caution: v.size() has an unsigned type, so comparing it with a signed int draws warnings. Casting like (int)v.size(), or using int n = v.size(); once, keeps loops clean.

A 2D grid as a vector of vectors

Because a vector's element type can itself be a vector, a grid is simply a vector of rows. This is the standard representation for matrices, game boards, and every island-counting interview problem:

// 3 rows, 4 columns, all cells start at 0
std::vector<std::vector<int>> grid(3, std::vector<int>(4, 0));

grid[1][2] = 7;        // row 1, column 2
grid.size()            // 3, the number of rows
grid[0].size()         // 4, the number of columns

The constructor call reads as making 3 copies of std::vector<int>(4, 0), which is itself a row of four zeros. The two-argument form of the constructor means a count followed by the value to repeat, so the same shape works at both levels.

Iterating uses the nested loops from lesson 3-3, with the outer loop over rows and the inner one over columns. Indexing follows the same order, so grid[r][c] is row first and column second, and swapping them is one of the most common bugs in grid code.

Note that the row count and column count come from different expressions, grid.size() and grid[0].size(). Nothing forces the rows to be equal lengths, so a vector of vectors can be ragged, and grid[0].size() is only the width if you built it uniformly.

Creating and indexing a grid

A 3-by-4 grid of zeros with one cell written, then its dimensions read back from the structure itself.

#include <iostream>
#include <vector>

int main() {
    std::vector<std::vector<int>> grid(3, std::vector<int>(4, 0));
    grid[1][2] = 7;
    std::cout << grid.size() << " rows, " << grid[0].size() << " cols\n";
    std::cout << grid[1][2] << "\n";
    return 0;
}

Output

3 rows, 4 cols
7

Changing the constructor to grid(5, std::vector<int>(2, 0)) gives 5 rows of 2 columns, and both printed numbers follow automatically because they are read from the grid rather than hardcoded. That is the habit to build, since a dimension written as a literal in a loop condition will eventually disagree with the data.

Every cell starts at 0 thanks to the second constructor argument, so grid[1][2] was a defined 0 before the assignment. This is a real difference from the raw new int[n] of lesson 6-1, which left its elements holding whatever bytes were already in memory.

One performance note for later: a vector of vectors stores each row in a separate heap block, so the rows are not contiguous with each other. For very large numerical grids, a single flat vector indexed as flat[r * cols + c] is faster because it keeps the whole grid in one cache-friendly block.

Reading n values and printing them backwards

The input pattern combined with a descending loop, which is the standard way to walk a vector from the end.

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;

    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        std::cout << v[i] << "\n";
    }
    return 0;
}

Input

4
5 8 1 9

Output

9
1
8
5

The reverse loop starts at n - 1 because that is the last valid index, and it uses >= 0 rather than > 0 so the first element is included. Both of those are off-by-one traps, and using > 0 would silently drop the 5.

There is a subtler trap hiding in this loop. Written with an unsigned counter, as for (size_t i = n - 1; i >= 0; i--), it would never terminate, because an unsigned value can never be less than 0 and decrementing past 0 wraps around to a huge number. That is a concrete reason to keep loop counters as plain int and cast size() when comparing, exactly as the previous block advised.

Reading directly into v[i] works because the vector was pre-sized with v(n), so all n elements already exist. Had it been declared empty, v[i] would be writing outside the vector, which is undefined behavior rather than an automatic growth, and push_back would be required instead.