C / C++ / 系统课时
自定义类型怎样作为 map 的键
自定义类型怎样作为 map 的键
std::map 必须知道任意两个键谁应排在前面。内置整数和字符串已经有默认顺序,自定义结构体则需要提供比较规则。真正重要的不是“写出一个能编译的比较函数”,而是让它满足严格弱序,否则查找和插入结果都可能失去可靠性。
学习目标
- 为自定义类型定义可供
map使用的排序规则 - 理解严格弱序与“键是否相同”的关系
- 避免会破坏关联容器有序性的比较器写法
map 依赖比较器组织键
std::map<Key, T> 默认使用 std::less<Key>。对自定义类型而言,最常见的做法有两种:给类型定义 operator<,或者把独立比较器作为 map 的第三个模板参数。
当排序规则只服务于某个容器,独立比较器通常更清晰,因为它不会给类型强加“唯一的天然顺序”。例如用户键可以按“部门编号,再按用户编号”排序。
用组合字段定义稳定顺序
下面的完整示例使用 std::tie 按两个字段进行字典序比较:
#include <iostream>
#include <map>
#include <string>
#include <tuple>
struct UserKey {
int department;
int id;
};
struct UserKeyLess {
bool operator()(const UserKey& a, const UserKey& b) const {
// 先比较 department,相同后再比较 id,形成稳定的字典序。
return std::tie(a.department, a.id)
< std::tie(b.department, b.id);
}
};
int main() {
std::map<UserKey, std::string, UserKeyLess> users;
users[{2, 10}] = "Bob";
users[{1, 20}] = "Alice";
users[{1, 10}] = "Carol";
for (const auto& [key, name] : users) {
std::cout << key.department << '-'
<< key.id << ": " << name << '\n';
}
}预期输出:
1-10: Carol
1-20: Alice
2-10: Bob这里的键顺序完全由 UserKeyLess 决定。map 不要求 UserKey 提供 operator==,因为它判断两个键“等价”的方式是:comp(a, b) 和 comp(b, a) 都为 false。
严格弱序意味着什么
比较器必须像一个一致的“小于关系”。最重要的约束包括:任何对象都不能小于自己;若 a < b,就不能同时 b < a;若 a < b 且 b < c,则必须有 a < c。由比较器产生的“等价关系”也必须保持一致。
因此,不要写依赖随机数、当前时间或频繁变化外部状态的比较器,也不要只比较一个不足以区分业务键的字段。例如只比较 department,会让同部门的不同 id 被 map 视为等价键,后续插入可能覆盖已有值。
选择 operator< 还是自定义比较器
如果类型在整个程序里确实只有一种自然顺序,可以定义 operator<,让 std::map<UserKey, T> 直接工作。若同一种类型可能有多种排序方式,例如按编号、按名称或按时间排序,则更适合为不同容器提供不同比较器。
比较规则一旦确定,就应覆盖构成键身份的全部必要字段,并保持稳定、可传递。这样 map 的插入、查找、lower_bound 和有序遍历才能建立在同一套一致规则上。