How are std::set and std::map implemented at a low…

In C++, std::set and std::map are usually implemented using balanced binary search trees, most often red-black trees.

Red-Black Tree:

A self-balancing binary search tree that maintains the order of elements and provides logarithmic complexity for most operations (insertion, deletion, search).

Main properties of red-black trees:

Each node has a color: red or black.
The root of the tree is always black.
Leaves (null nodes) are always black.
A red node cannot have a red child.
All simple paths from any node to the leaves in its subtree contain the same number of black nodes.

How this applies to std::set and std::map:

std::set: Stores unique elements in sorted order. Each node contains the element itself. Element comparison is used to determine the order in the tree.

// Conceptual example of a node in std::set
template <typename Key>
struct SetNode {
    Key key;
    SetNode* left;
    SetNode* right;
    SetNode* parent;
    Color color; // Red or black
};

std::map: Stores key-value pairs. Elements are sorted by key. Each node contains a pair of key and value. Comparison is done by key.

// Conceptual example of a node in std::map
template <typename Key, typename Value>
struct MapNode {
    std::pair<const Key, Value> value; // value.first - key, value.second - value
    MapNode* left;
    MapNode* right;
    MapNode* parent;
    Color color; // Red or black
};

Operations and their complexity:

Thanks to the properties of red-black trees, the main operations have the following time complexity:

Operation	Complexity
`insert`	O(log n)
`erase`	O(log n)
`find`	O(log n)
`lower_bound`	O(log n)
`upper_bound`	O(log n)
Iteration over elements	O(n)

n is the number of elements in the container.

Insertion and deletion in red-black trees involve recoloring nodes and tree rotations to maintain balance. This guarantees that the tree's depth remains logarithmic, which is important for performance. Iterators of std::set and std::map are usually implemented as tree iterators, allowing traversal of elements in sorted order (in-order traversal).

How are std::set and std::map implemented at a low level in C++?