源码版本：SGI-STL V3.3

set / map

• 底层都为 RB-tree（平衡二叉搜索树），每一个元素都是红黑树上的一个节点，所有元素都会根据键值自动被排序（默认递增）。
• map 的元素是 pair，同时拥有键值 key 和实值 value，不允许两个元素拥有相同的 key；set 元素的键值就是实值，也不允许两个元素拥有相同的键值。
• 查找、删除、添加的时间复杂度稳定在 O(logn)。
• 二叉搜索树的特点是左子树上所有节点的键值都小于根节点的键值，右子树上所有节点的键值都大于根节点的键值，使用中序遍历可将键值按照从小到大遍历出来。

重点代码：

• map 重载中括号（比如：mp[7] = 3）

_Tp& operator[](const key_type& __k) {
    iterator __i = lower_bound(__k);
    // key_comp()使得前者必须小于后者，保证了不会有重复的 key
    if (__i == end() || key_comp()(__k, (*__i).first))
        // 下句的逗号后部分构造了一个新的 pair 
        __i = insert(__i, value_type(__k, _Tp()));
    return (*__i).second;
}

插入后，返回 iterator 其中 .second 的引用，即 int&，赋值为 3。

ps：lower_bound 返回指向第一个不小于给定值的元素的迭代器，upper_bound 返回指向第一个大于给定值的元素的迭代器。

unordered_set / unordered_map

• 底层基于哈希表实现，因此其元素的排列是杂乱无序的。
• 查找、删除、添加的时间复杂度平均为 O(1)，最坏会退化至 O(n)（哈希冲突）。

multiset / multimap

• 通过扩展红黑树的比较函数从而支持重复元素，
• 元素有序，时间复杂度与 set / map 一致。

// set 比较函数
if (new_key < node.key) {
    // 向左子树插入
} else if (node.key < new_key) {
    // 向右子树插入
} else {
    // 键已存在，拒绝插入（set 的特性）
}

// multiset 比较函数
if (new_key < node.key) {
    // 向左子树插入
} else {
    // 向右子树插入（包括 new_key == node.key 的情况）
    // key 相同时，新节点会被插入到右子树的最左端（即中序遍历时，相同键按插入顺序排列）。
}