STL-map笔记
当前没有测试数据。
2. map（键值对容器，自动排序）
用途
存储“键-值”对（如统计次数时“数字-次数”），自动按键从小到大排序，键唯一。
核心特性
① 底层基于红黑树实现，插入、查找、删除时间复杂度均为O(logn)（竞赛高效关键）； ② 键必须支持比较运算（如int、string，自定义类型需重载<）； ③ 迭代器遍历顺序就是键的排序顺序，可直接按序访问。
核心定义方式
map需指定键类型和值类型，键需支持比较运算，常见方式如下：
| 定义方式 | 说明 | 示例 |
|---|---|---|
| 默认构造 | 创建空的map，键值对数量为0 | map<int, int> m; |
| 拷贝构造 | 用已有的map创建新map | map<int, int> m1; map<int, int> m2(m1); |
| 列表初始化 | 用键值对列表直接赋值，键自动排序 | map<int, int> m = {{1,2}, {3,4}, {2,1}}; |
| 指定比较方式 | 自定义键的排序规则（如降序），需用greater | map<int, int, greater<int>> m;// 键降序 |
map常用函数
| 函数名 | 功能说明 | 示例 |
|---|---|---|
| insert({key,value}) | 插入新的元素 不会插入重复值 检测到键重复插入失败 不会作任何更新 | m.insert({"张三",13}); |
| operator[] ★ | 通过键访问值，键不存在则自动创建并初始化值（默认0） | m[3] = 1; // 键3的值设为1 |
| size()/empty()/clear() ★ | 功能同vector，分别对应大小、判空、清空 | if (!m.empty()) { m.clear(); } |
| count(key) ★ | 判断键key是否存在，返回1（存在）或0（不存在） | if (m.count(3)) { ... } |
| find(key) ★ | 查找键key，返回指向该键值对的迭代器；不存在则返回end() | auto it = m.find(3); if (it != m.end()) { ... } |
| erase(key/it) ★ | 删除指定键或迭代器指向的键值对 | m.erase(3); // 删除键为3的键值对 |
map的遍历
1-范围for循环
i 是 map 里的键值对对象（pair<string, int>），不是指针 / 迭代器
for(auto i : a){
cout << i.first << " " << i.second << endl;
}
2-迭代器遍历
for (map<string, int>::iterator it = a.begin(); it != a.end(); it++) {
cout << it->first << " " << it->second << endl;
}
3-auto简化迭代器
for (auto it = a.begin(); it != a.end(); it++) {
cout << it->first << " " << it->second << endl;
}
相关
在以下作业中: