C++ map 与 multimap 核心用法及底层原理
map 类简介
map 是 C++ STL 中基于红黑树实现的关联容器，存储 Key-Value 键值对。Key 必须支持小于比较（默认 less<Key>），且 Key 唯一有序。底层内存由空间配置器管理，增删查改时间复杂度为 O(logN)。迭代器遍历时按 Key 升序排列。
template<class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key, T>>>
class map;
通常开发中只需关注前两个模板参数，后两个使用默认值即可。
pair 类型基础
map 内部存储的是 pair<const Key, T> 结构。pair 是一个类模板，将两个不同类型的数据耦合在一起，成员包括 first (Key) 和 second (Value)。
template<class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
// ... 构造函数省略
};
在 map 中，first 对应 Key，second 对应 Value。理解 pair 是掌握 map 操作的关键。
map 的构造与遍历
map 支持多种构造方式，包括默认构造、范围构造、拷贝构造以及初始化列表构造。由于底层是二叉搜索树，正向迭代器遍历默认按 Key 升序。
注意： map 支持修改 Value 数据，但不支持直接修改 Key 数据。修改 Key 会破坏红黑树的结构平衡。
// 初始化列表构造 (C++11)
map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};
// 遍历
for (auto it = scores.begin(); it != scores.end(); ++it) {
cout << it->first << << it->second << endl;
}