1. map容器基础

1.1 基本概念

map是C++ STL中的关联容器，它存储的是键值对(key-value pairs)，具有以下特性：

• 唯一键值：每个键只能出现一次
• 自动排序：元素按键的升序自动排列
• 高效查找：基于红黑树实现，查找时间复杂度为O(log n)

1.2 头文件与声明

使用map需要包含头文件：

#include <map>

声明一个map：

map<int, string> mapStu;  // 键为int，值为string

1.3 插入元素

有几种插入元素的方法：

1. 使用insert()和pair：

mapStu.insert(pair<int, string>(1, "刘琴"));
mapStu.insert(pair<int, string>(2, "胡景华"));

2. 使用[]操作符：

mapStu[6] = "赵六";  // 更简洁的语法

注意：[]操作符如果键不存在会创建新元素，如果键存在则会覆盖原有值。

1.4 遍历map

使用迭代器遍历map：

for (map<int, string>::iterator it = mapStu.begin(); it != mapStu.end(); it++) {
    cout << (*it).first << ", " << (*it).second << endl;
}

或者使用C++11的范围for循环：

for (const auto& pair : mapStu) {
    cout << pair.first << ", " << pair.second << endl;
}

2. multimap容器

2.1 基本概念

multimap与map类似，但有重要区别：

• 允许重复键：同一个键可以关联多个值
• 不支持[]操作符：因为一个键可能对应多个值

2.2 声明与插入

声明multimap：

multimap<int, string> muMapStu;

插入元素只能使用insert()：

muMapStu.insert(pair<int, string>(1, "小狗"));
muMapStu.insert(pair<int, string>(4, "小猪"));
muMapStu.insert(pair<int, string>(4, "小猪崽"));  // 允许重复键

2.3 遍历multimap

遍历方式与map类似：

for (multimap<int, string>::iterator it = muMapStu.begin(); it != muMapStu.end(); it++) {
    cout << "key:" << (*it).first << "  value:" << (*it).second << endl;
}

3. map与multimap的主要区别

特性	map	multimap
键唯一性	键唯一	允许重复键
[ ]操作符	支持	不支持
插入方式	insert或[]	只能使用insert
查找返回值	单个迭代器	可能多个值

4. 常用操作详解

4.1 查找元素

对于map：

auto it = mapStu.find(3);  // 查找键为3的元素
if (it != mapStu.end()) {
    cout << "找到: " << it->second << endl;
}

对于multimap，一个键可能对应多个值：

auto range = muMapStu.equal_range(4);  // 查找键为4的所有元素
for (auto it = range.first; it != range.second; ++it) {
    cout << it->second << endl;
}

4.2 删除元素

删除指定键的元素：

mapStu.erase(3);  // 删除键为3的元素

4.3 元素计数

统计某个键出现的次数：

int count = muMapStu.count(4);  // 对于multimap可能大于1

5. 实际应用场景

5.1 map适用场景

• 电话簿（姓名-电话号码）
• 学生成绩系统（学号-成绩）
• 配置参数（参数名-参数值）

5.2 multimap适用场景

• 单词在文档中的位置（单词-位置列表）
• 学生选课系统（学生ID-所选课程）
• 日志记录（时间戳-日志消息）

6. 性能考虑

• 插入和删除：O(log n)时间复杂度
• 查找：O(log n)时间复杂度
• 内存：比顺序容器占用更多内存，因为需要维护树结构

7. 完整代码回顾

#include <iostream>
#include <map>

using namespace std;

int main() {
    // map示例
    map<int, string> mapStu;
    mapStu.insert(pair<int, string>(1, "王胖子"));
    mapStu.insert(pair<int, string>(2, "胡八一"));
    mapStu.insert(pair<int, string>(3, "张三"));
    mapStu.insert(pair<int, string>(4, "李四"));
    mapStu.insert(pair<int, string>(5, "王五"));
    mapStu[6] = "赵六";  // 使用[]操作符插入

    cout << "map内容:" << endl;
    for (auto it = mapStu.begin(); it != mapStu.end(); it++) {
        cout << it->first << ", " << it->second << endl;
    }

    // multimap示例
    multimap<int, string> muMapStu;
    muMapStu.insert(pair<int, string>(1, "小狗"));
    muMapStu.insert(pair<int, string>(2, "小猫"));
    muMapStu.insert(pair<int, string>(3, "小牛"));
    muMapStu.insert(pair<int, string>(4, "小猪"));
    muMapStu.insert(pair<int, string>(4, "小猪崽"));  // 重复键

    cout << "\nmultimap内容:" << endl;
    for (auto it = muMapStu.begin(); it != muMapStu.end(); it++) {
        cout << "key:" << it->first << "  value:" << it->second << endl;
    }

    system("pause");
    return 0;
}

8. 最佳实践建议

1. 选择合适的容器：需要键唯一用map，允许重复键用multimap
2. 避免频繁插入删除：这类操作会导致迭代器失效
3. 考虑排序成本：如果不需要自动排序，可以考虑unordered_map
4. 使用emplace：C++11后推荐使用emplace代替insert提高效率

通过本文的学习，你应该已经掌握了map和multimap的核心用法和区别。记住根据实际需求选择合适的容器，并注意它们的特性和限制。