Choosing a container

To find out whether a vector holds a number, a loop must compare every element with it. std::set answers the same question with one call to contains:

#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> v{7, 3, 9};
    bool in_vector = false;
    for (int x : v) {
        if (x == 9) {
            in_vector = true;
        }
    }
    std::set<int> s{7, 3, 9};
    std::cout << in_vector << ' ' << s.contains(9) << '\n';  // 1 1
}

For three numbers the difference is invisible. But a loop over a million elements takes up to a million comparisons. std::set finds a key among a million in a few dozen comparisons. A container is chosen by what the program does with its data most often.

Vector by default

Start with std::vector. It stores elements next to each other, in the order they were added, allows repeats and gives access by index. Adding at the end and traversal are fast. Only searching for a value is slow: the search time grows with the size.

When the keys are consecutive numbers from 0, a vector replaces a std::map too: the index works as the key. For example, counters for grades from 0 to 5 fit into a std::vector<int> of six elements.

Keys and lookups

std::map and std::set fit when keys are unique and their order matters. std::set remembers which values have already appeared, and std::map stores data by key, counters for example. To keep a vector sorted, each new value would have to be inserted in its place, shifting the rest. std::map and std::set keep the order themselves on every insertion.

Their search time grows slowly: when the size doubles, one or two comparisons are added.

When the order of keys does not matter but lookups are frequent, use std::unordered_map. On average, it finds a key in about the same time whatever the container's size. A key can be a number or a std::string: the standard library already knows how to compute their place in the table.

Common mistake

The keys of a std::unordered_map are printed in the hope of alphabetical order:

std::unordered_map<std::string, int> stock{  // ✗
    {"pear", 2}, {"apple", 7}, {"kiwi", 5}};
for (const auto& item : stock) {
    std::cout << item.first << ' ';
}

The traversal order of a std::unordered_map depends on the implementation: the standard does not define it, and the order may change after new insertions. When you need the keys in order, use std::map: its loop prints apple kiwi pear. Only the type changes, and the line #include <unordered_map> becomes #include <map>. The rest of the code stays the same.

Key points

• Use std::vector by default: it stores elements next to each other and adds at the end fast, but searches for a value by scanning.
• std::set and std::map keep keys in order, and lookup in them barely slows down as they grow.
• std::unordered_map is the fastest at lookup on average, but the order of its keys is not defined.