目录
概述
<map>
是 C++ STL 中的有序关联容器,用于存储键值对(key-value pairs)。键是唯一的,元素按键的升序自动排序。它基于平衡二叉树实现,提供 O(log n) 的插入、删除和查找操作。
包含头文件
#include <map>
#include <iostream>
定义格式
std::map<键类型, 值类型, 比较器> 变量名;
键类型
:键的数据类型(如int
、std::string
)。值类型
:值的数据类型(如int
、double
)。比较器
:可选,默认是std::less<Key>
(升序),可改为std::greater<Key>
(降序)。
基本特性
- 键唯一性:每个键只能对应一个值。
- 自动排序:键按升序存储(可自定义比较器)。
- 高效操作:插入、删除、查找的时间复杂度为 O(log n)。
- 动态大小:支持运行时调整。
基本用法
声明和初始化
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m; // 空 map
std::map<int, std::string> m2 = {{1, "A"}, {2, "B"}, {3, "C"}}; // 初始化列表(C++11)
std::cout << "m2: ";
for (const auto& pair : m2) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出:{1, A} {2, B} {3, C}
return 0;
}
插入元素
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m;
m.insert({1, "Alice"}); // 插入键值对
m.insert(std::make_pair(2, "Bob"));
m[3] = "Charlie"; // 使用 [] 插入或覆盖
std::cout << "m: ";
for (const auto& pair : m) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出:{1, Alice} {2, Bob} {3, Charlie}
return 0;
}
删除元素
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
m.erase(2); // 删除键为 2 的元素
std::cout << "After erase: ";
for (const auto& pair : m) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << std::endl; // 输出:{1, A} {3, C}
return 0;
}
查找元素
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
auto it = m.find(2); // 查找键为 2 的元素
if (it != m.end()) {
std::cout << "Found: {" << it->first << ", " << it->second << "}" << std::endl; // 输出:Found: {2, B}
}
if (m.count(1)) {
std::cout << "Key 1 exists" << std::endl; // 输出:Key 1 exists
}
return 0;
}
访问和修改元素
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "A"}, {2, "B"}};
std::cout << "Value at 1: " << m[1] << std::endl; // 输出:A
m[1] = "Alice"; // 修改值
std::cout << "New value at 1: " << m.at(1) << std::endl; // 输出:Alice
// m.at(3) 若键不存在会抛出 std::out_of_range
return 0;
}
[]
:若键不存在,插入默认值(需谨慎)。at()
:若键不存在,抛异常。
大小和状态
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "A"}, {2, "B"}};
std::cout << "Size: " << m.size() << std::endl; // 输出:2
std::cout << "Empty? " << (m.empty() ? "Yes" : "No") << std::endl; // 输出:No
return 0;
}
迭代器
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "A"}, {2, "B"}, {3, "C"}};
std::cout << "Forward: ";
for (auto it = m.begin(); it != m.end(); ++it) {
std::cout << "{" << it->first << ", " << it->second << "} ";
}
std::cout << std::endl; // 输出:{1, A} {2, B} {3, C}
std::cout << "Reverse: ";
for (auto it = m.rbegin(); it != m.rend(); ++it) {
std::cout << "{" << it->first << ", " << it->second << "} ";
}
std::cout << std::endl; // 输出:{3, C} {2, B} {1, A}
return 0;
}
与 <unordered_map>
的对比
特性 | std::map | std::unordered_map |
---|---|---|
数据结构 | 平衡二叉树 | 哈希表 |
键顺序 | 升序 | 无序 |
重复键 | 不允许 | 不允许 |
查找 | O(log n) | 平均 O(1) |
插入/删除 | O(log n) | 平均 O(1) |
内存开销 | 树节点+指针 | 桶+指针 |
迭代器 | 双向 | 前向 |
注意事项
- 键唯一性:重复键插入无效,需用
<multimap>
支持重复键。 - 迭代器失效:插入不影响现有迭代器,删除使指向被删元素的迭代器失效。
- 性能:适合需要排序的场景,若只需高效查找,使用
<unordered_map>
。 []
的副作用:访问不存在的键会插入默认值。
实用示例:学生成绩管理
#include <map>
#include <iostream>
#include <string>
int main() {
std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 92;
std::cout << "Student Scores:\n";
for (const auto& pair : scores) {
std::cout << pair.first << ": " << pair.second << "\n";
}
std::string name;
std::cout << "Enter a student name to lookup: ";
std::cin >> name;
auto it = scores.find(name);
if (it != scores.end()) {
std::cout << name << "'s score: " << it->second << "\n";
} else {
std::cout << name << " not found.\n";
}
return 0;
}
输出示例:
Student Scores:
Alice: 95
Bob: 87
Charlie: 92
Enter a student name to lookup: Bob
Bob's score: 87
小练习
问题
写一个 C++ 程序:
- 定义一个
std::map<int, std::string>
。 - 插入键值对:{1, “A”}、{2, “B”}、{3, “C”}、{2, “D”}(注意重复键)。
- 删除键为 1 的元素。
- 输出所有键值对和大小。
参考答案
#include <map>
#include <iostream>
#include <string>
int main() {
std::map<int, std::string> m;
// 插入元素
m.insert({1, "A"});
m.insert({2, "B"});
m.insert({3, "C"});
m[2] = "D"; // 覆盖键 2 的值
// 删除键 1
m.erase(1);
// 输出所有键值对和大小
std::cout << "Elements: ";
for (const auto& pair : m) {
std::cout << "{" << pair.first << ", " << pair.second << "} ";
}
std::cout << "\nSize: " << m.size() << std::endl;
return 0;
}
输出:
Elements: {2, D} {3, C}
Size: 2
参考资料
- C++ Standard Library Reference:
<map>
的官方文档。
- ISO/IEC 14882:2011 (C++11 Standard)
- cppreference.com: 提供
<map>
的详细说明和示例。 - The C++ Programming Language (4th Edition) by Bjarne Stroustrup: C++ 容器权威书籍。
- Effective STL by Scott Meyers: STL 容器实用建议。
出站链接
- cppreference.com: std::map – 官方文档和示例。
- C++ Reference: std::map – 接口说明。
- GeeksforGeeks: map in C++ – 教程和代码示例。
- LearnCpp: Introduction to std::map – 初学者教程。
下一步
- 如果你想试试练习,请提交代码,我会帮你检查。
- 如果需要更深入内容(如自定义比较器、与
<multimap>
对比),或设计测验题,请告诉我! - 你也可以提出具体问题,如“如何用
<map>
实现字典?”或“<map>
的红黑树实现原理?”。
现在,你想做什么?试试练习,还是有其他需求?
发表回复