map

std::map 是 C++ 标准库里的有序关联容器，用来存储“键值对”数据。它的核心特点是：通过键快速查找元素，并且内部会按照键的顺序自动排序。

和 vector、list 这类顺序容器相比，map 更适合“根据关键字查找记录”的场景，例如学生成绩表、配置表、词频统计、ID 到对象的映射等。和 unordered_map 相比，map 保证元素始终有序，因此还能做范围查询、前驱后继查找等操作。

头文件与基本特征

使用 map 时，需要包含头文件：

#include <map>

map 的常见特征如下：

特征	说明
元素类型	std::pair<const Key, T>
键是否重复	默认不允许重复键
是否有序	是，按键比较结果排序
底层结构	通常基于平衡二叉搜索树实现
查找复杂度	平均和最坏通常都是 O(log n)

其中 Key 是键类型，T 是映射到的值类型。元素在容器中不是单独存放 T，而是以“键-值对”的形式存在。

基本用法

最常见的声明方式如下：

#include <map>
#include <string>

int main() {
	std::map<std::string, int> scores;

	scores["Alice"] = 95;
	scores["Bob"] = 88;
	scores["Cathy"] = 91;

	return 0;
}

这里的 operator[] 会按键访问元素。如果键不存在，它会先插入一个默认值，再返回对应值的引用。

例如：

std::map<std::string, int> scores;

scores["Tom"] = 100;
int value = scores["Jerry"];

执行后，Jerry 这个键会被插入到 map 中，对应值是 0。

遍历 map

map 支持迭代器遍历，遍历时元素会按照键的顺序依次输出。

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

int main() {
	std::map<std::string, int> scores;
	scores["Bob"] = 88;
	scores["Alice"] = 95;
	scores["Cathy"] = 91;

	for (std::map<std::string, int>::iterator it = scores.begin(); it != scores.end(); ++it) {
		std::cout << it->first << " = " << it->second << '\n';
	}

	return 0;
}

输出顺序会按键排序，而不是按插入顺序。对于字符串键，默认使用字典序排序。

常用成员函数

map 提供了很多常用操作接口：

函数	作用
begin()	返回第一个元素迭代器
end()	返回尾后迭代器
empty()	判断是否为空
size()	返回元素个数
clear()	清空容器
insert()	插入元素
erase()	删除元素
find()	查找指定键
count()	统计指定键出现次数
lower_bound()	找到第一个不小于目标键的位置
upper_bound()	找到第一个大于目标键的位置
equal_range()	同时返回上下界
swap()	交换两个容器内容

插入元素

map 的插入通常使用 insert()，传入一个 pair：

#include <map>
#include <string>

int main() {
	std::map<std::string, int> scores;

	scores.insert(std::make_pair(std::string("Alice"), 95));
	scores.insert(std::make_pair(std::string("Bob"), 88));

	return 0;
}

如果插入的键已经存在，insert() 不会覆盖原有值，而是插入失败。

可以通过返回值判断是否插入成功：

std::pair<std::map<std::string, int>::iterator, bool> result =
	scores.insert(std::make_pair(std::string("Alice"), 100));

if (!result.second) {
	// 键已存在
}

查找元素

查找元素时通常优先使用 find()：

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

int main() {
	std::map<std::string, int> scores;
	scores["Alice"] = 95;

	std::map<std::string, int>::iterator it = scores.find("Alice");
	if (it != scores.end()) {
		std::cout << it->first << " = " << it->second << '\n';
	}

	return 0;
}

find() 返回指向目标键的迭代器，找不到时返回 end()。

count() 在 map 中通常只会返回 0 或 1，因为普通 map 不允许重复键：

if (scores.count("Alice") > 0) {
	// 键存在
}

删除元素

map 支持按键、按迭代器、按区间删除元素：

#include <map>
#include <string>

int main() {
	std::map<std::string, int> scores;
	scores["Alice"] = 95;
	scores["Bob"] = 88;

	scores.erase("Bob");

	return 0;
}

如果要删除某个范围内的元素，可以结合迭代器使用：

std::map<std::string, int>::iterator it = scores.begin();
scores.erase(it, scores.end());

范围查找

由于 map 是有序的，所以可以进行范围相关操作。

#include <map>
#include <string>

int main() {
	std::map<int, std::string> data;
	data[10] = "ten";
	data[20] = "twenty";
	data[30] = "thirty";

	std::map<int, std::string>::iterator it1 = data.lower_bound(15);
	std::map<int, std::string>::iterator it2 = data.upper_bound(20);

	return 0;
}

含义如下：

函数	含义
lower_bound(k)	第一个键不小于 k 的元素
upper_bound(k)	第一个键大于 k 的元素
equal_range(k)	同时返回 lower_bound 和 upper_bound

这些接口在区间统计、前缀查找、排序后的定位中很有用。

自定义排序

map 的排序规则由比较器决定。默认使用 std::less<Key>，也就是升序排序。你也可以传入自定义比较器，让键按别的规则排序。

#include <map>
#include <string>

struct Greater {
	bool operator()(int lhs, int rhs) const {
		return lhs > rhs;
	}
};

int main() {
	std::map<int, std::string, Greater> data;
	data[1] = "one";
	data[3] = "three";
	data[2] = "two";

	return 0;
}

比较器必须满足严格弱序关系，否则容器行为可能异常。

典型场景

map 在下面这些场景里很常见：

1. 字符串到数值的映射，例如统计单词出现次数。
2. 学号到学生信息的映射，例如成绩管理系统。
3. 配置项存储，例如根据名字快速读取参数。
4. 有序去重，例如按某个关键字排序并保证唯一性。

词频统计示例：

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

int main() {
	std::map<std::string, int> counter;
	std::string word;

	while (std::cin >> word) {
		++counter[word];
	}

	for (std::map<std::string, int>::iterator it = counter.begin(); it != counter.end(); ++it) {
		std::cout << it->first << " : " << it->second << '\n';
	}

	return 0;
}

使用注意

1. operator[] 会在键不存在时自动插入默认值，读取前要确认这是不是你想要的行为。
2. 如果只想查询而不想插入，优先使用 find()。
3. map 默认按键排序，不会保留插入顺序。
4. 元素类型的键部分是 const，因此不能直接修改元素的键。
5. 由于是有序容器，map 的查找性能通常比线性容器更好，但插入和删除也比简单数组更重。

小结

std::map 适合处理“键唯一、需要按键查找、还要求有序”的数据。它提供了稳定的有序遍历、范围查找和较清晰的接口模型，是 C++98/03 里最重要的关联容器之一。只要掌握 insert、find、erase、operator[] 和几个范围查询函数，基本就能覆盖日常开发里的大多数映射需求。