How is the map container in C++ structured?

std::map is an associative container that stores elements consisting of a key-value pair, sorted by key.

Main characteristics:

• Elements are stored in sorted order by key.
• Keys are unique. Each key can only appear once.
• Access, insertion, and deletion times are on average logarithmic: $O(\log n)$, where $n$ is the number of elements.
• Usually implemented based on a self-balancing binary search tree, most often a red-black tree.

Internal structure (red-black tree):

Each node of the tree stores:

1. A key-value pair (std::pair<const Key, T>). The key is constant to prevent modification and maintain order.
2. Pointers to the left and right children.
3. A pointer to the parent.
4. The color of the node (red or black).

Properties of the red-black tree, maintained during insertion and deletion operations through rotations and recoloring, ensure the tree's height is logarithmic, and consequently, the operations have logarithmic complexity.

Operations:

• operator[]: Access by key. If the key is not found, inserts a new element with the key and a default value.
• at(): Access by key. Throws std::out_of_range exception if the key is not found.
• insert(): Inserts a new key-value pair. Ignores insertion if the key already exists.
• erase(): Removes an element by key or iterator.
• find(): Searches for an element by key and returns an iterator to it or end() if not found.

Example usage:

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<int, std::string> my_map;

    // Inserting elements
    my_map[1] = "one";
    my_map[3] = "three";
    my_map.insert({2, "two"}); // Another way to insert

    // Accessing elements
    std::cout << "Value for key 1: " << my_map[1] << std::endl;

    // Iterating over elements (will be in key order)
    for (const auto& pair : my_map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Searching for an element
    auto it = my_map.find(2);
    if (it != my_map.end()) {
        std::cout << "Found element with key 2: " << it->second << std::endl;
    }

    // Removing an element
    my_map.erase(1);

    return 0;
}

Difference from std::unordered_map:

Feature	std::map	std::unordered_map
Ordering	Sorted by key	Unordered
Implementation	Red-black tree	Hash table
Average complexity	$O(\log n)$	$O(1)$
Worst-case complexity	$O(\log n)$	$O(n)$
Key requirements	Less-than comparison	Hash function & equality