C/C++ | Вопросы собесов

🤔 Как std::set и std::map устроены под капотом?



Под капотом std::set и std::map реализованы как сбалансированные деревья поиска, обычно красно-черные деревья. Это обеспечивает логарифмическую сложность для операций вставки, удаления и поиска. Каждой ноде в дереве соответствует ключ для std::set и пара ключ-значение для std::map.



🚩`std::set`



Это контейнер, который хранит уникальные элементы в отсортированном порядке. Под капотом std::set обычно реализован как красно-черное дерево.



🚩Красно-черное дерево



Это тип самобалансирующегося бинарного дерева поиска, который гарантирует, что дерево остается сбалансированным после каждой операции вставки или удаления. Это обеспечивает время выполнения операций O(log n) для вставки, удаления и поиска.



🚩Свойства красно-черного дерева



Каждый узел либо красный, либо черный.

Корень дерева всегда черный.

Листья (NULL-узлы) считаются черными.

Красный узел не может иметь красных дочерних узлов (два красных узла подряд недопустимы).

Любой путь от корня до листа содержит одинаковое количество черных узлов.



Пример внутренней структуры std::set

#include <set>

#include <iostream>



int main() {

    std::set<int> mySet;

    mySet.insert(10);

    mySet.insert(20);

    mySet.insert(15);



    for (const auto& elem : mySet) {

        std::cout << elem << " ";

    }



    return 0;

}

🚩`std::map`



Это ассоциативный контейнер, который хранит пары "ключ-значение" в отсортированном порядке ключей. Как и std::set, std::map также обычно реализован как красно-черное дерево.



🚩Особенности `std::map`



🟠Пары "ключ-значение"

Каждый узел в дереве хранит пару "ключ-значение", где ключ используется для поддержания порядка узлов.

🟠Уникальные ключи

Ключи в std::map уникальны, и каждая операция вставки проверяет, существует ли уже ключ в дереве.



Пример внутренней структуры std::map

#include <map>

#include <iostream>



int main() {

    std::map<int, std::string> myMap;

    myMap.insert({1, "one"});

    myMap.insert({2, "two"});

    myMap.insert({3, "three"});



    for (const auto& pair : myMap) {

        std::cout << pair.first << ": " << pair.second << std::endl;

    }



    return 0;

}

Ставь 👍 и забирай 📚 Базу знаний