Урок 10. STL: sort, map и set

STL (Standard Template Library — стандартная библиотека шаблонов) — часть стандартной библиотеки C++ с готовыми контейнерами (вектор, множество, словарь) и алгоритмами (сортировка, поиск, подсчёт). vector из пятого урока — тоже часть STL. Умение пользоваться ею экономит часы: на олимпиадах сортировку и словари руками не пишут.

Начало и конец: begin и end

Алгоритмы STL работают не с самим контейнером, а с диапазоном — парой «начало, конец». v.begin() указывает на первый элемент, v.end() — на место после последнего. Такие «указатели в контейнер» называются итераторами. sort(v.begin(), v.end()) значит «отсортировать от начала до конца».

sort

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

void print(const vector<int>& v) {
    for (int x : v) {
        cout << x << " ";
    }
    cout << "\n";
}

int main() {
    vector<int> v = {5, 2, 9, 1, 7};
    sort(v.begin(), v.end());
    print(v);
    sort(v.begin(), v.end(), greater<int>());
    print(v);
    return 0;
}

1 2 5 7 9
9 7 5 2 1

sort из <algorithm> сортирует по возрастанию. Третий аргумент задаёт свой порядок: greater<int>() (из <functional>) — по убыванию. Обычный массив сортируется так же: sort(a, a + n). Строки сортируются по словарю.

Свой порядок: лямбда

Чаще всего порядок задают лямбдой — короткой функцией прямо на месте вызова. Она получает два элемента и отвечает, должен ли первый стоять раньше второго. Пример — ученики по убыванию балла, а при равных баллах — по имени:

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

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> s = {{"Vera", 87}, {"Anna", 92}, {"Boris", 87}, {"Gleb", 70}};
    sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) {
            return a.score > b.score;
        }
        return a.name < b.name;
    });
    for (const Student& st : s) {
        cout << st.name << " " << st.score << "\n";
    }
    return 0;
}

Anna 92
Boris 87
Vera 87
Gleb 70

[](const Student& a, const Student& b) { ... } — лямбда: [] — начало, в скобках — параметры, в фигурных скобках — тело. Больше примеров — в справке Как отсортировать вектор.

sort работает за время порядка n·log n: миллион чисел сортируется за доли секунды.

Другие алгоритмы

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

int main() {
    vector<int> v = {4, 1, 4, 3, 1, 4};
    cout << *max_element(v.begin(), v.end()) << "\n";
    cout << *min_element(v.begin(), v.end()) << "\n";
    cout << count(v.begin(), v.end(), 4) << "\n";
    cout << accumulate(v.begin(), v.end(), 0LL) << "\n";
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int x : v) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}

4
1
3
17
1 3 4

max_element возвращает не значение, а итератор на элемент, поэтому перед ним *. unique не удаляет повторы, а сдвигает их в конец и возвращает новый «конец»; удаляет их erase.

set — множество

set хранит разные значения и всегда держит их по возрастанию. Повторное добавление ничего не меняет.

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

int main() {
    int n;
    cin >> n;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << "\n";
    for (int x : s) {
        cout << x << " ";
    }
    cout << "\n";
    cout << s.count(5) << " " << s.count(6) << "\n";
    s.erase(5);
    cout << s.size() << "\n";
    return 0;
}

7
5 3 5 1 3 9 5

4
1 3 5 9
1 0
3

• s.insert(x) — добавить, s.erase(x) — удалить;
• s.count(x) — 1, если x есть, и 0, если нет;
• s.size() — сколько разных значений.

Добавление, удаление и поиск занимают порядка log n шагов — быстро даже для миллиона элементов. Если повторы нужно хранить, есть multiset.

map — словарь

map хранит пары «ключ — значение»: каждому ключу соответствует одно значение. Ключи, как и в set, разные и упорядочены. Классическая задача — посчитать, сколько раз встречается каждое слово:

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

int main() {
    map<string, int> freq;
    string word;
    while (cin >> word) {
        freq[word]++;
    }
    for (const auto& [w, c] : freq) {
        cout << w << " " << c << "\n";
    }
    return 0;
}

the cat and the dog and the bird

and 2
bird 1
cat 1
dog 1
the 3

• freq[word] — значение по ключу. Если ключа ещё нет, он создаётся со значением по умолчанию (для int — 0), поэтому freq[word]++ сразу работает.
• while (cin >> word) читает слова, пока ввод не кончится.
• for (const auto& [w, c] : freq) — обход в порядке ключей; w — ключ, c — значение. Такая запись появилась в C++17; в более старом коде пишут p.first и p.second.

pair

pair — пара значений: .first и .second. Её удобно класть в векторы и множества. Пары сравниваются сначала по first, потом по second, поэтому вектор пар сортируется «по первому, а при равенстве по второму» без своей функции сравнения:

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

int main() {
    vector<pair<int, int>> p = {{2, 5}, {1, 9}, {2, 1}};
    sort(p.begin(), p.end());
    for (const auto& [a, b] : p) {
        cout << a << " " << b << "\n";
    }
    return 0;
}

1 9
2 1
2 5

unordered_map и unordered_set

У map и set есть «неупорядоченные» родственники — unordered_map и unordered_set. В среднем они быстрее, но элементы в них лежат в непредсказуемом порядке. Если порядок не нужен и данных много, они дают выигрыш; если нужен вывод по порядку — берите map и set.

Коротко

• Алгоритмы STL работают с диапазоном begin()–end().
• sort(v.begin(), v.end()) — по возрастанию; свой порядок — третьим аргументом, сравнение строго < или >.
• max_element, count, accumulate, unique + erase — готовые решения частых задач.
• set — разные значения по возрастанию; insert, count, erase.
• map — ключ и значение; m[key] создаёт ключ, если его не было; count — проверить без создания.
• pair сравнивается по first, потом по second.

Проверьте себя