C++ map 与 multimap 核心用法及底层原理

map 的插入机制

插入数据有多种方式，核心都是向容器中添加 pair<const Key, T> 对象。

常见插入方法

1. 显式创建 pair 对象：语义清晰，适合复杂类型。
2. make_pair 函数：自动推导类型，减少代码量。
3. 初始化列表：C++11 起支持，最简洁。

map<string, string> dict;

// 法一：有名 pair
pair<string, string> kv("left", "左边");
dict.insert(kv);

// 法二：匿名 pair
dict.insert(pair<string, string>("right", "右边"));

// 法三：make_pair (自动推导)
dict.insert(make_pair("insert", "插入"));

// 法四：初始化列表 (推荐)
dict.insert({"string", "字符串"});

返回值与重复 Key

insert 返回一个 pair<iterator, bool>。如果 Key 已存在，插入失败，返回的 bool 为 false，迭代器指向已有元素；如果插入成功，bool 为 true。

这意味着即使传入相同的 Key，只要 Value 不同，也不会覆盖旧值，插入操作依然会失败。这与 operator[] 的行为有本质区别。

operator[] 的魔法

operator[] 是 map 中最常用的操作符，它集成了查找、插入和修改功能。

int main() {
    map<string, int> countMap;
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};

    for (const auto& str : arr) {
        countMap[str]++;  // 一行搞定统计逻辑
    }
    return 0;
}

底层原理

为什么 countMap[str]++ 能同时处理'不存在'和'存在'的情况？

1. 查找或插入：operator[] 内部先调用 insert(make_pair(k, mapped_type()))。如果 Key 不存在，它会插入一个默认构造的 Value（例如 int 默认为 0）。
2. 返回引用：无论插入是否成功，它都返回该 Key 对应 Value 的引用。
3. 自增：拿到引用后执行 ++，如果是新插入的则为 1，如果是已有的则累加。

这种设计让计数统计变得异常简单，但也意味着每次访问都会尝试插入默认值，性能上略低于 find + insert 的组合，但在可读性上优势明显。

注意事项

• Key 不可变：通过 operator[] 获取的 Value 引用可以修改，但 Key 不能改。
• multimap 不支持：由于 multimap 允许 Key 重复，operator[] 无法确定返回哪个 Key 对应的 Value，因此 multimap 不提供此操作符。

multimap 与 map 的差异

multimap 的使用接口与 map 高度相似，主要区别在于 Key 的冗余性。

当需要存储多个相同 Key 的值时（如学生成绩表，同一科目多次考试），应使用 multimap。

equal_range 接口

equal_range 用于获取相等元素的范围，返回一对迭代器 [first, last)。在 multimap 中，这非常有用，因为它能一次性取出所有相同 Key 的记录。

std::multimap<char, int> mymm;
mymm.insert(std::make_pair('a', 10));
mymm.insert(std::make_pair('b', 20));
mymm.insert(std::make_pair('b', 30));

auto range = mymm.equal_range('b');
for (auto it = range.first; it != range.second; ++it) {
    cout << it->second << endl;
}

总结

• map 基于红黑树，Key 有序且唯一，O(logN) 效率。
• 插入常用 insert 配合 pair 或 make_pair，C++11 支持 {} 语法。
• operator[] 会自动插入默认值并返回引用，适合计数场景，但 multimap 不支持。
• multimap 允许 Key 重复，需配合 equal_range 使用。

掌握这些细节，能让你在处理关联数据时更加得心应手。