When to Use vector and When Not To

Maria keeps a leaderboard sorted at all times. Every new score goes into the middle of a vector, at its place, so the list never needs sorting. It works, and with 200,000 scores it takes more than a second. Nothing is wrong with her code. She picked the wrong container. This lesson gives you the questions that would have told her which one to pick.

Four questions about your data

A container is a promise about which operations are cheap. So you choose one by asking what your program does most. Four questions decide almost every case.

Maria's answers: a sequence, yes, but she searches it by value and inserts in the middle. Two of four point away from vector, towards a sorted container. So the questions name a container before you write any code.

The comparison chart

The chart puts vector beside the four containers it is most often confused with. The costs come from each container's page on cppreference. The memory row was measured: on GCC 12, a million ints, counting every byte each container asked for, one run on Compiler Explorer.

Read the vector column top to bottom: cheap at the end, cheap by index, cheapest in memory. Its weak rows are the front, the middle and search. Every other column wins one of those and loses something else. A list stores two pointers beside every int, so it needs six times the memory. A set keeps its values in order and finds one in O(log n), at ten times the memory, and with no index at all.

The last row matters as much as the costs. An iterator, a pointer or a reference to a vector element is valid only until the vector reallocates. After that it points into the freed old block. Even without a reallocation, an insert or erase in the middle shifts the elements after it, so their iterators go stale too. A list or a set never moves an element once it is stored. So a vector is the right choice when nobody holds on to its elements across a growth.

The decision flowchart

The same four ideas as a flowchart, in the order to ask them. Start at the top and follow your answers. Every exit names a container and the module that teaches it.

Maria's walk: question 1, she looks up scores by value to find their place, so yes. The arrow says set, or multiset when two players may tie, Module 8. So the flowchart sends her away from vector at the very first box.

Here is what the switch is worth, measured. The program inserts the same 200,000 pseudo-random numbers into a sorted vector, each at its place, and into a multiset. lower_bound finds the place in a sorted range; Module 13 teaches it, and here it only finds where to insert.

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

int main() {
    const int n = 200000;
    vector<int> input(n);
    unsigned x = 12345;
    for (int& v : input) {
        x = x * 1103515245u + 12345u;
        v = (int)(x >> 1);
    }

    auto t0 = chrono::steady_clock::now();
    vector<int> sorted_v;
    for (int v : input) {
        sorted_v.insert(lower_bound(sorted_v.begin(), sorted_v.end(), v), v);
    }
    auto t1 = chrono::steady_clock::now();
    multiset<int> s;
    for (int v : input) {
        s.insert(v);
    }
    auto t2 = chrono::steady_clock::now();

    chrono::duration<double, milli> a = t1 - t0, b = t2 - t1;
    cout << "sorted vector: " << a.count() << " ms\n";
    cout << "multiset:      " << b.count() << " ms\n";
    cout << (equal(sorted_v.begin(), sorted_v.end(), s.begin()) ? "same order\n" : "different\n");
    return 0;
}

sorted vector: 1217.13 ms
multiset:      44.6139 ms
same order

One run on Compiler Explorer, GCC 12 at -O2 -std=c++17. Both hold the same numbers in the same order. Finding the place is fast in both; the vector's cost is shifting on average half its elements on every insert. So the right container was about 27 times faster here, with simpler code.

The honest default: vector, then measure

The chart can make a list look attractive: O(1) inserts anywhere. But a list puts each element in its own small block, wherever the allocator finds room. Walking it means jumping from block to block. A vector's elements sit side by side, and the processor reads memory in chunks, so the next element is usually already there.

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

int main() {
    const int n = 1000000;
    vector<int> v;
    list<int> l;
    for (int i = 0; i < n; i++) {
        v.push_back(i % 100);
        l.push_back(i % 100);
    }

    auto t0 = chrono::steady_clock::now();
    long long sv = 0;
    for (int x : v) sv += x;
    auto t1 = chrono::steady_clock::now();
    long long sl = 0;
    for (int x : l) sl += x;
    auto t2 = chrono::steady_clock::now();

    chrono::duration<double, milli> dv = t1 - t0, dl = t2 - t1;
    cout << "vector: sum " << sv << " in " << dv.count() << " ms\n";
    cout << "list:   sum " << sl << " in " << dl.count() << " ms\n";
    return 0;
}

vector: sum 49500000 in 0.736809 ms
list:   sum 49500000 in 4.59888 ms

Same million numbers, same loop, one run on Compiler Explorer at the Playground's flags: the list was about six times slower to walk. Module 17 measures this effect, the cache, properly. The C++ Core Guidelines give the rule this track follows. Use a vector by default, and switch only for a reason you can name or measure.

Big elements: keep them still, move indexes

Question 4 is about size. Moving an int copies 4 bytes. Moving a record with a long description copies all of it. If big records must be reordered or edited often, keep them in one vector that never changes, and move small int indexes in a second vector.

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

int main() {
    vector<string> books{
        "The C Programming Language, a long description...",
        "Structure and Interpretation of Computer Programs, a long description...",
        "Introduction to Algorithms, a long description...",
    };

    vector<int> reading_list{2, 0};
    reading_list.insert(reading_list.begin(), 1);

    for (int id : reading_list) {
        cout << id << ": " << books[id].substr(0, 20) << '\n';
    }
    return 0;
}

1: Structure and Interp
2: Introduction to Algo
0: The C Programming La

The insert at the front moved two ints, not two long strings. The books stay where they are, so an index into books never goes stale. So big data stays put, and its order lives in a vector of indexes.

Passing a vector to a function

How you pass a vector says what the function may do with it. There are three choices, and each one is a promise.

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

int highest(const vector<int>& marks) {
    int best = marks[0];
    for (int m : marks) {
        if (m > best) {
            best = m;
        }
    }
    return best;
}

void add_bonus(vector<int>& marks, int bonus) {
    for (int& m : marks) {
        m += bonus;
    }
}

vector<int> passed(const vector<int>& marks) {
    vector<int> result;
    for (int m : marks) {
        if (m >= 50) {
            result.push_back(m);
        }
    }
    return result;
}

int main() {
    vector<int> marks{70, 45, 62, 38};
    add_bonus(marks, 5);
    cout << "highest " << highest(marks) << '\n';
    cout << "passed:";
    for (int m : passed(marks)) {
        cout << ' ' << m;
    }
    cout << '\n';
    return 0;
}

highest 75
passed: 75 50 67

Returning a vector by value, as passed does, is cheap: the compiler moves the result out instead of copying it, which lesson 05 explains. So take by const& to read, by & to change, and return a new vector by value.

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

int total(span<const int> values) {
    int sum = 0;
    for (int x : values) {
        sum += x;
    }
    return sum;
}

int main() {
    vector<int> v{3, 1, 4, 1, 5};
    int a[3] = {9, 2, 6};
    cout << total(v) << ' ' << total(a) << '\n';
    cout << total(span<const int>(v).subspan(1, 3)) << '\n';
    return 0;
}

14 17
6

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

int main() {
    multiset<int> board;
    int scores[] = {310, 120, 455, 120, 280};
    for (int s : scores) {
        board.insert(s);
    }
    cout << "board:";
    for (int s : board) {
        cout << ' ' << s;
    }
    cout << "\nlowest " << *board.begin() << ", highest " << *board.rbegin() << '\n';
    return 0;
}

board: 120 120 280 310 455
lowest 120, highest 455

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

int main() {
    deque<string> line{"Bob", "Zara"};
    line.push_back("Kenji");
    while (!line.empty()) {
        cout << "serving " << line.front() << ", " << line.size() - 1 << " waiting\n";
        line.pop_front();
    }
    return 0;
}

serving Bob, 2 waiting
serving Zara, 1 waiting
serving Kenji, 0 waiting

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

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

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

    int coldest = temps[0];
    long long total = 0;
    for (int x : temps) {
        if (x < coldest) {
            coldest = x;
        }
        total += x;
    }
    cout << temps.size() << " readings, coldest " << coldest
         << ", average " << (double)total / temps.size() << '\n';
    return 0;
}

6 readings, coldest -3, average 2.5

void add_bonus(vector<int> marks) {
    for (int& m : marks) {
        m += 5;
    }
}

vector<int> marks{70, 85, 62};
int* first = &marks[0];
marks.push_back(91);
cout << "first mark: " << *first << '\n';

list<int> scores{70, 85, 62};
cout << scores[1] << '\n';

const vector<int>& make_marks() {
    vector<int> marks{70, 85, 62};
    return marks;
}

#include <vector>
using namespace std;

int main() {
    vector<bool> handed_in(100000);
    bool& first = handed_in[0];
    first = true;
    return 0;
}

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

// Return how many elements of v are greater than limit.
// The const& promises not to change v, and avoids a copy per call.
int count_above(const vector<int>& v, int limit) {
    return 0;
}

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

    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) {
        cin >> x;
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int limit;
        cin >> limit;
        cout << count_above(v, limit) << '\n';
    }
    return 0;
}

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

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string read, size, change;
        cin >> read >> size >> change;
        // Ask the flowchart's questions in its order, and print one word.
    }
    return 0;
}

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

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

    vector<int> sorted_v;
    vector<int> landed;
    int x;
    while (cin >> x) {
        // lower_bound(sorted_v.begin(), sorted_v.end(), x) is the first place
        // whose value is not less than x. Its distance from begin() is the index.
        // Insert x there, and remember the index.
    }
    // Print the indexes on one line, then the sorted list on the next.
    return 0;
}

Next, the Pro lesson 05 opens the vector up: how the capacity grows on our compiler, and what a reallocation breaks.