Every vector Operation, One by One, With Its Cost

Kenji reads 100,000 numbers and needs them in reverse order. So he inserts each new number at the front of a vector, and his program takes a third of a second. Amara writes push_back instead and walks the vector backwards. Hers takes half a millisecond, about six hundred times faster. Both programs are correct. The difference is one line of this lesson: the cost of each call.

How to read a cost line

Every operation below ends with a one-row table: the call, its cost, and why. The cost is written in big-O notation. It says how the work grows as the vector grows, not how many nanoseconds it takes.

Every cost here is the one the C++ standard requires, and you can check each on its cppreference page, as Module 0 showed. So a cost line is a promise about growth, true on every compiler.

push_back and pop_back

push_back(x) adds x after the last element. pop_back() removes the last element and returns nothing. To use the last value, read it with back() first.

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

int main() {
    vector<int> v{10, 20};
    v.push_back(30);
    cout << "after push_back: size " << v.size() << ", last " << v.back() << '\n';
    v.pop_back();
    cout << "after pop_back: size " << v.size() << ", last " << v.back() << '\n';
    return 0;
}

after push_back: size 3, last 30
after pop_back: size 2, last 20

Watch: pop_back() on an empty vector is undefined behaviour. On the Playground it ended with Success, and size() afterwards printed 18446744073709551615. The vector's end moved one step before its start, and nothing stopped it. Check !v.empty() before every pop_back whose input you do not control.

emplace_back(args) is push_back's sibling. It builds the element in place from its parts, so v.emplace_back(3, 4) on a vector<pair<int, int>> adds the pair (3, 4). Its cost is the same. So both calls add at the end, and only the end is cheap.

size, empty and capacity

Three questions you can ask any vector, each answered from the handle without touching the elements.

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

int main() {
    vector<int> v;
    cout << v.size() << ' ' << v.empty() << ' ' << v.capacity() << '\n';
    v.push_back(7);
    v.push_back(8);
    v.push_back(9);
    cout << v.size() << ' ' << v.empty() << ' ' << v.capacity() << '\n';
    return 0;
}

0 1 0
3 0 4

Watch: empty() prints as 1 or 0 because it is a bool. It does not empty anything; clear() does. So if (v.empty()) is a question, never an action.

operator[] and at

Both read or write the element at index i. v[i] trusts you. v.at(i) checks that i is less than size() first, and stops the program with an exception when it is not.

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

int main() {
    vector<int> v{10, 20, 30, 40, 50};
    v[1] = 25;
    v.at(2) = 35;
    cout << v[1] << ' ' << v.at(2) << '\n';
    cout << v.at(5) << '\n';
    return 0;
}

On the Playground the run ended with Runtime error. The output pane was empty, and the error stream said this:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

Read the second line: the index you asked for, and the size it broke. Even 25 35 never appeared. cout was still holding that line in its buffer when the program stopped. A crash skips the flush, as Module 1's lesson on fast input and output warned. Compare Bob's v[v.size()] in lesson 01, which printed a quiet 0 and was Success. A loud stop is better than a wrong answer that looks right.

Watch: use at() while you write and test, especially with indexes computed from input. Contest code uses [], because a checked index costs a comparison on every access. So [] is the fast promise and at() is the checked one.

front and back

v.front() is the first element, v[0]. v.back() is the last, v[v.size() - 1], without the subtraction to get wrong.

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

int main() {
    vector<int> temps{18, 21, 25, 19};
    cout << "first " << temps.front() << ", last " << temps.back() << '\n';
    temps.back() = 20;
    cout << "last now " << temps.back() << '\n';
    return 0;
}

first 18, last 19
last now 20

Watch: Zara's first test is an empty vector. temps.front() on an empty temps compiled with no message. On the Playground it ended with Runtime error and printed nothing, not even the text before it. back() on an empty vector did the same. So both are undefined on an empty vector, and only an empty() check protects them.

insert at a position

v.insert(pos, x) puts x before the position pos. A position is an iterator, a marker for one place in the vector. For now, write it as v.begin() + i, which means "the place of index i". Module 11 explains iterators properly.

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

int main() {
    vector<int> v{10, 20, 40};
    v.insert(v.begin() + 2, 30);
    v.insert(v.begin(), 5);
    v.insert(v.end(), 50);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5 10 20 30 40 50

To make room at index i, every element from i to the end moves one box to the right. Inserting at v.begin() moves all of them. Inserting at v.end() moves none, and is the same as push_back.

Watch: a position past v.end() is undefined. Nothing checks it. v.insert(v.begin() + 5, 99) on three elements was Success on the Playground and reported size 4, though no index 5 existed. So build positions from indexes you have checked, 0 to size() inclusive.

erase at a position, and erase in a loop

v.erase(pos) removes the element at pos. v.erase(first, last) removes a range, from first up to but not including last. Both return an iterator to the element that now sits where the removed one was.

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

int main() {
    vector<int> v{5, 10, 20, 30, 40, 50};
    v.erase(v.begin());
    v.erase(v.begin() + 1, v.begin() + 3);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 10 40 50

The first call removed 5. The second removed indexes 1 and 2 of what was left, 20 and 30. Everything after a removed element slides left to close the gap.

Now remove every even number from {2, 4, 5, 6}. Bob writes the loop he would write for an array.

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

int main() {
    vector<int> v{2, 4, 5, 6};
    for (size_t i = 0; i < v.size(); i++) {
        if (v[i] % 2 == 0) {
            v.erase(v.begin() + i);
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 4 5

The 4 survived. When 2 was erased at index 0, the 4 slid into index 0, and the loop moved on to index 1. So the element right after each erased one is never tested.

The safe loop uses what erase returns. Erase, and stay where you are; otherwise step forward.

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

int main() {
    vector<int> v{2, 4, 5, 6};
    for (auto it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5

*it reads the element the iterator marks, the way *p reads through a pointer. This loop is correct, but each erase still shifts the rest, so many erasures cost O(n) each. Amara removes everything in one pass with the erase-remove idiom. remove_if from <algorithm> moves the elements to keep to the front and returns where they end. One erase then cuts the tail.

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

bool is_even(int x) {
    return x % 2 == 0;
}

int main() {
    vector<int> v{2, 4, 5, 6, 7, 8};
    v.erase(remove_if(v.begin(), v.end(), is_even), v.end());
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5 7

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

int main() {
    vector<int> v{3, -1, 4, -1, -5, 9, 2};
    auto removed = erase_if(v, [](int x) { return x < 0; });
    cout << "removed " << removed << '\n';
    erase(v, 4);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

removed 3
v: 3 9 2

So erase returns the next position, a loop must use it, and a mass removal is one erase-remove.

clear

v.clear() removes every element. The size becomes 0. The block stays, so the capacity does not change.

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

int main() {
    vector<int> v(1000, 1);
    v.clear();
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    return 0;
}

size 0, capacity 1000

Watch: clear() keeps the memory, which is what you want when you refill the vector in a loop. So a cleared vector is empty, not small.

resize and assign

v.resize(n) makes the size exactly n. Growing adds zeros, or copies of a value you pass. Shrinking cuts from the end. v.assign(n, x) throws away the old elements and puts in n copies of x.

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

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

int main() {
    vector<int> v{1, 2, 3};
    v.resize(5);
    show(v);
    v.resize(7, 9);
    show(v);
    v.resize(2);
    show(v);
    v.assign(4, 8);
    show(v);
    return 0;
}

1 2 3 0 0 (size 5)
1 2 3 0 0 9 9 (size 7)
1 2 (size 2)
8 8 8 8 (size 4)

Watch: resize(7, 9) fills only the new boxes with 9; the old elements keep their values. So resize changes the length, and assign replaces the contents.

reserve and shrink_to_fitIntermediate

v.reserve(n) makes the capacity at least n, so the next pushes up to n never reallocate. It does not change the size. v.shrink_to_fit() asks the vector to give back its spare boxes.

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

int main() {
    vector<int> v;
    v.reserve(100);
    cout << "after reserve: size " << v.size() << ", capacity " << v.capacity() << '\n';
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    cout << "after 10 pushes: size " << v.size() << ", capacity " << v.capacity() << '\n';
    v.shrink_to_fit();
    cout << "after shrink_to_fit: size " << v.size() << ", capacity " << v.capacity() << '\n';
    return 0;
}

after reserve: size 0, capacity 100
after 10 pushes: size 10, capacity 100
after shrink_to_fit: size 10, capacity 10

Watch: reserve makes room, not elements. Kenji wrote v.reserve(5); v[0] = 42;. It ran Success on the Playground, printed size 0, and a range-for over v printed nothing. The 42 went into a spare box that is not an element. Use resize or the v(n) constructor when you want elements. shrink_to_fit is a request; GCC's library honours it, and the standard allows a library to ignore it.

swap

a.swap(b), or swap(a, b), exchanges the contents of two vectors of the same type.

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

int main() {
    vector<int> today{1, 2, 3};
    vector<int> tomorrow(100000, 7);
    today.swap(tomorrow);
    cout << today.size() << ' ' << tomorrow.size() << '\n';
    return 0;
}

100000 3

Watch: swapping 100,000 elements cost the same as swapping 3. So a swap is a trade of handles, not a copy.

begin, end and dataIntermediate

v.begin() marks the first element and v.end() marks the place just after the last one. The algorithms of Part Four take a pair of them. v.data() returns a plain pointer to the first element, for code that wants a C array.

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int main() {
    vector<int> v{40, 10, 30, 20};
    sort(v.begin(), v.end());
    const int* p = v.data();
    printf("%d %d %d %d\n", p[0], p[1], p[2], p[3]);
    printf("end - begin = %d\n", (int)(v.end() - v.begin()));
    return 0;
}

10 20 30 40
end - begin = 4

Watch: v.end() is past the last element, so *v.end() reads a box that is not there. The distance end - begin is the size. So the pair begin(), end() is how every algorithm says "the whole vector".

Every cost in one table, and Kenji's measurement

Here is Kenji's question measured. The program below inserts 100,000 numbers at the front and times the loop with <chrono>, the standard clock. We ran it three times on Compiler Explorer, GCC 12 at the Playground's -O2 -std=c++17, one run each. The other two runs changed only the line in the loop, to v.push_back(i); and to v.insert(v.begin() + v.size() / 2, i);.

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

int main() {
    const int n = 100000;
    auto start = chrono::steady_clock::now();
    vector<int> v;
    for (int i = 0; i < n; i++) {
        v.insert(v.begin(), i);
    }
    auto stop = chrono::steady_clock::now();
    chrono::duration<double, milli> took = stop - start;
    cout << v.size() << " elements in " << took.count() << " ms\n";
    return 0;
}

100000 elements in 308.871 ms

The front insert moved about n² / 2 elements in total, five billion. The middle moved half of that, and its time is half. push_back moved almost none, and was nearly six hundred times faster. So the cost lines are not theory: they are the shape of the measurement.

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

int main() {
    vector<string> history;
    history.push_back("draw circle");
    history.push_back("fill blue");
    history.push_back("draw square");

    for (int undo = 0; undo < 4; undo++) {
        if (history.empty()) {
            cout << "nothing to undo\n";
        } else {
            cout << "undo: " << history.back() << '\n';
            history.pop_back();
        }
    }
    cout << history.size() << " actions left\n";
    return 0;
}

undo: draw square
undo: fill blue
undo: draw circle
nothing to undo
0 actions left

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

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

    vector<int> v;
    int x;
    while (cin >> x) {
        v.push_back(x);
    }
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        cout << v[i] << (i > 0 ? ' ' : '\n');
    }
    return 0;
}

9 7 5 3 1

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

bool too_short(int seconds) {
    return seconds < 60;
}

int main() {
    vector<int> songs{215, 45, 190, 30, 260, 58, 175};
    songs.erase(remove_if(songs.begin(), songs.end(), too_short), songs.end());
    songs.insert(songs.begin(), 30);

    int total = 0;
    cout << "playlist:";
    for (int s : songs) {
        cout << ' ' << s;
        total += s;
    }
    cout << '\n' << songs.size() << " songs, " << total / 60 << " min " << total % 60 << " s\n";
    return 0;
}

playlist: 30 215 190 260 175
5 songs, 14 min 30 s

int last = history.pop_back();

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);
    }
}

vector<int> v;
v.reserve(5);
v[0] = 42;

vector<int> temps;
cout << "first reading: " << temps.front() << '\n';

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

int main() {
    vector<int> v{-1, -2, 3};
    for (size_t i = 0; i < v.size(); i++) {
        if (v[i] < 0) {
            v.erase(v.begin() + i);
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    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> marks(n);
    for (int i = 0; i < n; i++) {
        cin >> marks[i];
    }
    int k, x;
    cin >> k >> x;

    // Insert x so that it becomes the k-th value, counting from 1,
    // then print all n + 1 values on one line.

    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> readings(n);
    for (int i = 0; i < n; i++) {
        cin >> readings[i];
    }

    // Remove every negative reading with erase, without skipping any,
    // then print the rest on one line, or "empty".

    return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> list;
    for (int i = 0; i < n; i++) {
        string command;
        cin >> command;
        // "push": read x and add it at the end.
        // "pop": remove the last value, only if there is one.
        // "print": print the list on one line, or "empty".
    }
    return 0;
}

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

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

    int n, m;
    cin >> n >> m;
    vector<int> items(n);
    for (int& x : items) {
        cin >> x;
    }
    vector<int> places(m);
    for (int& p : places) {
        cin >> p;
    }

    // Keep a second index that says where the next kept value goes,
    // copy each kept value there, then resize the vector once.

    return 0;
}

Next, lesson 03 puts these operations to work in six complete programs, from five lines to a real marks report.