STL: контейнеры и алгоритмы

В этом уроке ты узнаешь

Выбирать подходящий контейнер STL для задачи
Хранить и подсчитывать пары «ключ — значение» с помощью std::map
Создавать набор уникальных элементов с помощью std::set
Сортировать, искать и считать с помощью итераторов и функций из <algorithm>

На олимпиаде нужно отсортировать миллион чисел. Написать и отладить сортировку с нуля — это час работы. Программист на C++ пишет всего одну строку: std::sort(v.begin(), v.end());. Это волшебство даёт STL (Standard Template Library — стандартная библиотека шаблонов): набор готовых, проверенных и очень быстрых структур данных и алгоритмов.

Три части STL

Контейнеры хранят данные: std::vector, std::map, std::set и другие.
Итераторы указывают на позицию в контейнере: v.begin() — на первый элемент, а v.end() — на место после последнего.
Алгоритмы (из <algorithm>) работают с диапазоном, заданным итераторами: сортируют, ищут, считают, преобразуют.

Контейнер	Что хранит	Скорость поиска
`std::vector<T>`	элементы по порядку, по индексу	поиск по значению: O(n)
`std::map<K, V>`	пары «ключ — значение», отсортированные по ключу	O(log n)
`std::set<T>`	отсортированные уникальные элементы	O(log n)
`std::unordered_map<K, V>`	неупорядоченные пары «ключ — значение» (хеш-таблица)	в среднем O(1)

Самые используемые контейнеры

std::map: ключи и значения

std::map (из <map>) похож на словарь: каждому ключу соответствует одно значение, и ключи не повторяются. Элементы всегда хранятся отсортированными по ключу. Ниже мы подсчитываем голоса классного опроса: count[v] создаёт ключ со значением 0, если его нет, а ++ увеличивает значение.

C++

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> votes = {"tea", "coffee", "tea", "juice", "tea", "coffee"};
    std::map<std::string, int> count;
    for (const std::string& v : votes) {
        count[v]++;
    }
    for (const auto& entry : count) {
        std::cout << entry.first << ": " << entry.second << '\n';
    }
    std::cout << "Kinds: " << count.size() << '\n';

    if (count.find("milk") == count.end()) {
        std::cout << "Nobody chose milk\n";
    }
    return 0;
}

Ожидаемый результат

coffee: 2
juice: 1
tea: 3
Kinds: 3
Nobody chose milk

Ключи вывелись в алфавитном порядке. Каждый элемент — это pair: first — ключ, second — значение.

std::set: уникальные элементы

std::set (из <set>) хранит каждое значение только один раз и автоматически сортирует элементы. Если через insert добавить уже существующее значение, ничего не изменится. Это идеально, чтобы убирать повторы и быстро отвечать на вопрос «было ли такое значение?».

C++

#include <iostream>
#include <set>

int main() {
    std::set<int> numbers = {5, 1, 4, 1, 5, 9, 2, 6, 5};
    numbers.insert(3);
    numbers.insert(4);
    std::cout << "Size: " << numbers.size() << '\n';
    for (int n : numbers) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    std::cout << std::boolalpha << (numbers.count(7) > 0) << '\n';
    return 0;
}

Ожидаемый результат

Size: 7
1 2 3 4 5 6 9 
false

Из девяти чисел уникальны шесть; 3 добавилось, а 4 уже было.

Алгоритмы

В <algorithm> десятки готовых функций, и все они работают одинаково: принимают начало и конец диапазона в виде итераторов. std::find возвращает итератор на найденный элемент, а если ничего не нашёл — end(). Для суммирования есть std::accumulate из <numeric>.

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v = {42, 7, 19, 73, 7, 50};

    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';

    auto it = std::find(v.begin(), v.end(), 19);
    if (it != v.end()) {
        std::cout << "19 found at index " << (it - v.begin()) << '\n';
    }
    std::cout << "Sevens: " << std::count(v.begin(), v.end(), 7) << '\n';
    std::cout << "Max: " << *std::max_element(v.begin(), v.end()) << '\n';
    std::cout << "Sum: " << std::accumulate(v.begin(), v.end(), 0) << '\n';
    return 0;
}

Ожидаемый результат

7 7 19 42 50 73 
19 found at index 2
Sevens: 2
Max: 73
Sum: 198

Алгоритм	Что делает
`std::sort(b, e)`	сортирует по возрастанию
`std::reverse(b, e)`	переворачивает порядок
`std::find(b, e, x)`	возвращает итератор на `x` или `e`
`std::count(b, e, x)`	считает, сколько раз встречается `x`
`std::max_element(b, e)`	итератор на наибольший элемент
`std::binary_search(b, e, x)`	быстрый поиск в отсортированном диапазоне, `true`/`false`

Интерактив

Загрузка симуляции…

Простые алгоритмы сортировки делают порядка n² шагов. std::sort обходится порядка n · log n сравнений — для миллиона элементов это в тысячи раз меньше.

Главное

STL = контейнеры + итераторы + алгоритмы.
std::map хранит пары «ключ — значение», отсортированные по ключу; m[k] создаёт отсутствующий ключ со значением 0.
std::set хранит каждое значение один раз и в отсортированном виде.
v.end() — место после последнего элемента; std::find возвращает его, если ничего не нашёл.
Готовые алгоритмы вроде std::sort, std::count и std::max_element короче и надёжнее самописных циклов.

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

1 / 10

Какой контейнер хранит элементы уникальными и отсортированными?