Arrays and vectors

An array keeps $n$ values in cells with indices 0 to n - 1, and reads or changes any cell by its index in $O(1)$ time. A vector is the C++ array that knows its size and can grow at the end.

How it works

The cells of an array lie side by side in memory, in order. One place in the array is a cell, its number is its index, and what it holds is its value. Cell $i$ lies $i$ cells after the first one, so the computer finds it with one addition. That is why a[3] takes the same time in an array of 6 cells and in an array of a million. This is also why indices start at 0: the first cell lies 0 cells after itself.

Fig. 1. Six cells with indices from 0. a[3] is the value 9. There is no cell 6.

Vector

An array has a fixed number of cells. Once they are all used, nothing more fits, so a fixed array has to be made as big as the largest input can need. A vector solves this by growing when it runs out of cells.

It can't just take the cell right after its last one: that memory may belong to something else. So it keeps a block with some spare cells at the end. The number of cells in the block is the vector's capacity. When no spare cell is left, the vector takes a new block with twice the capacity, copies every value into it and frees the old block. Copying takes time, so a vector is convenient, not free.

The vector holds 3 in a block of 4 cells, so its capacity is 4. The grey cells are spare.

7 is pushed into a spare cell.

1 is pushed into a spare cell.

9 is pushed into a spare cell. Now the block is full.

4 is pushed, but there is no spare cell. The vector takes a new block of 8 cells.

It copies 3, 7, 1 and 9 into the new block. That is 4 values copied.

It writes 4 after them.

It frees the old block. The capacity is 8 now.

6 is pushed into a spare cell of the new block. Nothing is copied.

1/9

Fig. 2. A vector of capacity 4 grows to 8. Blue is the value just pushed, light blue the values copied into the new block.

An empty vector has capacity 0. The first push takes a block of 1 cell, and every growth doubles the capacity: 1, 2, 4, 8, and so on. After $n$ pushes, the last copy moved fewer than $n$ values, and all the copies before it together moved fewer than that, because each block was half the size of the next. In all, fewer than $2n$ values are copied, so push_back takes $O(1)$ time on average, although now and then a single push copies the whole vector.

In C++

Fixed-size array

int a[6]; makes an array of 6 cells, a[0] to a[5]. Its size must be a constant known when the program is written, so it is taken from the constraints:

const int MAXN = 100005;
int a[MAXN];   // outside main: every cell starts at 0

Declared outside main, every cell starts at 0; inside main, the cells hold leftover values until you write them. int a[n]; with a variable n is not standard C++.

std::vector

The vector is in the header <vector>. vector<int> a(n); makes n cells, all 0, and vector<int> a; makes an empty vector. These are its main operations:

The reverse-order program reads n (1 \le n \le 10^5) and then n integers (|x| \le 10^9), and prints them in reverse order, separated by spaces. The array from Fig. 1 is this input:

6
3 7 1 9 4 6

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    // read
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // print backwards
    for (int i = n - 1; i >= 0; i--) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

It takes $O(n)$ time and memory. The fixed array int a[MAXN]; above would work here too, and both are equally fast for a[i]. Use a vector by default: its size can come from the input, and it can grow.

When the count isn't given, start with an empty vector and push each number as it is read. The loop stops when the input ends, and then a.size() is the count:

vector<int> a;
int x;
while (cin >> x) {
    a.push_back(x);
}

Two-dimensional vectors

A cinema hall is a table: here 3 rows of 4 seats, where 1 marks a sold seat and 0 a free one.

Fig. 3. The hall as a table. g[1][2] is row 1, column 2: a free seat.

A table is a vector of rows, and each row is a vector. vector<vector<int>> g(n, vector<int>(m)); makes n rows of m zeros. g[r][c] is row r, column c, both from 0. g.size() is the number of rows and g[0].size() the number of columns.

The hall program reads n and m (1 \le n, m \le 500), then n lines of m values 0 or 1, and prints the number of sold seats in each row. The hall above is this input:

3 4
1 0 0 1
1 1 0 0
0 1 1 1

In the second loop, for (int x : g[r]) gives x each value of row r in turn.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));

    // read the hall row by row
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            cin >> g[r][c];
        }
    }

    // count sold seats in each row
    for (int r = 0; r < n; r++) {
        int sold = 0;
        for (int x : g[r]) {
            sold += x;
        }
        cout << sold << ' ';
    }
    cout << '\n';
}

It takes $O(nm)$ time and memory. Rows can also have different lengths: vector<vector<int>> g(3); g[0].push_back(5); g[2].push_back(1); g[2].push_back(4); gives rows of lengths 1, 0 and 2. An adjacency list is built this way: row v holds the numbers linked to v.

Passing a vector to a function

A function with a parameter vector<int> a gets a copy of the vector. Changes to the copy are lost when the function returns, and making the copy takes $O(n)$ time on every call. With vector<int>& a the function works on the caller's vector itself:

void doubleAll(vector<int>& a) {
    for (int i = 0; i < (int)a.size(); i++) {
        a[i] *= 2;
    }
}

On a vector holding 3 7 1, this makes it 6 14 2. Without the & the caller's vector stays 3 7 1. When a function only reads the vector, write const vector<int>& a: no copy is made, and the compiler rejects any line that changes a.

Examples of use

A counting array keeps in cell x how many times the value x has appeared: cnt[x]++ for each value read. For values from $-2000$ to $2000$, use cell x + 2000, because a negative index is out of range. Counting sort is built on it. Prefix sums and dynamic programming also keep one value per cell, and sort(a.begin(), a.end()) sorts a vector.

Common mistakes

• Starting the reverse loop at n, as in for (int i = n; i >= 0; i--), which reads cell n past the end. Start at n - 1, or loop with i < n.

• Problems number seats and days from 1, but a vector of size n ends at cell n - 1, so a[n] is out of range. Make the vector a(n + 1) and leave cell 0 unused, or subtract 1 from every number as you read it.

• vector<int> a; followed by cin >> a[i] in a loop writes into cells that don't exist, because the size is 0. Give the size, a(n), or use push_back.

• vector<vector<int>> g(n); makes n empty rows, so g[1][2] is out of range. Write g(n, vector<int>(m)).

• A fixed array declared inside main starts with garbage, not zeros, and a large one can crash the program before it reads anything. Declare fixed arrays outside main, or use a vector, which can be large anywhere.

Similar structures

A string is a vector of characters with operations for text. A stack is a vector used only at the end, through push_back, back and pop_back. A queue lets values leave from the front, where a vector would move every other cell. A deque is like a vector, but adding and removing at the front also takes $O(1)$ time. A map is for indices up to 10^9 or indices that aren't numbers: a vector of 10^9 int cells needs 4 GB.

Practice