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 scan of 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. 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 very slowly: doubling the size adds one or two comparisons. std::set remembers which values have already appeared, and std::map stores data by key, counters for example.

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: a hash for them is already defined.

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 standard does not define the traversal order of a std::unordered_map: it depends on the implementation and may change after new insertions. When you need the keys in order, use std::map: its loop prints apple kiwi pear. Only the type and the header change, and the rest of the code stays the same.