#story

Сделай свой std::flat_set из C++23 📦

В C++23 были приняты новые контейнеры std::flat_set, std::flat_map (и их multi-варианты), аналогично уже существующим std::set и std::map.

В интернете почти нет нормальных объяснений их содержимого. Многие из тех, что есть, скорее запутывают. Там приводятся всякие ненужные размышления на тему локальности памяти, бенчмарки, итераторы, и так далее.
А на деле реализация этих контейнеров простая, ее может сделать каждый. Из готовой реализации можно уже самому понять свойства этого класса.

API flat_set почти не отличается от set. Добавлены новые конструкторы и перегрузки insert. Заменены редкие методы:
node_type extract(...)
insert_return_type insert(node_type&& nh);
то есть те, где юзер должен был работать с вершинами красно-черного дерева.
Можно просто заменить тип на новый и почти наверняка это скомпилируется.

Новые контейнеры являются адаптерами. Это такие контейнеры, которые сами не делают ничего "тяжелого", а только держат у себя другой контейнер и все методы пробрасывают туда. В C++ уже было три таких контейнера - stack, queue, priority_queue:

    template<class T, class Container = std::deque<T>> class stack;
    template<class T, class Container = std::deque<T>> class queue;

flat_set (и ему подобные) такой же адаптер:

    template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>> class flat_set;

То есть множество представляется (по умолчанию) в виде отсортированного вектора (но можно дать и другой класс - static_vector, small_vector).

Пусть у нас есть std::vector<T> data. Попробуем реализовать для него все основные методы flat_set сами, в упрощенном виде (без кастомных компараторов и прочего) 😝

0️⃣Итераторы begin/end/..., методы empty()/size()/max_size()
Подобные методы не рассматриваем, они просто перенаправляют вызовы в сам контейнер

decltype(auto) begin() noexcept { return data.begin(); }

1️⃣ Конструктор flat_set(container_type cont);
Конструкторов там примерно 24 штуки на разные случаи жизни. Можно реализовать случай, когда дается контейнер, который изначально не отсортирован и там могут быть повторяющиеся элементы - с использованием std::unique:

    data = std::move(cont);
    std::sort(data.begin(), data.end());
    auto last = std::unique(data.begin(), data.end());
    data.erase(last, data.end());

Сложность этого метода O(NlogN)

2️⃣ Вставка insert(const value_type& x)
Нужно найти место, куда вставить новый элемент. Если он уже существует, то вставлять не нужно. Это можно делать бинарным поиском через std::lower_bound и вставкой в вектор в этом место.

    auto lower = std::lower_bound(data.begin(), data.end(), x);
    if (lower == data.end() || *lower != x) {
        data.insert(lower, x);
    }

Сложность этого метода O(N) в общем случае и амортизированный O(logN) в случае вставки в конец. "Амортизированный" - потому что можно попасть на реаллокацию вектора 😁

3️⃣ Удаление erase(const key_type& x) и прочие методы (find, contains, ...)
Действуют по одинаковому принципу с insert - найти место этого элемента бинарным поиском и что-то с этим сделать.

    auto lower = std::lower_bound(data.begin(), data.end(), x);
    if (lower != data.end() && *lower == x) {
        data.erase(lower);
    }

Сложность этого метода O(N) в общем случае и O(logN) в случае удаления с конца.

4️⃣ Слияние двух flat_set
В некоторых случаях надо делать слияние двух отсортированных векторов. Это стандартный алгоритм, его часто спрашивают на собеседованиях.

Если нужно вставить несколько элементов, то можно вызвать такой метод, который вставит каждый элемент по отдельности за O(N), с итоговой сложностью до O(N^2) в среднем:

    void insert(InputIterator first, InputIterator last);

Но если есть знание, что вставляемые элементы [first, last) уже отсортированы, то можно вызвать другой метод с "мусорным" объектом в начале, который сделает слияние, это будет работать за O(N), что может быть быстрее:

    void insert(sorted_unique_t, InputIterator first, InputIterator last);

Такую задачу можно решить на Leetcode - Merge Sorted Array 🙂