vector: Many Boxes That Grow by Themselves

Amara types her class's marks into a program, one per line, until she reaches the end of the pile. She does not know how many papers there are. In the C track's Module 14 this was malloc, realloc, a capacity variable and, for most of us, one bug. In C++ it is one line inside a loop: marks.push_back(x);. This lesson shows that line, and what it does behind your back.

The problem: you do not know how many

A C array is sized before the program runs. If the input is longer than the array, you overflow it. If it is shorter, the extra boxes sit unused. A vector is the C++ answer. It is a row of boxes of one type, like an array, that grows by itself when you add to the end. It lives in the header <vector>, and its full name is std::vector.

Here is Amara's program. It reads marks until the input ends, then prints how many it read and their average.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long total = 0;
    for (int m : marks) {
        total += m;
    }
    cout << marks.size() << " marks\n";
    cout << "average " << (double)total / marks.size() << '\n';
    return 0;
}

5 marks
average 71.2

That output is for the input 70 85 62 91 48. There is no size anywhere in the program. while (cin >> x) stops when the input ends, as Module 1 showed, and each push_back adds one mark at the end. So the vector ends up exactly as long as the input.

Zara runs it on an empty input, as she always does first. It prints 0 marks and then average -nan, because 0.0 / 0 is not a number. Examples 2 and 3 below check for an empty vector before they divide or read.

Boxes in a row, and boxes that grow

A vector keeps its elements side by side in one block of memory, exactly like a C array. An element is one box. The block usually has a few spare boxes at the end, so the next push_back has somewhere to go.

That gives a vector two numbers. Its size is how many elements it holds now. Its capacity is how many boxes the block has room for. The size is never more than the capacity. In the C track, you kept these two numbers yourself, in two variables. A vector keeps both for you.

So the size is what you stored, and the capacity is the room the vector has already set aside.

The syntax you need on day one

#include <vector>

vector<T> v;                  an empty vector of T
vector<int> v(n, 0);          n elements, every one 0
vector<int> v{1, 2, 3};       exactly these three elements
v.push_back(x);               add x at the end
v[i]                          the element at index i, 0 to v.size() - 1
v.size()                      how many elements it holds
v.empty()                     true when it holds none

So a vector is declared with its element type in angle brackets, and everything else is a call on it with a dot.

Four ways to make one

You will make vectors in four shapes. This program makes one of each and prints its size and its elements.

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

void show(const char* name, const vector<int>& v) {
    cout << name << ": size " << v.size() << " [";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << " ]\n";
}

int main() {
    vector<int> empty_one;
    vector<int> zeros(5);
    vector<int> sevens(5, 7);
    vector<int> listed{3, 1, 4};

    show("empty_one", empty_one);
    show("zeros", zeros);
    show("sevens", sevens);
    show("listed", listed);
    return 0;
}

empty_one: size 0 [ ]
zeros: size 5 [ 0 0 0 0 0 ]
sevens: size 5 [ 7 7 7 7 7 ]
listed: size 3 [ 3 1 4 ]

The table reads the four lines back.

Unlike a C array without an initialiser, vector<int> v(n) never holds garbage. Its elements start at 0. The helper show takes the vector by const&, Module 1's read-only second name, so no copy is made. So round brackets give a count, and braces give a list. Keep that in mind for the brain teaser.

push_back, and reading until the input ends

push_back is the call you will write most. In a loop over the input, it turns "I do not know how many" into "I do not need to know". When you do know n, you can still read into an empty vector with push_back, or size it first and read by index. Both are correct.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    cout << "a has " << a.size() << ", b has " << b.size() << '\n';
    return 0;
}

a has 3, b has 4

That output is for the input 3, then 10 20 30, then 7 8 9 6. The first loop reads exactly n values into boxes that already exist. The second takes whatever is left. So a[i] fills an element that is already there, and push_back makes a new one.

What happens inside when it runs out of room

When push_back finds the block full, the vector cannot simply stretch it. The memory after the block may belong to something else. So it does four things. It asks for a new, bigger block. It copies every element across. It frees the old block. Then it adds the new element. This is a reallocation.

Watch it happen. This program pushes five marks into an empty vector. After each call it prints the size, the capacity, and whether the elements now live in a new block. data() returns where the block starts, so a changed data() means the vector moved.

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

int main() {
    vector<int> marks;
    int input[] = {70, 85, 62, 91, 48};
    for (int x : input) {
        const int* before = marks.data();
        marks.push_back(x);
        cout << "push_back(" << x << "): size " << marks.size()
             << ", capacity " << marks.capacity();
        if (marks.data() != before) {
            cout << ", new block";
        }
        cout << '\n';
    }
    return 0;
}

push_back(70): size 1, capacity 1, new block
push_back(85): size 2, capacity 2, new block
push_back(62): size 3, capacity 4, new block
push_back(91): size 4, capacity 4
push_back(48): size 5, capacity 8, new block

Step through the same five calls below. Each step shows the block before and after, and how many elements were copied.

On our compiler the capacity doubles: 1, 2, 4, 8, and on to 16 and 32. The C++ standard does not fix the factor. It only promises that push_back costs constant time on average over many calls. So copying is rare: most calls just fill a spare box, and lesson 05 does the arithmetic.

So push_back is cheap almost every time, and now and then it moves the whole vector.

Indexing, and the last index

The elements of a vector are numbered like an array's, from 0. A vector of size n has indexes 0 to n - 1. The last element is v[v.size() - 1], and lesson 02 shows the shorter v.back().

Bob prints Amara's marks. He wants to be sure he reaches the last one, so he writes <=.

vector<int> marks{70, 85, 62, 91, 48};
for (int i = 0; i <= marks.size(); i++) {
    cout << marks[i] << ' ';
}

On the Playground this compiled with no message and ended with Success. It printed 70 85 62 91 48 0. The last number, 0, is marks[5]. That box is not an element. It is whatever sat in memory just past the block. This is the same silent bug as the C track's array lesson, because v[i] checks nothing. On another day, or another machine, that 0 can be any number, or a crash.

The fix is i < marks.size(). You will write <= because "up to the size" sounds as if it includes the size. So an index is in range when 0 <= i and i < v.size(). Lesson 02 shows at(), which checks.

size() is an unsigned number

v.size() does not return an int. It returns size_t, an unsigned type: a whole number that can never be negative. On the Playground it is 64 bits wide. So below 0 it wraps around, as unsigned numbers did in the C track's Module 2.

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

int main() {
    vector<int> v;
    cout << "size: " << v.size() << '\n';
    cout << "size - 1: " << v.size() - 1 << '\n';
    return 0;
}

size: 0
size - 1: 18446744073709551615

Zara tests the empty input first, always. She runs Bob's "last index" loop on an empty vector.

vector<int> v;
for (int i = 0; i <= v.size() - 1; i++) {
    cout << v[i] << '\n';
}

Bob expected zero passes. v.size() - 1 is 18446744073709551615, so the test i <= ... stays true and the loop reads far past the empty vector. On the Playground it ended with Runtime error, after printing nothing.

The Playground compiles without -Wall, so it says nothing. With -Wall -Wextra on your own machine, GCC 12 warns about the mix of types: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]. Write i < v.size(), which is 0 < 0 and false, or check v.empty() first. So never subtract from size() until you know the vector is not empty.

The range-for walks every element

When you need every element in order and not the index, the range-for from Module 1 is the clearest loop. for (int m : marks) gives you a copy of each element. for (int& m : marks) gives you a second name for each one, so a change reaches the vector.

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

int main() {
    vector<int> marks{70, 85, 62};

    for (int m : marks) {
        m += 5;
    }
    cout << "after the copy loop:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';

    for (int& m : marks) {
        m += 5;
    }
    cout << "after the reference loop:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';
    return 0;
}

after the copy loop: 70 85 62
after the reference loop: 75 90 67

So read with int m (or const int& m for big elements), and change with int& m. A range-for never goes past the end, so it cannot make Bob's mistake.

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

int main() {
    vector<double> temps;
    temps.push_back(21.5);
    temps.push_back(23.0);
    temps.push_back(19.75);

    cout << temps.size() << " readings\n";
    for (size_t i = 0; i < temps.size(); i++) {
        cout << "temps[" << i << "] = " << temps[i] << '\n';
    }
    return 0;
}

3 readings
temps[0] = 21.5
temps[1] = 23
temps[2] = 19.75

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> marks;
    int x;
    while (cin >> x) {
        marks.push_back(x);
    }
    if (marks.empty()) {
        cout << "no marks\n";
        return 0;
    }

    int best = marks[0];
    cout << "marks:";
    for (int m : marks) {
        cout << ' ' << m;
        if (m > best) {
            best = m;
        }
    }
    cout << '\n' << marks.size() << " marks, highest " << best << '\n';
    return 0;
}

marks: 70 85 62 91 48
5 marks, highest 91

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> prices;
    int p;
    while (cin >> p) {
        prices.push_back(p);
    }

    if (prices.empty()) {
        cout << "no prices\n";
        return 0;
    }

    long long total = 0;
    for (size_t i = 0; i < prices.size(); i++) {
        cout << "item " << i + 1 << ": " << prices[i] << '\n';
        total += prices[i];
    }
    cout << "total: " << total << '\n';
    cout << "last item: " << prices[prices.size() - 1] << '\n';
    return 0;
}

item 1: 120
item 2: 45
item 3: 300
item 4: 80
total: 545
last item: 80

vector<int> marks;
for (int i = 0; i < 3; i++) {
    cin >> marks[i];
}

#include <iostream>
using namespace std;

int main() {
    vector<int> marks;
}

int n = 3;
vector<int> marks(n);
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    marks.push_back(x);
}

vector<int> marks{70, 85};
cout << marks << '\n';

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

int main() {
    vector<int> kenji(5);
    vector<int> maria{5};
    cout << kenji.size() << ' ' << maria.size() << '\n';
    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // Print the marks from the last element back to the first,
    // on one line, separated by single spaces.

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // Pass 1: add every temperature into a long long.
    // Pass 2: print the ones above the average, or "none".

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    cin >> k;
    vector<int> songs;
    int s;
    while (cin >> s) {
        songs.push_back(s);
    }

    // Print songs.size() songs, starting at index k % songs.size(),
    // wrapping back to index 0 after the last one.

    return 0;
}

Next, Kenji's program inserts at the front of a vector in a loop and runs slowly. Lesson 02 puts a cost on every operation to find out why.