关联容器
在日常编程中，我们经常需要根据某个特定的标识来快速查找和检索数据。比如，根据学号查找学生信息、根据商品编号获取价格、或者判断某个用户名是否已经存在。这种基于键进行高效查找的需求，正是关联容器设计的初衷。
关联容器支持基于键的高效查找和检索操作。与顺序容器不同，关联容器中元素的位置不是由它们在容器中的物理位置决定，而是由元素的键值决定。这种设计使得我们能够快速定位和访问特定的元素，而不需要遍历整个容器。
关联容器的分类与特点
C++标准库提供了八种关联容器，它们在三个维度上有所不同：
- 首先是数据组织方式的差异：
set类型只存储键，而map类型存储键值对，其中键作为索引，值表示与该索引关联的数据。 - 其次是键的唯一性要求：某些容器要求键必须唯一，而另一些允许重复的键。
- 最后是元素的存储方式：有些容器按照键的顺序存储元素，而另一些则使用哈希函数来组织元素。
有序关联容器使用比较函数来维护元素的顺序，这类容器包括map（关联数组，存储键值对）、set（键集合）、multimap（允许重复键的map）和multiset（允许重复键的set）。它们的头文件分别是map和set。
无序关联容器使用哈希函数来组织元素，包括unordered_map、unordered_set、unordered_multimap和unordered_multiset。这些容器定义在unordered_map和unordered_set头文件中。
虽然大多数程序员都熟悉向量和链表这样的数据结构，但很多人可能没有使用过关联数据结构。在深入了解这些容器的技术细节之前，让我们先通过实际例子来感受它们的用法和威力。
初步认识关联容器的应用
map：构建映射关系
map容器本质上是一个键值对的集合。我们可以把它想象成一个高效的"字典"，其中每个条目都有一个唯一的"词条"（键）和对应的"释义"（值）。这种数据结构通常被称为关联数组，它像普通数组一样支持下标访问，但下标不必是整数，而可以是任何类型的键。
让我们通过一个学生成绩管理的例子来理解map的使用。假设我们需要统计每门课程的选课人数：
|map<string, size_t> courseCount; string courseName; while (cin >> courseName) { ++courseCount[courseName]; } // 输出统计结果 for (const auto &course : courseCount) { cout << course.first << "：" << course.second << "人选课" << endl; }
这个程序读取课程名称，并统计每门课程出现的次数。当我们使用courseCount[courseName]时，如果该课程名称还不在map中，下标运算符会自动创建一个新的条目，键为课程名称，值初始化为0。无论元素是否已存在，我们都可以对其值进行递增操作。
当我们遍历map时，每个元素都是一个pair对象。pair的first成员保存键（课程名称），second成员保存值（选课人数）。需要注意的是，有序容器会按照键的字典序输出结果。
set：高效的存在性检查
set容器就是键的集合，它最适合用来判断某个值是否存在。比如在文本处理中，我们可能需要过滤掉一些常见的停用词。
让我们扩展前面的例子，假设我们要统计课程选课人数，但需要排除一些无效的课程代码：
|map<string, size_t> courseCount; set<string> invalidCodes = {"TMP", "TEST", "DEBUG", "TEMP", "NULL", "EMPTY", "INVALID"}; string courseName; while (cin >> courseName) { // 只统计有效的课程代码 if (invalidCodes.find(courseName) == invalidCodes.end()) {
在这个改进的版本中，我们首先创建了一个包含无效课程代码的set。然后在统计之前，我们使用find方法检查当前的课程名称是否在无效代码集合中。find方法返回一个迭代器：如果找到了目标元素，迭代器指向该元素；如果没找到，则返回end()迭代器。只有当课程代码不在无效集合中时，我们才进行统计。
关联容器的深入理解
定义和初始化关联容器
关联容器的定义方式与顺序容器类似，但有一些重要的区别。对于map类型，我们必须同时指定键和值的类型；对于set类型，我们只需要指定键的类型。
|map<string, int> studentGrades; // 空的成绩映射 // 使用列表初始化 set<string> departments = {"计算机", "数学", "物理", "化学"}; // 初始化教师信息映射 map<string, string> teachers = { {"张教授", "计算机系"}, {"李教授", "数学系"},
初始化map时，我们需要将每个键值对包装在花括号中，形成{key, value}的格式。键是第一个元素，值是第二个元素。
标准的map和set要求键必须唯一，但有时我们需要允许重复的键。比如在图书管理系统中，同一个作者可能写了多本书，这时我们就需要使用multimap：
|vector<int> numbers; for (int i = 0; i < 10; ++i) { numbers.push_back(i % 5); // 创建包含重复值的序列 numbers.push_back(i % 5); } set<int> uniqueNumbers(numbers.cbegin(), numbers.cend
这个例子展示了set和multiset的区别：set自动去除重复元素，只保留唯一值；而multiset保留所有元素，包括重复的。
键类型的要求与自定义比较
有序关联容器对键类型有特殊要求：键类型必须定义一种比较元素的方法。默认情况下，标准库使用键类型的<运算符来比较键。这意味着键类型必须支持严格弱序关系，这种关系具有以下特性：
两个键不能同时"小于"对方；如果键A小于键B，且键B小于键C，那么键A必须小于键C；如果两个键互不小于对方，我们称它们"等价"。
在实际应用中，大多数内置类型和标准库类型都满足这些要求。但当我们使用自定义类型作为键时，可能需要提供自定义的比较函数。
假设我们有一个表示学生的类，我们希望按照学号对学生进行排序：
|struct Student { string id; string name; int grade; }; bool compareById(const Student &lhs, const Student &rhs) { return lhs.id < rhs.id; } // 使用自定义比较函数的multiset multiset<Student, decltype(compareById)*> studentSet(compareById);
这里我们定义了一个比较函数compareById，然后在定义multiset时指定了这个函数的类型。我们使用decltype来获取函数类型，并加上*表示这是一个函数指针类型。
pair类型：理解键值对
在深入学习关联容器的操作之前，我们需要了解pair类型。pair是一个模板类型，定义在utility头文件中，它可以保存两个数据成员。
|pair<string, int> studentInfo; // 保存学生姓名和年龄 pair<string, vector<int>> courseScores; // 保存课程名和成绩列表 // 使用初始化列表创建pair pair<string, string> authorBook{"鲁迅", "朝花夕拾"};
pair的两个数据成员是公开的，分别命名为first和second。我们可以直接访问这些成员：
|cout << "作者：" << authorBook.first << endl; cout << "作品：" << authorBook.second << endl;
标准库还提供了make_pair函数来创建pair对象：
|auto bookInfo = make_pair("红楼梦", 1200); // 自动推断类型
当我们需要从函数返回两个值时，pair特别有用：
|pair<bool, string> validateUser(const string &username) { if (username.empty()) { return {false, "用户名不能为空"}; } if (username.length() < 3) { return {false, "用户名长度至少3个字符"}; } return {true
关联容器的核心操作
迭代器的特殊性质
关联容器的迭代器具有一些特殊性质。对于map类型，解引用迭代器得到的是一个pair对象，其中first成员是const键，second成员是对应的值：
|map<string, int> examScores = {{"张三", 85}, {"李四", 92}, {"王五", 78}}; auto mapIter = examScores.begin(); cout << "学生：" << mapIter->first << endl; // 输出键 cout << "成绩：" << mapIter->second << endl; // 输出值
对于set类型，虽然定义了iterator和const_iterator类型，但两者都只提供只读访问。这是因为set中的键也是const的：
|set<int> numbers = {1, 3, 5, 7, 9}; set<int>::iterator setIter = numbers.begin(); if (setIter != numbers.end()) { // *setIter = 42; // 错误！set中的键是只读的 cout << *setIter << endl; // 正确：可以读取键 }
当我们遍历关联容器时，元素按照键的升序返回：
|map<string, int> scores = {{"物理", 88}, {"数学", 95}, {"化学", 82}}; for (const auto &subject : scores) { cout << subject.first << ": " << subject.second << "分" << endl; } // 输出顺序：化学、数学、物理（按字典序）
添加元素的策略
关联容器提供了多种添加元素的方法。insert成员函数是最通用的方法：
|set<string> courses; courses.insert("数据结构"); courses.insert("算法分析"); // 使用迭代器范围插入 vector<string> newCourses = {"操作系统", "数据库", "网络原理"}; courses.insert(newCourses.begin(), newCourses.end()); // 使用初始化列表插入 courses.insert({
对于map类型，我们需要插入键值对。有多种方法可以创建这样的pair对象：
|map<string, int> inventory; // 使用花括号初始化（推荐） inventory.insert({"苹果", 50}); // 使用make_pair inventory.insert(make_pair("香蕉", 30)); // 显式构造pair inventory.insert(pair<string, int>("橙子", 25)); // 使用value_type inventory.
检测插入结果
对于要求唯一键的容器，insert操作返回一个pair，告诉我们插入是否成功。返回的pair的first成员是指向具有给定键的元素的迭代器，second成员是一个布尔值，指示元素是否被插入：
|map<string, size_t> wordCount; string word = "hello"; auto result = wordCount.insert({word, 1}); if (!result.second) { // 如果插入失败（元素已存在） ++result.first->second; // 递增计数器 }
这种模式在计数程序中很常见。我们尝试插入一个新的键值对，如果键已经存在，就增加对应的计数。
多重容器的插入
对于允许重复键的容器，insert总是成功插入元素，并返回指向新元素的迭代器：
|multimap<string, string> authorBooks; authorBooks.insert({"金庸", "射雕英雄传"}); authorBooks.insert({"金庸", "神雕侠侣"}); // 总是成功插入 authorBooks.insert({"金庸", "倚天屠龙记"});
删除元素的方式
关联容器提供了几种删除元素的方法。我们可以通过迭代器删除单个元素或一个范围的元素：
|map<string, int> scores = {{"数学", 95}, {"物理", 88}, {"化学", 92}}; // 删除指定位置的元素 auto iter = scores.find("物理"); if (iter != scores.end()) { scores.erase(iter); } // 删除指定键的所有元素 size_t
对于唯一键容器，erase返回0或1，表示是否找到并删除了元素。对于多重键容器，返回值可能大于1：
|multimap<string, string> phoneBook; phoneBook.insert({"张三", "13800000001"}); phoneBook.insert({"张三", "13800000002"}); size_t removed = phoneBook.erase("张三"); cout << "删除了" << removed << "个电话号码" << endl; // 输出：删除了2个电话号码
map的下标操作
map和unordered_map支持下标操作，这是它们独有的特性。下标操作接受一个键，返回关联的值。但是要特别注意：如果键不存在，下标操作会自动插入一个新元素：
|map<string, int> studentAges; studentAges["张三"] = 20; // 插入新元素 studentAges["李四"] = 21; cout << studentAges["张三"] << endl; // 输出：20 cout << studentAges["王五"] << endl; // 输出：0（自动插入并值初始化） // 现在map中有三个元素了 cout << "学生总数：" << studentAges.
由于下标操作可能插入新元素，我们只能对非const的map使用下标操作。下标操作返回的是mapped_type对象（即值类型），而解引用map迭代器得到的是value_type对象（即pair类型）。
如果我们只想检查某个键是否存在而不想插入新元素，应该使用find或count：
|if (studentAges.find("赵六") != studentAges.end()) { cout << "找到赵六的年龄：" << studentAges["赵六"] << endl; } else { cout << "赵六不在记录中" << endl; }
查找元素的技巧
关联容器提供了多种查找元素的方法。find是最基本的查找操作，它返回指向找到元素的迭代器，如果没找到则返回end()迭代器：
|set<string> validUsers = {"admin", "user1", "user2", "guest"}; string username = "user1"; auto found = validUsers.find(username); if (found != validUsers.end()) { cout << "用户" << username << "验证通过" << endl; }
count方法返回具有给定键的元素数量。对于唯一键容器，结果只能是0或1；对于多重键容器，结果可能大于1：
|cout << validUsers.count("admin") << endl; // 输出：1 cout << validUsers.count("hacker") << endl; // 输出：0
在多重键容器中查找元素更加复杂，因为可能有多个元素具有相同的键。标准库提供了几种方法来处理这种情况。最直观的方法是结合使用find和count：
|multimap<string, string> courseTeachers; courseTeachers.insert({"数据结构", "张教授"}); courseTeachers.insert({"数据结构", "李教授"}); courseTeachers.insert({"算法分析", "王教授"}); string course = "数据结构"; auto teacherCount = courseTeachers.count(course); auto iter = courseTeachers.
更高效的方法是使用lower_bound和upper_bound：
|auto lowerIter = courseTeachers.lower_bound(course); auto upperIter = courseTeachers.upper_bound(course); for (auto iter = lowerIter; iter != upperIter; ++iter) { cout << course << "由" << iter->second << "授课" << endl; }
lower_bound返回指向第一个不小于给定键的元素的迭代器，upper_bound返回指向第一个大于给定键的元素的迭代器。这两个迭代器构成一个范围，包含所有具有给定键的元素。
最直接的方法是使用equal_range，它返回一个pair，包含lower_bound和upper_bound的结果：
|auto range = courseTeachers.equal_range(course); for (auto iter = range.first; iter != range.second; ++iter) { cout << course << "由" << iter->second << "授课" << endl; }
实际应用：文本转换程序
为了展示关联容器在实际编程中的应用，让我们构建一个文本转换程序。这个程序读取两个文件：第一个文件包含转换规则，每条规则指定一个单词及其替换内容；第二个文件包含要转换的文本。
假设我们的转换规则文件包含：
|很好 excellent 不错 good 一般 okay 较差 poor 很差 terrible
要转换的文本是：
|这次考试成绩很好 那个项目做得不错 这个方案一般 服务质量较差
程序应该输出：
|这次考试成绩excellent 那个项目做得good 这个方案okay 服务质量poor
整体程序结构
我们的解决方案包含三个函数：transformText管理整体流程，buildTransformMap构建转换映射，applyTransform执行单词转换。
|void transformText(ifstream &ruleFile, ifstream &inputFile) { auto transformMap = buildTransformMap(ruleFile); string line; while (getline(inputFile, line)) { istringstream lineStream(line); string word; bool firstWord = true; while (lineStream >> word) { if (firstWord) {
这个函数首先调用buildTransformMap构建转换规则映射，然后逐行读取输入文件。对于每一行，我们使用istringstream将其分解为单词，并对每个单词应用转换规则。
构建转换映射
|map<string, string> buildTransformMap(ifstream &ruleFile) { map<string, string> transformMap; string key, value; while (ruleFile >> key && getline(ruleFile, value)) { if (value.size() > 1) { transformMap[key] = value.substr(1); // 跳过前导空格
这个函数读取规则文件，每条规则包含一个要转换的单词和对应的替换文本。我们使用>>读取第一个单词作为键，然后用getline读取该行的剩余部分作为值。由于getline不会跳过前导空格，我们需要使用substr(1)去掉键和值之间的空格。
执行单词转换
|const string& applyTransform(const string &word, const map<string, string> &transformMap) { auto foundIter = transformMap.find(word); if (foundIter != transformMap.cend()) { return foundIter->second; } else { return word; }
转换函数接受一个单词和转换映射，返回转换后的结果。我们使用find查找单词是否在映射中存在，如果存在就返回对应的转换结果，否则返回原始单词。
文本转换引擎
无序容器的应用与优化
C++11引入的无序关联容器使用哈希函数而不是比较操作来组织元素。当键类型没有明显的排序关系，或者当维护元素顺序的代价过高时，无序容器是理想的选择。
无序容器提供与有序容器相同的操作接口，这意味着我们可以很容易地在两者之间切换：
|// 使用无序map重写词频统计程序 unordered_map<string, size_t> wordFreq; string word; while (cin >> word) { ++wordFreq[word]; } for (const auto &entry : wordFreq) { cout << entry.first << " 出现 " << entry.second << " 次" << endl; }
这个程序与使用有序map的版本几乎完全相同，唯一的区别是容器类型声明。但是输出的顺序会有所不同：有序容器按照键的字典序输出，而无序容器的输出顺序是不确定的。
虽然哈希容器在理论上具有更好的平均性能，但在实践中获得良好的性能往往需要仔细的性能测试和调优。通常，除非有明确的性能需求或键类型本身无法排序，否则使用有序容器往往更容易获得稳定的性能。
无序容器将元素组织在一系列桶中，每个桶包含零个或多个元素。容器使用哈希函数将元素映射到桶。为了访问元素，容器首先计算元素的哈希码，然后在对应的桶中搜索元素。
理想情况下，哈希函数会将每个特定值映射到唯一的桶。但是，允许不同的键映射到相同的桶。当一个桶包含多个元素时，需要顺序搜索来找到目标元素。
|unordered_map<string, int> studentIds; // 添加一些数据... // 检查容器的哈希性能 cout << "桶的数量：" << studentIds.bucket_count() << endl; cout << "负载因子：" << studentIds.load_factor() << endl; cout << "最大负载因子：" << studentIds.max_load_factor() << endl; // 如果负载因子过高，可以主动重新哈希 if (studentIds.load_factor()
对于内置类型和标准库类型（如string），标准库已经提供了哈希函数。但是对于自定义类型，我们需要提供自己的哈希函数和相等比较操作：
|struct Student { string id; string name; bool operator==(const Student &other) const { return id == other.id; } }; // 自定义哈希函数 struct StudentHash { size_t operator()(const Student &s) const {
或者，我们可以使用函数来定义哈希和相等操作：
|size_t studentHasher(const Student &s) { return hash<string>()(s.id); } bool studentEqual(const Student &lhs, const Student &rhs) { return lhs.id == rhs.id; } unordered_multiset<Student, decltype(studentHasher)*, decltype
通过理解和掌握关联容器，我们能够编写更加高效和优雅的程序。这些容器不仅提供了快速的查找和检索能力，还通过其丰富的接口支持各种复杂的数据操作需求。在实际开发中，选择合适的关联容器类型往往能够显著提升程序的性能和可维护性。
练习
练习 1：map的基本使用
编写一个程序，使用map存储学生的姓名和成绩，然后实现查找和显示所有学生的功能。
|#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, int> scores; // 姓名 -> 成绩 // 添加学生成绩 scores["张三"] = 85; scores["李四"] = 90; scores["王五"] = 78;
练习 2：multimap的使用
编写一个程序，使用multimap存储学生的姓名和课程，一个学生可以选择多门课程。
|#include <iostream> #include <map> #include <string> using namespace std; int main() { multimap<string, string> courses; // 姓名 -> 课程 // 添加选课信息 courses.insert({"张三", "数学"}); courses.insert({"张三", "英语"}); courses.insert({
练习 3：set的使用
编写一个程序，使用set存储一组不重复的数字，然后检查某个数字是否存在。
|#include <iostream> #include <set> using namespace std; int main() { set<int> numbers; // 添加数字（set自动去重） numbers.insert(10); numbers.insert(20); numbers.insert(30); numbers.insert(20); // 重复，不会被添加 numbers.
练习 4：统计单词出现次数
编写一个程序，统计一段文本中每个单词出现的次数，并输出统计结果。
|#include <iostream> #include <map> #include <string> #include <sstream> using namespace std; int main() { string text = "hello world hello cpp world cpp"; map<string, int> wordCount; // 将文本分割成单词 istringstream iss(text); string word; while (iss >> word) { wordCount[word]
练习 5：综合应用——简单的电话簿
实现一个简单的电话簿程序，支持添加联系人、查找电话号码和显示所有联系人。
|#include <iostream> #include <map> #include <string> using namespace std; class PhoneBook { private: map<string, string> contacts; // 姓名 -> 电话号码 public: // 添加联系人 void addContact(const string& name, const string& phone) { contacts[name] =