std::vector: The Array Done Right

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.

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.

Worked example: a 2D grid

Because a vector's element type can itself be a vector, a grid is a vector of rows. This is the standard representation for matrices, game boards, and every "number of islands"-style 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: make 3 copies of std::vector<int>(4, 0) (a row of four zeros). Iterate with the nested loops from lesson 3-3: outer over rows, inner over columns.