map/multimap容器：从入门到实战

map和multimap，说白了就是关联容器里的"字典"。你给它一个键，它立马还你一个值。我刚开始用STL时，觉得这玩意儿不就是个高级数组嘛？后来才发现，它背后的红黑树结构，才是真正的精髓所在。

map的基本概念

map存储的是键值对——每个元素都是一个pair。键是唯一的，值可以重复。multimap呢？它允许键重复。就这么点区别。

我记得有一次做用户信息缓存，需要根据用户ID快速查找。用map简直不要太爽——O(log n)的查找速度，比遍历vector快了一个数量级。

map的构造与赋值

构造map的方式有好几种，我平时最常用的是默认构造和初始化列表构造。

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

using namespace std;

// 默认构造
map<int, string> m1;

// 初始化列表构造（C++11起）
map<int, string> m2 = {
    {1, "张三"},
    {2, "李四"},
    {3, "王五"}
};

// 拷贝构造
map<int, string> m3(m2);

// 赋值操作
map<int, string> m4;
m4 = m2;

嗯，这里要注意：map的键类型必须支持<操作符。如果你用自定义类型做键，记得重载operator<。我曾经在这上面栽过跟头——自定义结构体忘了重载，编译报错找了半天。

map大小与交换

大小操作很简单，跟其他容器差不多。但有个细节——size()返回的是键值对的数量，不是所有元素的总数。

map<int, string> m = {{1, "A"}, {2, "B"}, {3, "C"}};

// 大小
cout << "size: " << m.size() << endl;      // 3
cout << "empty: " << m.empty() << endl;    // 0 (false)

// 交换
map<int, string> m2 = {{4, "D"}, {5, "E"}};
m.swap(m2);
// 现在m有2个元素，m2有3个元素

交换操作是O(1)的，它只交换内部指针，不复制数据。这在需要清空一个map但又不想释放内存时特别有用。

map插入与删除

插入方式有好几种，我个人的习惯是用insert或emplace。emplace是C++11引入的，能避免临时对象的构造，性能更好。

map<int, string> m;

// 方式1：用pair
m.insert(pair<int, string>(1, "Apple"));

// 方式2：用make_pair
m.insert(make_pair(2, "Banana"));

// 方式3：用value_type
m.insert(map<int, string>::value_type(3, "Cherry"));

// 方式4：用[]（仅map）
m[4] = "Date";

// 方式5：emplace（推荐）
m.emplace(5, "Elderberry");

// 删除
m.erase(3);           // 按键删除
m.erase(m.begin());   // 按迭代器删除
m.clear();            // 清空所有

map查找与统计

查找是map的强项。find、count、lower_bound、upper_bound，各有各的用途。

map<int, string> m = {{1, "A"}, {2, "B"}, {3, "C"}, {3, "D"}};

// find：返回迭代器，找不到返回end()
auto it = m.find(2);
if (it != m.end()) {
    cout << "找到了: " << it->second << endl;
}

// count：对于map，返回0或1；对于multimap，返回实际个数
cout << "键3出现次数: " << m.count(3) << endl;  // 1（map中键唯一）

// lower_bound/upper_bound：常用于范围查找
auto low = m.lower_bound(2);  // 第一个键>=2的元素
auto up = m.upper_bound(2);   // 第一个键>2的元素

为什么count在map里只返回0或1？因为map的键是唯一的。但multimap就不一样了——它允许重复键，所以count能返回实际个数。我做过一个日志分析系统，用multimap存储时间戳和日志条目，用count统计某个时间段内的日志数量，配合lower_bound/upper_bound做范围查询，效率极高。

map排序

map默认按键升序排列。如果你想改变排序规则，可以在声明时指定仿函数或lambda。

// 降序排列
map<int, string, greater<int>> m1 = {
    {1, "A"}, {2, "B"}, {3, "C"}
};
// 遍历结果：3->C, 2->B, 1->A

// 自定义排序（按字符串长度）
struct CompareByLength {
    bool operator()(const string& a, const string& b) const {
        return a.length() < b.length();
    }
};

map<string, int, CompareByLength> m2;
m2["apple"] = 1;
m2["banana"] = 2;
m2["cherry"] = 3;
// 按键的字符串长度排序

知识体系总览

下面这张图，是我梳理的map/multimap核心知识结构。你可以把它当作学习路线图。

实战经验总结

map和multimap是我项目中使用频率最高的容器之一。我总结了几条经验：

• 优先用emplace而不是insert——减少临时对象构造，性能提升明显
• 用find而不是[]来检查键是否存在——[]会插入默认值，容易引入bug
• multimap适合一对多场景——比如一个学生有多门成绩，用multimap存学生ID到成绩的映射
• 自定义排序时确保比较器是严格弱序——否则map会崩溃，我调试过这种问题，非常隐蔽

好了，map和multimap的核心内容就这些。说白了，它就是一把双刃剑——用好了效率极高，用不好容易踩坑。多写多练，慢慢就熟练了。

---