成员函数

访问

成员函数	函数说明
at(key)	带有边界检查，返回对键为 key 的元素的引用。如果键不存在，则抛出 std::out_of_range 异常。
operator[](key)	如果键 key 不存在，则插入一个新元素并返回对它的引用；如果键存在，返回对现有元素的引用。
find(key)	查找键为 key 的元素。如果找到，返回指向该元素的迭代器；否则返回 end()。
count(key)	返回键为 key 的元素数量。由于 map 的键唯一，该函数返回值只能是 0 或 1。
lower_bound(key)	返回一个迭代器，指向键不小于 key 的第一个元素。
upper_bound(key)	返回一个迭代器，指向键大于 key 的第一个元素。

修改

成员函数	说明
insert(value)	插入一个键值对 value。如果键已存在，则插入失败。
emplace(Args&&... args)	通过就地构造一个新元素，并将其插入到 map 中。
erase(const_iterator position)	移除 position 处的元素。
erase(key)	移除键为 key 的所有元素，返回被移除的元素数量。
clear()	移除所有元素，使 map 变为空。
swap(map& other)	与另一个 map 交换内容。

容量

成员函数	说明
empty()	如果 map 中没有元素，则返回 true。
size()	返回 map 中元素的数量。
max_size()	返回 map 可以容纳的最大元素数量。

迭代器

成员函数	说明
begin()	返回指向第一个元素的迭代器。
end()	返回指向最后一个元素之后位置的迭代器。
rbegin()	返回指向最后一个元素的反向迭代器。
rend()	返回指向第一个元素之前位置的反向迭代器。
cbegin()	返回指向第一个元素的 const 迭代器。
cend()	返回指向最后一个元素之后位置的 const 迭代器。
crbegin()	返回指向最后一个元素的 const 反向迭代器。
crend()	返回指向第一个元素之前位置的 const 逆向迭代器。

复杂度

操作	复杂度	说明
访问元素 map::at() map::operator[]	O(logn)	查找键并访问其对应的值。
插入元素 map::insert() map::emplace() map::operator[]	O(logn)	查找插入位置并插入新元素，并可能需要重新平衡树。
删除元素 map::erase()	O(logn)	查找要删除的元素并将其移除，并重新平衡树。
查找元素 map::find()	O(logn)
清空 map::clear()	O(n)
获取大小 map::size()	O(1)

实现分析

std::map 基于红黑树实现。

红黑树是一种特殊的自平衡二叉搜索树，它的主要特点是能保证树的高度始终保持在一个相对较小的范围内，从而确保了所有基本操作的时间复杂度都是稳定的对数时间 O(logn)。

一个简单的二叉搜索树在最坏情况下会退化成一个链表，导致操作的复杂度变为 O(n)。红黑树通过引入以下规则进行自平衡：

• 每个节点都带有颜色（红色或黑色）。
• 根节点是黑色的。
• 所有叶子节点是黑色的。
• 每个红色节点的两个子节点都是黑色的。
• 从任一节点到其所有叶子节点的路径上包含相同数目的黑色节点。

这些规则确保了从根节点到最远叶子节点的路径长度不会超过最短路径长度的两倍，从而保证了树的相对平衡。

---