Как выбрать контейнер

Узнать, есть ли число в векторе, можно только перебором: цикл сравнивает с этим числом каждый элемент. std::set отвечает на тот же вопрос одним вызовом 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
}

Для трёх чисел разницы не видно. Но цикл по миллиону элементов делает до миллиона сравнений, а std::set находит ключ среди миллиона за несколько десятков. Контейнер выбирают по тому, что программа делает с данными чаще всего.

Вектор по умолчанию

Начинайте с std::vector. Он хранит элементы подряд, в порядке добавления, допускает повторы и даёт доступ по индексу. Добавление в конец и обход у него быстрые. Медленно только искать значение: время поиска растёт вместе с размером.

Если ключи — числа подряд от 0, вектор заменяет и std::map: индекс работает как ключ. Например, счётчики оценок от 0 до 5 помещаются в std::vector<int> из шести элементов.

Ключи и поиск

std::map и std::set подходят, когда ключи уникальны и нужен их порядок. std::set помнит, какие значения уже встречались, а std::map хранит данные по ключу, например счётчики. Чтобы держать вектор упорядоченным, каждое новое значение пришлось бы вставлять в нужное место, сдвигая остальные. std::map и std::set сохраняют порядок сами при каждой вставке.

Время поиска в них растёт медленно: когда размер удваивается, прибавляется одно-два сравнения.

Если порядок ключей не нужен, а искать приходится часто, берите std::unordered_map. В среднем он находит ключ примерно за одно и то же время при любом размере. Ключом может быть число или std::string: стандартная библиотека уже умеет вычислять для них место в таблице.

Частая ошибка

Ключи std::unordered_map выводят, ожидая порядка по алфавиту:

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

Порядок обхода std::unordered_map зависит от реализации: стандарт его не задаёт, и после новых вставок порядок может измениться. Если ключи нужны по порядку, возьмите std::map: его цикл выведет apple kiwi pear. Меняется только тип, а строка #include <unordered_map> становится #include <map>. Остальной код останется прежним.

Главное

• По умолчанию берите std::vector: он хранит элементы подряд и быстро добавляет в конец, но ищет значение перебором.
• std::set и std::map держат ключи по порядку, и поиск в них почти не замедляется с ростом размера.
• std::unordered_map в среднем ищет быстрее всех, но порядок его ключей не задан.