C++ std::map 使用详细指南

目录

  1. 什么是 std::map
  2. 基本用法
  3. 常用操作
  4. 遍历 map
  5. 性能特点
  6. 实际示例
  7. 常见问题

什么是 std::map

std::map 是 C++ 标准模板库(STL)中的一个关联容器，它存储键值对(key-value pairs)，并根据键自动排序。

特点：

  • 键是唯一的（不允许重复）
  • 按键自动排序（默认升序）
  • 基于红黑树实现
  • 查找、插入、删除的时间复杂度：O(log n)

基本用法

头文件

1
2
3
#include <map>
#include <iostream>
#include <string>

声明和初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 基本声明
std::map<std::string, int> studentScores;

// 初始化列表（C++11及以上）
std::map<std::string, int> studentScores = {
    {"Alice", 90},
    {"Bob", 85},
    {"Charlie", 92}
};

// 使用 make_pair
std::map<int, std::string> idToName;
idToName.insert(std::make_pair(1, "Alice"));
idToName.insert(std::make_pair(2, "Bob"));

常用操作

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
std::map<std::string, int> scores;

// 方法1：使用 [] 运算符
scores["Alice"] = 95;
scores["Bob"] = 87;

// 方法2：使用 insert 函数
scores.insert(std::make_pair("Charlie", 92));
scores.insert({"David", 88});  // C++11

// 方法3：使用 emplace（C++11，更高效）
scores.emplace("Eve", 91);

访问元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::map<std::string, int> scores = {{"Alice", 95}, {"Bob", 87}};

// 方法1：使用 [] 运算符（如果键不存在会创建）
std::cout << scores["Alice"] << std::endl;  // 输出: 95

// 方法2：使用 at() 函数（如果键不存在会抛出异常）
std::cout << scores.at("Bob") << std::endl; // 输出: 87

// 方法3：使用 find() 函数（安全的方式）
auto it = scores.find("Charlie");
if (it != scores.end()) {
    std::cout << it->second << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

修改元素

1
2
3
4
5
6
7
8
9
10
std::map<std::string, int> scores = {{"Alice", 95}};

// 直接赋值修改
scores["Alice"] = 98;

// 通过迭代器修改值（不能修改键）
auto it = scores.find("Alice");
if (it != scores.end()) {
    it->second = 100;  // 修改值
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::map<std::string, int> scores = {
    {"Alice", 95}, {"Bob", 87}, {"Charlie", 92}
};

// 方法1：通过键删除
scores.erase("Bob");

// 方法2：通过迭代器删除
auto it = scores.find("Charlie");
if (it != scores.end()) {
    scores.erase(it);
}

// 方法3：删除范围内的元素
scores.erase(scores.begin(), std::next(scores.begin(), 2));

// 方法4：清空所有元素
scores.clear();

查找和判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::map<std::string, int> scores = {{"Alice", 95}, {"Bob", 87}};

// 查找元素
auto it = scores.find("Alice");
if (it != scores.end()) {
    std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
}

// 检查元素是否存在（C++20）
if (scores.contains("Alice")) {  // C++20
    std::cout << "Alice exists" << std::endl;
}

// 计数（对于map，只能是0或1）
if (scores.count("Bob") > 0) {
    std::cout << "Bob exists" << std::endl;
}

// 检查是否为空
if (scores.empty()) {
    std::cout << "Map is empty" << std::endl;
}

遍历 map

使用迭代器

1
2
3
4
5
6
7
8
9
10
11
std::map<std::string, int> scores = {{"Alice", 95}, {"Bob", 87}, {"Charlie", 92}};

// 正向迭代器
for (auto it = scores.begin(); it != scores.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

// 反向迭代器
for (auto it = scores.rbegin(); it != scores.rend(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

使用范围循环（C++11）

1
2
3
4
5
6
7
8
9
10
11
std::map<std::string, int> scores = {{"Alice", 95}, {"Bob", 87}, {"Charlie", 92}};

// 值拷贝（不推荐用于大对象）
for (const auto& pair : scores) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

// 引用（推荐）
for (const auto& [key, value] : scores) {  // C++17 结构化绑定
    std::cout << key << ": " << value << std::endl;
}

容量信息

1
2
3
4
5
6
7
std::map<std::string, int> scores = {{"Alice", 95}, {"Bob", 87}};

// 元素数量
std::cout << "Size: " << scores.size() << std::endl;

// 最大可能的大小
std::cout << "Max size: " << scores.max_size() << std::endl;

自定义比较函数

自定义排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 按字符串长度排序
struct StringLengthComparator {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

std::map<std::string, int, StringLengthComparator> scoresByLength;

// 使用 lambda 表达式（C++11）
auto comparator = [](const std::string& a, const std::string& b) {
    return a.length() < b.length();
};
std::map<std::string, int, decltype(comparator)> scores(comparator);

降序排列

1
2
3
4
5
6
7
8
9
10
// 方法1：使用 std::greater
std::map<int, std::string, std::greater<int>> descendingMap;

// 方法2：自定义比较函数
struct DescendingComparator {
    bool operator()(int a, int b) const {
        return a > b;  // 降序
    }
};
std::map<int, std::string, DescendingComparator> customDescendingMap;

性能特点

操作 时间复杂度 说明
插入 O(log n) 基于红黑树
查找 O(log n) 基于红黑树
删除 O(log n) 基于红黑树
遍历 O(n) 顺序访问所有元素
空间 O(n) 存储所有键值对

实际示例

示例1：单词计数器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> wordCount;
    std::string word;
    
    // 读取单词并计数
    while (std::cin >> word) {
        ++wordCount[word];
    }
    
    // 输出结果
    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << std::endl;
    }
    
    return 0;
}

示例2：学生成绩管理系统

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <map>
#include <string>

class StudentManager {
private:
    std::map<int, std::string> students;  // 学号 -> 姓名
    
public:
    void addStudent(int id, const std::string& name) {
        students[id] = name;
    }
    
    void removeStudent(int id) {
        students.erase(id);
    }
    
    std::string findStudent(int id) {
        auto it = students.find(id);
        if (it != students.end()) {
            return it->second;
        }
        return "Not found";
    }
    
    void printAllStudents() {
        for (const auto& [id, name] : students) {
            std::cout << "ID: " << id << ", Name: " << name << std::endl;
        }
    }
};

int main() {
    StudentManager manager;
    
    manager.addStudent(1001, "Alice");
    manager.addStudent(1002, "Bob");
    manager.addStudent(1003, "Charlie");
    
    std::cout << "All students:" << std::endl;
    manager.printAllStudents();
    
    std::cout << "\nStudent with ID 1002: " << manager.findStudent(1002) << std::endl;
    
    manager.removeStudent(1001);
    std::cout << "\nAfter removing ID 1001:" << std::endl;
    manager.printAllStudents();
    
    return 0;
}

常见问题

1. 键不存在时的行为

1
2
3
4
5
6
7
std::map<std::string, int> scores;

// 使用 [] 访问不存在的键会创建该键（值为默认构造）
int value = scores["Unknown"];  // 创建键 "Unknown"，值为 0

// 使用 at() 会抛出 std::out_of_range 异常
// int value = scores.at("Unknown");  // 抛出异常

2. 迭代器失效

1
2
3
4
5
6
7
8
std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};
auto it = myMap.find(1);

// 删除操作会使指向被删除元素的迭代器失效
myMap.erase(it);
// it 现在已失效，不能再使用

// 但其他迭代器仍然有效

3. 性能考虑

1
2
3
// 如果不需要排序，考虑使用 std::unordered_map（哈希表）
#include <unordered_map>
std::unordered_map<std::string, int> hashMap;  // 平均 O(1) 操作

4. 自定义类型作为键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Person {
    std::string name;
    int age;
    
    // 需要定义比较运算符
    bool operator<(const Person& other) const {
        if (name == other.name) {
            return age < other.age;
        }
        return name < other.name;
    }
};

std::map<Person, int> personScores;

总结

std::map 是 C++ 中非常有用的关联容器，适用于需要按键排序和快速查找的场景。掌握它的基本用法和特性，能够帮助你在编程中更高效地处理键值对数据。

关键要点：

  • 使用 [] 运算符进行插入和访问
  • 使用 find() 进行安全查找
  • 使用范围循环进行遍历
  • 了解时间复杂度特征
  • 根据需求选择合适的比较函数