跳到主要内容

C++ 中的map容器详解

什么是map容器？​

Map是C++ STL（标准模板库）中提供的一种关联容器，它存储的是键值对（key-value pairs）元素，其中每个键都是唯一的。Map容器内部实现是一棵红黑树（平衡二叉搜索树），这使得map中的元素按照键（key）自动排序。

map容器的主要特点：

  1. 键值对存储 - 每个元素包含一个键和一个相关联的值
  2. 唯一键 - 每个键在map中只能出现一次
  3. 自动排序 - 元素按照键的顺序被自动排序
  4. 快速访问 - 可以通过键快速查找对应的值
提示

如果你需要一个可以通过键快速查找值的数据结构，而且希望这些元素能够保持顺序，map是一个很好的选择！

map容器的基本语法​

头文件和声明​

要使用map容器，需要先包含相应的头文件：

cpp
#include <map>

int main() {
    // 创建一个将字符串映射到整数的map
    std::map<std::string, int> studentScores;
    
    // 其他代码...
    
    return 0;
}

插入元素​

向map中插入元素有多种方法：

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

int main() {
    std::map<std::string, int> studentScores;
    
    // 方法1：使用insert()函数插入pair
    studentScores.insert(std::pair<std::string, int>("Alice", 95));
    
    // 方法2：使用make_pair()函数
    studentScores.insert(std::make_pair("Bob", 89));
    
    // 方法3：使用数组下标操作符
    studentScores["Charlie"] = 78;
    studentScores["David"] = 92;
    
    // 输出map中的元素
    for (const auto& student : studentScores) {
        std::cout << student.first << ": " << student.second << std::endl;
    }
    
    return 0;
}

输出结果：

Alice: 95
Bob: 89
Charlie: 78
David: 92
备注

注意到输出的元素按照键（学生姓名）的字母顺序排列，这是因为map默认使用<运算符对键进行排序。

map容器的常用操作​

查找元素​

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

int main() {
    std::map<std::string, int> studentScores;
    studentScores["Alice"] = 95;
    studentScores["Bob"] = 89;
    studentScores["Charlie"] = 78;
    
    // 使用find()函数查找元素
    auto it = studentScores.find("Bob");
    if (it != studentScores.end()) {
        std::cout << "找到了Bob的分数：" << it->second << std::endl;
    } else {
        std::cout << "没有找到Bob" << std::endl;
    }
    
    // 使用count()函数检查键是否存在
    if (studentScores.count("David") > 0) {
        std::cout << "David的分数是：" << studentScores["David"] << std::endl;
    } else {
        std::cout << "没有David的记录" << std::endl;
    }
    
    return 0;
}

输出结果：

找到了Bob的分数：89
没有David的记录

删除元素​

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

int main() {
    std::map<std::string, int> studentScores;
    studentScores["Alice"] = 95;
    studentScores["Bob"] = 89;
    studentScores["Charlie"] = 78;
    studentScores["David"] = 92;
    
    std::cout << "初始map大小: " << studentScores.size() << std::endl;
    
    // 通过键删除元素
    studentScores.erase("Bob");
    std::cout << "删除Bob后map大小: " << studentScores.size() << std::endl;
    
    // 通过迭代器删除元素
    auto it = studentScores.find("Charlie");
    if (it != studentScores.end()) {
        studentScores.erase(it);
    }
    
    std::cout << "删除Charlie后map大小: " << studentScores.size() << std::endl;
    
    // 删除所有元素
    studentScores.clear();
    std::cout << "清空后map大小: " << studentScores.size() << std::endl;
    
    return 0;
}

输出结果：

初始map大小: 4
删除Bob后map大小: 3
删除Charlie后map大小: 2
清空后map大小: 0

遍历map​

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

int main() {
    std::map<std::string, int> studentScores;
    studentScores["Alice"] = 95;
    studentScores["Bob"] = 89;
    studentScores["Charlie"] = 78;
    
    // 方法1：使用范围for循环（C++11及以上）
    std::cout << "使用范围for循环遍历：" << std::endl;
    for (const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 方法2：使用迭代器
    std::cout << "\n使用迭代器遍历：" << std::endl;
    for (auto it = studentScores.begin(); it != studentScores.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }
    
    return 0;
}

输出结果：

使用范围for循环遍历：
Alice: 95
Bob: 89
Charlie: 78

使用迭代器遍历：
Alice: 95
Bob: 89
Charlie: 78

map的其他常用功能​

检查容器是否为空​

cpp
if (studentScores.empty()) {
    std::cout << "容器为空" << std::endl;
} else {
    std::cout << "容器不为空，包含 " << studentScores.size() << " 个元素" << std::endl;
}

获取map大小​

cpp
std::cout << "map中有 " << studentScores.size() << " 个元素" << std::endl;

交换两个map​

cpp
std::map<std::string, int> map1 = {{"A", 1}, {"B", 2}};
std::map<std::string, int> map2 = {{"X", 24}, {"Y", 25}};

map1.swap(map2);  // 现在map1包含{"X", 24}和{"Y", 25}，map2包含{"A", 1}和{"B", 2}

获取上下界​

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

int main() {
    std::map<int, std::string> codeNames;
    codeNames[1] = "Alpha";
    codeNames[3] = "Charlie";
    codeNames[5] = "Echo";
    codeNames[7] = "Golf";
    
    // 找到键值为3的元素
    auto it_lower = codeNames.lower_bound(3);  // 指向键为3的元素
    std::cout << "lower_bound(3): " << it_lower->first << " -> " << it_lower->second << std::endl;
    
    // 找到键值大于3的第一个元素
    auto it_upper = codeNames.upper_bound(3);  // 指向键为5的元素
    std::cout << "upper_bound(3): " << it_upper->first << " -> " << it_upper->second << std::endl;
    
    return 0;
}

输出结果：

lower_bound(3): 3 -> Charlie
upper_bound(3): 5 -> Echo

实际应用场景​

场景1：单词频率统计​

cpp
#include <iostream>
#include <map>
#include <string>
#include <sstream>

int main() {
    std::string text = "apple banana apple orange banana apple pear";
    std::istringstream iss(text);
    std::map<std::string, int> wordFreq;
    std::string word;
    
    // 统计每个单词出现的次数
    while (iss >> word) {
        // 每次遇到单词时，对应的计数加1
        wordFreq[word]++;
    }
    
    // 输出每个单词及其频率
    std::cout << "单词频率统计：" << std::endl;
    for (const auto& pair : wordFreq) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

输出结果：

单词频率统计：
apple: 3
banana: 2
orange: 1
pear: 1

场景2：学生成绩管理系统​

cpp
#include <iostream>
#include <map>
#include <string>
#include <iomanip>

class StudentManager {
private:
    std::map<std::string, std::map<std::string, int>> studentScores;  // 学生id -> {课程名 -> 分数}

public:
    // 添加或更新学生成绩
    void addScore(const std::string& studentId, const std::string& course, int score) {
        studentScores[studentId][course] = score;
    }
    
    // 获取学生特定课程的成绩
    int getScore(const std::string& studentId, const std::string& course) {
        if (studentScores.find(studentId) != studentScores.end() &&
            studentScores[studentId].find(course) != studentScores[studentId].end()) {
            return studentScores[studentId][course];
        }
        return -1;  // 表示不存在
    }
    
    // 计算学生的平均分
    double getAverage(const std::string& studentId) {
        if (studentScores.find(studentId) == studentScores.end() || 
            studentScores[studentId].empty()) {
            return 0.0;
        }
        
        double sum = 0.0;
        for (const auto& course : studentScores[studentId]) {
            sum += course.second;
        }
        return sum / studentScores[studentId].size();
    }
    
    // 显示所有学生的所有成绩
    void displayAllScores() {
        for (const auto& student : studentScores) {
            std::cout << "学生ID: " << student.first << std::endl;
            for (const auto& course : student.second) {
                std::cout << "  " << course.first << ": " << course.second << std::endl;
            }
            std::cout << "  平均分: " << std::fixed << std::setprecision(2) 
                      << getAverage(student.first) << std::endl << std::endl;
        }
    }
};

int main() {
    StudentManager manager;
    
    // 添加一些学生成绩
    manager.addScore("10001", "Math", 95);
    manager.addScore("10001", "English", 87);
    manager.addScore("10001", "Physics", 92);
    
    manager.addScore("10002", "Math", 82);
    manager.addScore("10002", "English", 78);
    manager.addScore("10002", "Chemistry", 90);
    
    // 显示所有成绩
    manager.displayAllScores();
    
    // 查询特定学生的特定课程分数
    std::cout << "学生10001的英语成绩: " << manager.getScore("10001", "English") << std::endl;
    
    return 0;
}

输出结果：

学生ID: 10001
  English: 87
  Math: 95
  Physics: 92
  平均分: 91.33

学生ID: 10002
  Chemistry: 90
  English: 78
  Math: 82
  平均分: 83.33

学生10001的英语成绩: 87

使用自定义类型作为键​

要在map中使用自定义类型作为键，需要为该类型定义一个比较函数：

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

// 自定义类型
struct Student {
    int id;
    std::string name;
    
    // 定义小于操作符，用于map排序
    bool operator<(const Student& other) const {
        return id < other.id;  // 按学生ID排序
    }
};

int main() {
    // 使用Student作为键，int作为值的map
    std::map<Student, int> studentScores;
    
    // 添加元素
    studentScores[{101, "Alice"}] = 95;
    studentScores[{102, "Bob"}] = 89;
    studentScores[{103, "Charlie"}] = 78;
    
    // 遍历并输出
    for (const auto& pair : studentScores) {
        std::cout << "ID: " << pair.first.id 
                  << ", 姓名: " << pair.first.name 
                  << ", 分数: " << pair.second << std::endl;
    }
    
    return 0;
}

输出结果：

ID: 101, 姓名: Alice, 分数: 95
ID: 102, 姓名: Bob, 分数: 89
ID: 103, 姓名: Charlie, 分数: 78
警告

对于自定义类型，必须定义比较操作符（通常是<），否则编译器将无法排序map的元素。

map与unordered_map的比较​

C++ STL提供了两种键值对容器：map和unordered_map。以下是它们之间的主要区别：

特性mapunordered_map
内部实现红黑树哈希表
元素顺序按键排序无序
查找复杂度O(log n)平均O(1)，最坏O(n)
插入复杂度O(log n)平均O(1)，最坏O(n)
删除复杂度O(log n)平均O(1)，最坏O(n)
内存消耗较少较多（需要哈希表开销）
迭代器稳定性删除元素时不会失效如果rehash可能失效
适用场景需要有序，需要稳定的迭代器速度优先，不关心顺序

根据您的具体需求选择适当的容器:

  • 如果需要元素自动排序，选择map
  • 如果查找速度是最重要的，选择unordered_map

总结​

map是C++ STL中一种非常实用的关联容器，它提供了键值对的存储方式，并且会根据键自动对元素进行排序。本文中，我们学习了：

  1. map的基本概念和特点
  2. 如何创建map并添加、访问、删除元素
  3. map的各种常用操作，如find()、count()、size()等
  4. 如何遍历map中的元素
  5. 使用自定义类型作为map的键
  6. map与unordered_map的区别和选择标准
  7. map在实际应用中的案例

使用map容器可以帮助我们轻松实现需要键值映射的各种功能，例如单词频率统计、学生成绩管理、电话簿等。随着您对C++的理解加深，map将成为您编程工具箱中一个不可或缺的工具。

练习题​

  1. 编写一个程序，统计一个文本文件中各字符出现的频率。
  2. 实现一个简单的电话簿程序，可以添加、查找、删除联系人。
  3. 使用map实现一个单词翻译器，将英文单词映射到中文释义。
  4. 编写一个程序，统计给定文章中每个单词出现的次数，并按照出现频率降序输出。
  5. 创建一个使用自定义类型Person作为键的map，其中Person包含姓名和年龄，并实现按姓名排序。

进一步学习资源​

  • C++ STL官方文档
  • 《C++ Primer》第11章：关联容器
  • 《Effective STL》：Scott Meyers著
  • C++ Reference网站的map部分
  • 《The C++ Standard Library》：Nicolai Josuttis著