C++ set: уникальные отсортированные элементы с std::set

Набор уникальных отсортированных значений

Вы уже видели, как unordered_map хранит пары «ключ-значение» с быстрым поиском на основе хеша. std::set — более простой родственник: он хранит только значения (без связанных данных) и автоматически следит за двумя правилами. Каждый элемент уникален (дубликаты молча отбрасываются), и элементы всегда хранятся в отсортированном порядке.

Это делает set естественным выбором для вопросов вроде «видел ли я это раньше?» или «дай мне различные элементы по порядку». Вы вставляете, не беспокоясь о дубликатах, и обходите без предварительной сортировки.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // дубликат - игнорируется

    for (int x : s) cout << x << " ";   // 10 30 40 (отсортировано, без повторов)
}

Обратите внимание: мы вставили 10 дважды и не по порядку, но вывод всё равно отсортирован, и 10 появляется один раз. set сам выполнил всю учётную работу за вас.

Вставка и удаление

insert добавляет значение, если его ещё нет. Он возвращает pair, у которой .second — это bool, сообщающий, действительно ли произошла вставка. Это удобно, когда нужно узнать, было ли значение новым:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Чтобы удалить значение, вызовите erase с самим значением — он возвращает количество удалённых элементов (0 или 1 для set). Удаление того, чего нет, безвредно, это не ошибка:

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // удаляет 3
    s.erase(99);         // ничего не делает, возвращает 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Проверка наличия

Главное предназначение set — быстрые проверки «есть ли это здесь?». Самый понятный способ — count, который возвращает 1 или 0:

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Начиная с C++20 есть ещё более читаемый вариант — contains, который возвращает bool напрямую:

if (primes.contains(7)) { /* ... */ }   // C++20

Распространённая ошибка — тянуться к operator[], как сделали бы с map. У set нет operator[]: здесь нечего получать, можно лишь проверить наличие. Используйте count или contains, а не s[7].

Если нужна сама позиция (чтобы удалить элемент или посмотреть соседей), используйте find, который возвращает итератор или end():

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

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // удаление по итератору - без повторного поиска
    }
    cout << "size now " << s.size() << "\n";
}

Упорядоченный обход и запросы по диапазону

Поскольку set отсортирован, обход всегда выдаёт элементы от меньшего к большему, а приёмы упорядоченных контейнеров достаются вам бесплатно. lower_bound(x) даёт первый элемент, не меньший x, а upper_bound(x) — первый элемент, строго больший x; вместе они позволяют просмотреть числовой диапазон, не проверяя каждый элемент:

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // вывести всё в диапазоне [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Тонкое, но важное правило: элементы set неизменяемы. Итератор отдаёт вам const-ссылку, поэтому изменить элемент на месте нельзя — это может нарушить порядок сортировки, на который опирается контейнер. Чтобы «изменить» значение, удалите старое и вставьте новое.

По умолчанию порядок возрастающий (std::less). Для убывающего порядка укажите другой компаратор в качестве второго аргумента шаблона:

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set — один из трёх близких родственников, и правильный выбор имеет значение:

set<int>            // уникальные значения, отсортированы, O(log n)
multiset<int>       // допускает дубликаты, отсортированы, O(log n)
unordered_set<int>  // уникальные значения, БЕЗ порядка, в среднем O(1)

Берите unordered_set, когда нужны только проверки наличия и порядок неважен — его поиск на основе хеша в среднем быстрее, чем древовидное O(log n) у set. Выбирайте set, когда нужны элементы в отсортированном порядке, запросы по диапазону с lower_bound/upper_bound или стабильное поведение итераторов. Используйте multiset только когда дубликаты значимы (например, гистограмма повторяющихся значений): в multiset count(x) может вернуть больше 1, а erase(x) удаляет все копии, если только вы не удаляете по одному итератору.

Классическое применение set: убрать дубликаты и отсортировать vector за один приём.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Создание set из итераторов вектора отбрасывает каждый дубликат и сортирует остальное — без ручного цикла, без танца с std::sort и std::unique.

Далее: pair и tuple

Теперь вы видели, как .first и .second появляются у pair, которую возвращает insert, и как структурированные привязки (auto [it, inserted]) аккуратно её распаковывают. Эти лёгкие типы для «связывания нескольких значений вместе» встречаются в STL повсюду. Дальше мы подробно рассмотрим pair и tuple: как их создавать, распаковывать и возвращать несколько значений из функции, не определяя целую структуру.