引言
随着计算机科学的发展，高效的数据管理和存储已经变得越来越重要。在许多编程场景中，我们需要快速地查找和访问数据。这就是关联容器（Associative Containers）的核心功能。在C++中，关联容器为我们提供了一种高效、易于实现的数据结构，可以帮助我们更好地管理数据。在这部分中，我们将讨论关联容器的重要性和应用场景。
1.1. 关联容器的重要性
关联容器在C++中非常重要，因为它们为我们提供了一种高效的数据存储和查找方法。关联容器内部采用了特定的数据结构，如二叉搜索树、哈希表等，使得查找、插入和删除操作的时间复杂度在大多数情况下都能达到对数或常数时间。这意味着在大型数据集中，关联容器比其他线性数据结构（如数组和链表）具有更高的性能。
此外，关联容器在C++标准库中也得到了良好的支持。例如，标准库提供了几种常用的关联容器，如set、map、unordered_set和unordered_map等。这使得开发者可以方便地在自己的代码中引入关联容器，而无需从头开始实现它们。
1.2. 关联容器的应用场景
关联容器在很多场景中都有广泛的应用。以下是一些常见的关联容器使用场景：
- 索引：关联容器可以用作索引，将一个键值与另一个值关联起来。例如，在一个通讯录应用中，我们可以使用关联容器（如map）将联系人的姓名（键）关联到他们的电话号码（值）。
- 去重：在需要去除重复数据的场景下，关联容器（如set）非常有用。因为它们可以自动检测并忽略重复的数据。
- 计数：关联容器可以用来统计数据出现的次数。例如，在一个单词计数器应用中，我们可以使用关联容器（如map）将单词（键）关联到它们出现的次数（值）。
- 数据组织：当我们需要对数据进行排序或按照特定顺序访问时，关联容器（如map和set）可以帮助我们实现这一目标。
- 缓存：关联容器可以用作缓存数据结构，以减少对慢速存储（如磁盘）的访问。例如，我们可以使用关联容器（如unordered_map）将计算过的数据（键）关联到它们的结果。
关联容器概述
关联容器是一种特殊类型的容器，用于存储键值对。它们提供高效的键值查找和访问功能。关联容器根据键值对的组织方式分为两大类：有序关联容器和无序关联容器。
2.1. 关联容器的分类
2.1.1. 有序关联容器
有序关联容器中的键值对按键的顺序（通常是递增顺序）进行排列。它们通常基于平衡二叉搜索树（例如红黑树）实现。有序关联容器包括：
std::map：一个键值对的有序集合，其中每个键最多只能出现一次。std::multimap：一个键值对的有序集合，其中每个键可以出现多次。std::set：一个键的有序集合，其中每个键最多只能出现一次。实际上，std::set可以看作是一个只有键的特殊std::map。std::multiset：一个键的有序集合，其中每个键可以出现多次。
2.1.2. 无序关联容器
无序关联容器中的键值对按哈希函数的值进行排列。它们通常基于哈希表实现。无序关联容器包括：
std::unordered_map：一个键值对的无序集合，其中每个键最多只能出现一次。std::unordered_multimap：一个键值对的无序集合，其中每个键可以出现多次。std::unordered_set：一个键的无序集合，其中每个键最多只能出现一次。实际上，std::unordered_set可以看作是一个只有键的特殊std::unordered_map。std::unordered_multiset：一个键的无序集合，其中每个键可以出现多次。
2.2. 关联容器的基本特性
- 关联容器提供快速查找功能，允许根据键高效地访问值。
- 关联容器支持插入和删除操作，但不支持随机访问。
- 有序关联容器根据键的顺序存储元素，而无序关联容器根据键的哈希值存储元素。
- 关联容器中的元素（键值对）在插入时会自动按照键进行排序（有序关联容器）或分组（无序关联容器）。
无序关联容器详解
set容器
std::set 是C++标准库中的一个关联容器，用于存储唯一元素的集合。每个元素在容器中都有一个特定的键，该键也是元素本身。元素根据键的顺序（通常是递增顺序）进行排列。std::set 不允许有重复元素，即每个键在集合中最多只能出现一次。
set容器的内部实现
std::set 底层通常采用平衡二叉搜索树（例如红黑树）实现。这种数据结构能够确保插入、删除和查找操作的时间复杂度都是 O(log n)，其中 n 是树中元素的数量。
set容器的迭代器
std::set 支持双向迭代器，可以顺序遍历整个集合。通过迭代器，我们可以访问集合中的元素，但不能修改元素，因为修改可能导致元素的顺序发生改变，从而破坏集合的有序性质。
set容器的成员函数
std::set 提供了许多成员函数，包括：
insert：插入新元素到集合中。如果元素已存在，则不进行任何操作。erase：删除集合中与给定键匹配的元素。find：查找给定键在集合中的位置。如果找到，返回指向该键的迭代器；否则，返回指向集合末尾的迭代器。count：返回集合中与给定键匹配的元素数量（对于std::set，结果为 0 或 1）。lower_bound和upper_bound：返回给定键的下界和上界。size：返回集合中元素的数量。empty：检查集合是否为空。clear：清空集合中的所有元素。
set容器的性能特点
- 插入、删除和查找操作的时间复杂度为 O(log n)。
- 不支持随机访问，因此访问元素的时间复杂度为 O(log n)。
- 具有良好的内存局部性，因为元素在内存中按键的顺序存储。
std::set容器在以下应用场景中非常有用
- 唯一元素存储：当需要存储不重复的元素时，
std::set提供了一个简洁的方式来确保集合中的元素是唯一的。一旦插入了一个重复元素，std::set会自动忽略它。 - 有序数据集合：由于
std::set的底层实现是基于有序数据结构（例如红黑树），所以它天然地支持元素按键值顺序存储。这使得std::set在需要有序数据存储和高效查找的场景中非常适用。 - 区间查找：
std::set提供了lower_bound和upper_bound成员函数，使得在集合中查找给定范围的元素变得简单。这对于需要执行区间查询的应用场景非常有用，例如时间序列数据查询。 - 查找集合中是否存在某个元素：
std::set的查找操作具有 O(log n) 的时间复杂度，相对较快。当需要检查某个元素是否在集合中时，std::set可以高效地完成任务。 - 数据去重：在处理包含重复数据的数据集时，
std::set可以作为一个简单的方法来对数据进行去重。只需将数据插入到std::set中，集合中仅保留唯一元素。 - 处理关系型数据：在处理关系型数据（例如图、树等）时，
std::set可以用来存储邻接表或者子节点列表。这样可以确保关系是唯一的，并能快速地检索某个关系是否存在。
总之，std::set作为一个关联容器，主要适用于需要存储唯一、有序元素，以及在查找、插入、删除等操作中需要高效性能的场景。
set容器的代码
#include <iostream> #include <set> #include <string> int main() { // 创建一个std::set，用于存储字符串 std::set<std::string> stringSet; // 使用insert插入新元素 stringSet.insert("apple"); stringSet.insert("banana"); stringSet.insert("orange"); stringSet.insert("grape"); // 插入一个已存在的元素，集合中不会有重复的元素 stringSet.insert("apple"); // 使用erase删除元素 stringSet.erase("banana"); // 使用find查找元素 auto it = stringSet.find("orange"); if (it != stringSet.end()) { std::cout << "Found: " << *it << std::endl; } else { std::cout << "Not found." << std::endl; } // 使用count检查元素是否存在 if (stringSet.count("banana")) { std::cout << "banana exists in the set." << std::endl; } else { std::cout << "banana does not exist in the set." << std::endl; } // 使用lower_bound和upper_bound查找给定值的范围 auto lower = stringSet.lower_bound("apple"); auto upper = stringSet.upper_bound("apple"); std::cout << "Range of 'apple': [" << *lower << ", " << *upper << ")" << std::endl; // 使用size获取集合中的元素数量 std::cout << "Size of the set: " << stringSet.size() << std::endl; // 使用empty检查集合是否为空 if (stringSet.empty()) { std::cout << "The set is empty." << std::endl; } else { std::cout << "The set is not empty." << std::endl; } // 使用clear清空集合中的所有元素 stringSet.clear(); std::cout << "Size of the set after clearing: " << stringSet.size() << std::endl; return 0; }
map容器
std::map 是一个关联容器，用于存储键值对（key-value pairs），它可以通过键快速查找对应的值。std::map中的键是唯一的，且按照一定的顺序排列。默认情况下，std::map 使用 std::less 比较器对键进行排序。
map容器的内部实现
std::map 的内部通常基于平衡二叉搜索树（如红黑树）实现。这种数据结构可以保证插入、删除和查找操作具有 O(log n) 的时间复杂度。这使得std::map在处理大量数据时具有较好的性能表现。
map容器的迭代器
std::map 提供了双向迭代器，可以通过递增或递减的方式访问元素。迭代器通过键值对的引用（pair &）来访问键和值。需要注意的是，由于键是 const 类型，因此无法修改它的值。
map容器的成员函数
std::map 提供了一系列成员函数，如插入元素（insert、emplace）、删除元素（erase）、查找元素（find、count、lower_bound、upper_bound）、访问或修改值（operator[]、at）等。此外，还提供了 size、empty、clear、swap 等通用容器操作。
map容器的性能特点
std::map 的性能特点主要表现在以下几个方面：
- 查找性能：由于基于平衡二叉搜索树实现，
std::map的查找性能具有 O(log n) 的时间复杂度，适用于大规模数据的查找。 - 插入和删除性能：
std::map的插入和删除操作同样具有 O(log n) 的时间复杂度，相较于连续存储的容器如std::vector、std::deque具有更好的性能。 - 空间开销：
std::map的内存使用通常会比连续存储的容器高一些，因为需要存储树结构的额外信息。 - 有序性：
std::map内部的元素是按键排序的，因此可以直接通过迭代器访问有序元素。
总之，std::map 作为关联容器，在需要存储有序的键值对、快速查找和修改值的场景中非常适用。同时，在插入和删除操作中也具有较好的性能表现。
std::map 容器应用场景
std::map 容器在许多应用场景中都非常实用，以下是一些常见的应用场景：
- 统计频次：当需要对数据集中出现的元素及其出现次数进行统计时，可以使用
std::map。其中，键表示数据集中的元素，值表示该元素的出现次数。 - 字符串映射：
std::map可以用于将字符串映射到其他数据类型，例如，用字符串表示用户名，将其映射到用户 ID。 - 缓存系统：当需要实现一个缓存系统时，可以使用
std::map来存储键值对。此时，键表示缓存项的标识符，值表示缓存的数据。 - 索引数据结构：
std::map可用于实现类似数据库索引的数据结构，以快速查找相关数据。例如，使用人员姓名作为键，将其映射到包含详细信息的结构体对象。 - 存储有序数据：当需要存储有序的键值对数据时，可以使用
std::map。由于std::map内部的元素是根据键自动排序的，因此可以直接通过迭代器访问有序数据。 - 字典：可以使用
std::map创建字典，将单词映射到它们的解释或翻译。在这种场景中，查找操作会非常频繁，而std::map的查找性能非常适合这种需求。
这些仅仅是 std::map 容器的部分应用场景，实际上，它在许多其他领域和场景中都有广泛的应用。
std::map的代码示例
#include <iostream> #include <map> #include <string> int main() { // 创建一个空的 std::map 对象，键类型为 int，值类型为 std::string std::map<int, std::string> my_map; // 使用 insert 方法插入元素 my_map.insert({1, "one"}); my_map.insert({3, "three"}); // 使用 emplace 方法插入元素 my_map.emplace(2, "two"); // 使用 operator[] 修改或添加元素 my_map[4] = "four"; // 使用 at 方法访问值，如果键不存在，抛出 std::out_of_range 异常 try { std::cout << "Value at key 1: " << my_map.at(1) << std::endl; } catch (const std::out_of_range &e) { std::cerr << "Error: " << e.what() << std::endl; } // 使用 count 方法查找键是否存在 if (my_map.count(5)) { std::cout << "Key 5 exists" << std::endl; } else { std::cout << "Key 5 does not exist" << std::endl; } // 使用 find 方法查找键对应的迭代器 auto it = my_map.find(3); if (it != my_map.end()) { std::cout << "Found key 3, value: " << it->second << std::endl; } // 使用 lower_bound 和 upper_bound 方法查找范围内的键 auto lower = my_map.lower_bound(2); auto upper = my_map.upper_bound(3); for (auto it = lower; it != upper; ++it) { std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl; } // 使用 erase 方法删除键为 4 的元素 my_map.erase(4); // 输出 map 中的元素数量 std::cout << "Size of the map: " << my_map.size() << std::endl; // 检查 map 是否为空 if (!my_map.empty()) { std::cout << "The map is not empty" << std::endl; } // 使用 clear 方法清空 map my_map.clear(); std::cout << "Size after clearing the map: " << my_map.size() << std::endl; return 0; }
multimap容器
std::multimap 是一种关联式容器，允许多个元素具有相同的键。与 std::map 类似，它将键值对作为元素进行存储，键和值之间具有一对一的关系。不过，在 std::multimap 中，多个键可以具有相同的值。元素会根据键自动进行排序（通常是升序）。
multimap容器的内部实现
std::multimap 的内部实现通常基于平衡二叉搜索树（例如红黑树）。这种数据结构可以确保插入、删除和查找操作的时间复杂度均为 O(log n)。由于元素是按照键的顺序存储的，因此迭代器遍历时会按照键的排序顺序进行。
multimap容器的迭代器
std::multimap 支持双向迭代器（bidirectional iterator），可以进行正向和反向遍历。迭代器提供对容器元素的访问，同时支持迭代器的递增和递减操作。请注意，由于 std::multimap 的元素是常量（const），因此不能直接修改元素。要修改元素，需要先删除旧元素，然后插入新元素。
multimap容器的成员函数
std::multimap 提供了一系列成员函数，例如：
insert：向容器中插入一个新的键值对元素。erase：从容器中删除指定的元素。find：查找具有给定键的元素，并返回指向该元素的迭代器。count：返回具有给定键的元素的数量。equal_range：返回一个迭代器范围，包含具有给定键的所有元素。lower_bound和upper_bound：查找具有给定键的元素的下界和上界，返回指向这些元素的迭代器。
注意：std::multimap 不提供 operator[] 或 at 成员函数，因为可以有多个具有相同键的元素。
multimap容器的性能特点
- 查找：
std::multimap的查找操作时间复杂度为 O(log n)，因为其底层通常实现为平衡二叉搜索树（如红黑树）。 - 插入：插入元素的时间复杂度也为 O(log n)，因为新插入的元素需要保持排序顺序，而平衡二叉搜索树可以保证插入效率。
- 删除：删除元素的时间复杂度为 O(log n)，原因与插入相同，平衡二叉搜索树可以在保持排序顺序的情况下高效地删除元素。
- 内存：
std::multimap的内存开销相对较大，因为它需要为每个节点存储额外的指针以维护树结构。
multimap容器的应用场景
std::multimap 适用于以下场景：
- 当需要根据键值对的键来自动排序数据时。
- 当需要允许具有相同键的多个值时。
- 当需要在元素插入、删除和查找时保持较好的性能时。
一些典型的应用场景包括：
- 存储具有多个属性的对象集合，其中某些属性可以相同（例如，存储多个员工记录，并根据姓氏进行排序，其中多个员工可能具有相同的姓氏）。
- 构建反向索引，如搜索引擎中的单词到文档的映射。
- 存储邻接列表，用于表示具有多对多关系的图形数据结构（例如，社交网络中的用户与用户之间的关系）。
std::multimap的代码示例
#include <iostream> #include <map> #include <string> int main() { // 创建一个空的 std::multimap 对象，键类型为 int，值类型为 std::string std::multimap<int, std::string> my_multimap; // 使用 insert 方法插入一个新的键值对元素 my_multimap.insert({1, "one"}); my_multimap.insert({1, "uno"}); my_multimap.insert({2, "two"}); my_multimap.insert({3, "three"}); // 使用 erase 方法删除键为 2 的所有元素 my_multimap.erase(2); // 使用 find 方法查找具有给定键的元素，并返回指向该元素的迭代器 auto it = my_multimap.find(3); if (it != my_multimap.end()) { std::cout << "Found key 3, value: " << it->second << std::endl; } // 使用 count 方法返回具有给定键的元素的数量 std::cout << "Number of elements with key 1: " << my_multimap.count(1) << std::endl; // 使用 equal_range 方法返回一个迭代器范围，包含具有给定键的所有元素 auto range = my_multimap.equal_range(1); for (auto it = range.first; it != range.second; ++it) { std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl; } // 使用 lower_bound 和 upper_bound 方法查找具有给定键的元素的下界和上界，返回指向这些元素的迭代器 auto lower = my_multimap.lower_bound(1); auto upper = my_multimap.upper_bound(1); for (auto it = lower; it != upper; ++it) { std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl; } return 0; }
有序关联容器详解
unordered_set容器
std::unordered_set 是一个关联容器，它包含不重复的元素。元素在容器中按哈希值存储，无特定顺序。std::unordered_set 具有以下特性：
- 每个元素的值也是其关键字。
- 元素在容器中根据其关键字的哈希值进行组织，而不是关键字的顺序。
- 元素具有唯一的关键字（即，没有两个元素具有相同的关键字）。
unordered_set容器的内部实现
std::unordered_set 通常使用哈希表实现。哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构。std::unordered_set 的哈希表可能包括一系列存储桶，每个桶可以包含一个或多个元素。
unordered_set容器的迭代器
std::unordered_set 提供前向迭代器。前向迭代器支持一系列操作，包括递增（++）运算符、比较运算符（== 和 !=）和解引用运算符（* 和 ->）。迭代器可以用于遍历容器中的元素，但是遍历顺序不能保证是任何特定顺序。
unordered_set容器的成员函数
std::unordered_set 提供了一系列成员函数，用于操作和访问容器中的元素。一些常见的成员函数包括：
begin()和end()：返回指向容器中第一个元素和尾后位置的迭代器。emplace()和insert()：向容器中插入新元素。erase()：从容器中删除一个或多个元素。find()：查找具有给定关键字的元素。count()：返回具有给定关键字的元素数量。bucket_count()和bucket_size()：返回存储桶的数量和给定存储桶中的元素数量。load_factor()和max_load_factor()：返回容器的当前和最大负载因子。rehash()和reserve()：调整容器的存储桶数量以适应给定数量的元素。
这只是一些常见的成员函数，std::unordered_set 还提供了其他成员函数以满足不同的操作需求。
unordered_set容器的性能特点
std::unordered_set 作为基于哈希表的容器，具有以下性能特点：
- 平均情况下，插入、删除和查找操作的时间复杂度为 O(1)。然而，在最差情况下（哈希冲突严重时），这些操作的时间复杂度可能退化为 O(n)。
- 哈希表需要动态调整存储桶数量以保持高效性能，这可能导致在某些操作（如插入新元素）时出现额外的计算和内存开销。
std::unordered_set不保证元素的顺序，因此在有序访问元素方面性能较差。
unordered_set容器的应用场景
std::unordered_set 适用于以下场景：
- 当需要存储不重复元素集合时，例如词汇表、ID集合等。
- 当数据集中元素查找、插入和删除操作频繁且不关心元素的顺序时。由于哈希表使得这些操作在平均情况下具有 O(1) 复杂度，unordered_set 在这种场景下表现良好。
- 当需要快速检查元素是否存在于集合中时。例如，在图形算法中检查已访问过的节点，或在权限管理系统中检查用户是否具有特定权限。
注意，在以下情况下，您可能需要考虑使用其他关联容器（如 std::set 或 std::map）：
- 当需要有序集合时。
std::unordered_set不保证元素顺序，因此在有序访问元素方面性能较差。 - 当关键字和值之间存在映射关系时。在这种情况下，可以考虑使用
std::unordered_map或std::map。
std::unordered_set的代码示例
#include <iostream> #include <unordered_set> #include <string> int main() { // 创建一个空的 std::unordered_set 对象，元素类型为 std::string std::unordered_set<std::string> my_set; // 使用 emplace 方法插入新元素 my_set.emplace("apple"); // 使用 insert 方法插入新元素 my_set.insert("banana"); // 使用 begin 和 end 方法遍历容器中的所有元素 for (auto it = my_set.begin(); it != my_set.end(); ++it) { std::cout << *it << std::endl; } // 使用 erase 方法删除指定元素 my_set.erase("apple"); // 使用 find 方法查找具有给定关键字的元素 auto it = my_set.find("banana"); if (it != my_set.end()) { std::cout << "Found: " << *it << std::endl; } // 使用 count 方法返回具有给定关键字的元素数量 std::cout << "Count of banana: " << my_set.count("banana") << std::endl; // 使用 bucket_count 方法返回存储桶的数量 std::cout << "Number of buckets: " << my_set.bucket_count() << std::endl; // 使用 bucket_size 方法返回给定存储桶中的元素数量 std::cout << "Number of elements in bucket 0: " << my_set.bucket_size(0) << std::endl; // 使用 load_factor 方法返回容器的当前负载因子 std::cout << "Current load factor: " << my_set.load_factor() << std::endl; // 使用 max_load_factor 方法返回容器的最大负载因子 std::cout << "Max load factor: " << my_set.max_load_factor() << std::endl; // 使用 rehash 方法调整容器的存储桶数量 my_set.rehash(10); std::cout << "Number of buckets after rehash: " << my_set.bucket_count() << std::endl; // 使用 reserve 方法预留足够的存储空间以容纳给定数量的元素 my_set.reserve(20); std::cout << "Number of buckets after reserve: " << my_set.bucket_count() << std::endl; return 0; }
unordered_multiset容器
std::unordered_multiset 是一种无序的关联容器，存储的元素根据其键值的哈希函数进行组织。它允许多个元素具有相同的键值。它提供了快速查找、插入和删除操作。
unordered_multiset容器的内部实现
std::unordered_multiset 内部通常实现为哈希表。哈希表是一种在数组中存储桶（buckets）的数据结构，每个桶可以存储一个或多个元素。元素的位置根据其键值的哈希值确定。为了解决哈希冲突，每个桶可以存储具有相同哈希值的多个元素，这可以通过链地址法或开放地址法实现。std::unordered_multiset 会在负载因子（当前元素数量与存储桶数量之比）达到预定阈值时调整哈希表大小以保持高效性能。
unordered_multiset容器的迭代器
std::unordered_multiset 提供了前向迭代器，可用于访问容器中的元素。迭代器支持前向遍历（例如使用 ++iter），但不支持双向遍历。由于元素存储无序，迭代器访问的元素顺序不可预测。
unordered_multiset容器的成员函数
std::unordered_multiset 提供了以下常见的成员函数：
begin(),end(): 获取指向容器首元素和尾后元素的迭代器。size(): 返回容器中元素的数量。empty(): 判断容器是否为空。insert(): 向容器中插入一个或多个元素。erase(): 从容器中删除一个或多个元素。find(): 查找具有特定键值的元素。count(): 返回具有特定键值的元素数量。bucket_count(): 返回存储桶的数量。load_factor(): 返回负载因子。max_load_factor(): 获取或设置最大负载因子。rehash(): 调整存储桶的数量。
注意：这些成员函数可能具有不同的复杂度，详细信息可参考具体实现的文档。
unordered_multiset容器的性能特点
- 平均情况下，
std::unordered_multiset的查找、插入和删除操作具有常数时间复杂度（O(1)）。在最坏情况下，操作可能变为线性时间复杂度（O(n)），但这在实际应用中很少发生。 - 由于使用哈希表实现，
std::unordered_multiset可以快速查找元素。然而，哈希表的内存开销较大，因此空间效率可能不如其他容器（例如std::set）。 - 当哈希表需要调整大小时，可能会导致短暂的性能下降。通过设置合适的最大负载因子和预分配存储桶可以缓解此问题。
unordered_multiset容器的应用场景
std::unordered_multiset 适用于以下场景：
- 需要快速查找、插入和删除操作的场景，且无需对元素进行排序。
- 当允许多个元素具有相同键值时，例如统计词频时，同一个单词可能出现多次。
- 空间效率不是关键因素时，性能优先。
总之，std::unordered_multiset 适用于需要高效查询和操作的场景，同时允许元素具有相同的键值。在选择容器时，请根据具体需求权衡性能、空间和功能。
std::unordered_multiset的代码示例
#include <iostream> #include <unordered_set> #include <string> int main() { // 创建一个空的 std::unordered_multiset 对象，元素类型为 std::string std::unordered_multiset<std::string> my_multiset; // 使用 insert 方法向容器中插入一个或多个元素 my_multiset.insert("apple"); my_multiset.insert("apple"); my_multiset.insert("banana"); // 使用 begin 和 end 方法获取指向容器首元素和尾后元素的迭代器，并遍历容器 for (auto it = my_multiset.begin(); it != my_multiset.end(); ++it) { std::cout << *it << std::endl; } // 使用 size 方法返回容器中元素的数量 std::cout << "Size: " << my_multiset.size() << std::endl; // 使用 empty 方法判断容器是否为空 std::cout << "Empty? " << (my_multiset.empty() ? "Yes" : "No") << std::endl; // 使用 erase 方法从容器中删除一个或多个元素 my_multiset.erase("apple"); // 使用 find 方法查找具有特定键值的元素 auto it = my_multiset.find("banana"); if (it != my_multiset.end()) { std::cout << "Found: " << *it << std::endl; } // 使用 count 方法返回具有特定键值的元素数量 std::cout << "Count of 'apple': " << my_multiset.count("apple") << std::endl; // 使用 bucket_count 方法返回存储桶的数量 std::cout << "Number of buckets: " << my_multiset.bucket_count() << std::endl; // 使用 load_factor 方法返回负载因子 std::cout << "Load factor: " << my_multiset.load_factor() << std::endl; // 使用 max_load_factor 方法获取或设置最大负载因子 std::cout << "Max load factor: " << my_multiset.max_load_factor() << std::endl; my_multiset.max_load_factor(1.0); std::cout << "New max load factor: " << my_multiset.max_load_factor() << std::endl; // 使用 rehash 方法调整存储桶的数量 my_multiset.rehash(10); std::cout << "Number of buckets after rehash: " << my_multiset.bucket_count() << std::endl; return 0; }
unordered_map容器
unordered_map容器的定义与基本概念
std::unordered_map 是一种关联容器，它允许通过唯一键值快速访问关联的数据。该容器的底层实现为哈希表，键值根据哈希函数映射到存储桶。哈希表内的元素无序，且不会根据键值进行排序。
unordered_map容器的内部实现
std::unordered_map 的内部实现通常为开放寻址或链表法的哈希表。当发生哈希冲突时，容器会采用不同的解决策略。开放寻址法会查找哈希表中的其他位置来存储冲突的元素；链表法则会在冲突位置创建一个链表来存储具有相同哈希值的元素。当哈希表容量不足时，std::unordered_map 会自动调整存储桶的数量。
unordered_map容器的迭代器
std::unordered_map 提供了双向迭代器，可用于遍历容器中的所有元素。迭代器中包含键值对（std::pair 类型），分别用 first 和 second 成员访问键和值。请注意，容器中的元素是无序的，因此迭代器遍历的顺序是不确定的。
unordered_map容器的成员函数
std::unordered_map 提供了许多成员函数，包括插入、删除、查找、访问等操作。部分常用成员函数如下：
insert()：插入键值对到容器中。erase()：根据键值或迭代器从容器中删除元素。find()：查找具有特定键值的元素，并返回相应的迭代器。operator[]：通过键值访问或修改关联的数据，如果键不存在，会创建一个新元素。at()：类似operator[]，但当键不存在时抛出异常。size()：返回容器中的元素数量。empty()：判断容器是否为空。clear()：清空容器中的所有元素。bucket_count()：返回存储桶的数量。max_load_factor()和load_factor()：用于控制哈希表的性能参数。
请参考 C++标准库文档 以获取完整的成员函数列表。
unordered_map容器的性能特点
由于std::unordered_map基于哈希表实现，具有以下性能特点：
- 平均情况下，插入、删除和查找操作的时间复杂度为 O(1)。在理想情况下，性能非常优越。
- 最坏情况下，所有哈希冲突都聚集在一个存储桶中，时间复杂度将退化为 O(n)，n 为容器中的元素数量。
std::unordered_map的性能依赖于哈希函数的质量。一个好的哈希函数能将键值均匀地分布在存储桶中，从而降低冲突的概率。- 可调整哈希表的负载因子（load factor）以平衡空间和时间性能。增加负载因子可以减少内存使用，但可能增加冲突；降低负载因子可以提高性能，但需要更多内存。
- 与有序关联容器（如
std::map）相比，std::unordered_map通常具有更好的性能表现。但请注意，该容器中的元素是无序的。
unordered_map容器的应用场景
std::unordered_map适用于以下场景：
- 快速查找：通过键值快速查找相关数据。例如，根据用户名查找用户信息。
- 无需元素排序：如果不需要对元素进行排序，
std::unordered_map会比有序容器更高效。 - 频繁插入和删除：由于平均时间复杂度为 O(1)，插入和删除操作非常快。
- 缓存和计数：可以用于实现缓存系统（例如，LRU缓存）或统计词频等应用。
- 去重：通过键值的唯一性，可以用来去除重复元素。
总之，当需要快速访问和修改关联数据且不关心元素顺序时，std::unordered_map 是一个很好的选择。
std::unordered_map的代码示例
#include <iostream> #include <unordered_map> #include <string> int main() { // 创建一个空的 std::unordered_map 对象，键类型为 int，值类型为 std::string std::unordered_map<int, std::string> my_map; // 使用 insert 方法插入键值对到容器中 my_map.insert({1, "one"}); my_map.insert({2, "two"}); my_map.insert({3, "three"}); // 使用 erase 方法根据键值从容器中删除元素 my_map.erase(2); // 使用 find 方法查找具有特定键值的元素，并返回相应的迭代器 auto it = my_map.find(3); if (it != my_map.end()) { std::cout << "Found key 3, value: " << it->second << std::endl; } // 使用 operator[] 通过键值访问或修改关联的数据，如果键不存在，会创建一个新元素 std::cout << "Value for key 1: " << my_map[1] << std::endl; my_map[1] = "uno"; std::cout << "New value for key 1: " << my_map[1] << std::endl; // 使用 at 方法类似 operator[]，但当键不存在时抛出异常 try { std::cout << "Value for key 2: " << my_map.at(2) << std::endl; } catch (const std::out_of_range& e) { std::cout << "Key 2 not found: " << e.what() << std::endl; } // 使用 size 方法返回容器中的元素数量 std::cout << "Size: " << my_map.size() << std::endl; // 使用 empty 方法判断容器是否为空 std::cout << "Empty? " << (my_map.empty() ? "Yes" : "No") << std::endl; // 使用 clear 方法清空容器中的所有元素 my_map.clear(); std::cout << "Size after clear: " << my_map.size() << std::endl; // 使用 bucket_count 方法返回存储桶的数量 std::cout << "Number of buckets: " << my_map.bucket_count() << std::endl; // 使用 max_load_factor 和 load_factor 方法控制哈希表的性能参数 std::cout << "Max load factor: " << my_map.max_load_factor() << std::endl; std::cout << "Load factor: " << my_map.load_factor() << std::endl; return 0; }
unordered_multimap容器
std::unordered_multimap是一种无序关联容器，用于存储键值对的集合。它的主要特点是允许多个元素具有相同的键值，且存储的元素没有特定的顺序。元素的存储位置由其键值的哈希值决定。
unordered_multimap容器的内部实现
std::unordered_multimap基于哈希表实现。哈希表包含一系列存储桶，每个存储桶存储一个键值对的链表。哈希表根据键值的哈希值来确定元素存储在哪个存储桶中。与std::unordered_map不同，std::unordered_multimap允许多个键值对具有相同的键。
unordered_multimap容器的迭代器
std::unordered_multimap提供了前向迭代器，允许遍历容器中的元素。请注意，元素的遍历顺序不确定，因为std::unordered_multimap是无序的。
unordered_multimap容器的成员函数
std::unordered_multimap提供了一系列成员函数，包括：
- 插入元素：
insert、emplace等。 - 删除元素：
erase、clear等。 - 查找元素：
find、count、equal_range等。 - 获取迭代器：
begin、end、cbegin、cend等。 - 哈希表操作：
bucket_count、bucket_size、bucket、max_bucket_count、load_factor、max_load_factor、rehash、reserve等。
这些成员函数可用于操作容器中的元素、查询容器状态以及调整哈希表的性能。
unordered_multimap容器的性能特点
- 查找、插入和删除操作的平均时间复杂度为O(1)，最坏情况下为O(n)。这取决于容器内的哈希函数和哈希冲突的处理。
- 由于
std::unordered_multimap使用哈希表实现，因此内存使用可能较高，特别是当存储桶数量很大时。 - 与有序关联容器（如
std::multimap）相比，无序关联容器通常具有较高的性能，但是无序关联容器不提供任何顺序保证。 - 通过调整哈希表的装载因子和存储桶数量，可以在一定程度上调整性能。装载因子较低时，哈希冲突减少，但内存使用较高；装载因子较高时，哈希冲突增多，但内存使用较低。
unordered_multimap容器的应用场景
- 当需要存储具有相同键的多个键值对时，可以使用
std::unordered_multimap。 - 当对元素的存储顺序没有特定要求，但希望在查找、插入和删除操作上获得较高性能时，
std::unordered_multimap是一个合适的选择。 - 如果需要将数据分组（具有相同键的元素属于同一组），
std::unordered_multimap可以很好地满足这一需求。 - 应用场景示例：缓存系统、多值字典、将相同属性的对象进行分组等。
std::unordered_map的代码示例
#include <iostream> #include <unordered_map> #include <string> int main() { // 创建一个空的 std::unordered_multimap 对象，键类型为 int，值类型为 std::string std::unordered_multimap<int, std::string> my_multimap; // 使用 insert 和 emplace 方法插入键值对到容器中 my_multimap.insert({1, "one"}); my_multimap.insert({1, "uno"}); my_multimap.emplace(2, "two"); // 使用 erase 方法根据键值从容器中删除元素 my_multimap.erase(2); // 使用 find 方法查找具有特定键值的元素，并返回相应的迭代器 auto it = my_multimap.find(1); if (it != my_multimap.end()) { std::cout << "Found key 1, value: " << it->second << std::endl; } // 使用 count 方法返回具有特定键值的元素数量 std::cout << "Count of key 1: " << my_multimap.count(1) << std::endl; // 使用 equal_range 方法返回一个迭代器范围，包含具有特定键值的所有元素 auto range = my_multimap.equal_range(1); for (auto r_it = range.first; r_it != range.second; ++r_it) { std::cout << "Key 1, value: " << r_it->second << std::endl; } // 使用 begin、end、cbegin 和 cend 方法获取迭代器 for (auto cit = my_multimap.cbegin(); cit != my_multimap.cend(); ++cit) { std::cout << "Key: " << cit->first << ", value: " << cit->second << std::endl; } // 使用 clear 方法清空容器中的所有元素 my_multimap.clear(); // 使用 bucket_count、bucket_size、bucket 和 max_bucket_count 方法进行哈希表操作 std::cout << "Number of buckets: " << my_multimap.bucket_count() << std::endl; std::cout << "Max bucket count: " << my_multimap.max_bucket_count() << std::endl; std::cout << "Bucket for key 1: " << my_multimap.bucket(1) << std::endl; // 使用 load_factor 和 max_load_factor 方法控制哈希表的性能参数 std::cout << "Load factor: " << my_multimap.load_factor() << std::endl; std::cout << "Max load factor: " << my_multimap.max_load_factor() << std::endl; // 使用 rehash 和 reserve 方法调整哈希表的存储桶数量 my_multimap.reserve(10); my_multimap.rehash(20); std::cout << "Number of buckets after rehash: " << my_multimap.bucket_count() << std::endl; return 0; }
关联容器的性能优化
自定义比较函数
关联容器使用比较函数来确定元素的顺序或者哈希值。自定义比较函数可以提高容器的性能，同时满足特定的需求。以下是一些关于自定义比较函数的提示：
- 有序关联容器（如
std::set、std::map、std::multiset和std::multimap）通常使用比较函数（例如std::less或std::greater）来确定元素的顺序。在创建这些容器时，可以传递自定义的比较函数，以便根据特定需求对元素进行排序。
例如：
struct CustomCompare { bool operator()(const int &a, const int &b) const { // 自定义比较逻辑 return a % 10 < b % 10; } }; std::set<int, CustomCompare> customSet;
- 无序关联容器（如
std::unordered_set、std::unordered_map、std::unordered_multiset和std::unordered_multimap）使用哈希函数和键的相等性比较函数来确定元素的位置和是否相等。在创建这些容器时，可以传递自定义的哈希函数和相等性比较函数，以便根据特定需求对元素进行哈希和比较。
例如：
struct CustomHash { std::size_t operator()(const int &key) const { // 自定义哈希逻辑 return key % 10; } }; struct CustomEqual { bool operator()(const int &a, const int &b) const { // 自定义相等性比较逻辑 return a % 10 == b % 10; } }; std::unordered_set<int, CustomHash, CustomEqual> customUnorderedSet;
在自定义比较函数时，请注意以下几点：
- 自定义比较函数应该是高效的，避免产生不必要的开销。
- 有序关联容器的比较函数必须满足严格弱序（strict weak ordering）的要求，即具有反身性、非对称性和传递性。
- 无序关联容器的哈希函数应该能够尽量减少哈希冲突，从而提高容器的性能。同时，相等性比较函数应当满足自反性、对称性和传递性。
通过合理地自定义比较函数，可以提高关联容器的性能，同时满足特定场景的需求。
自定义哈希函数
在使用无序关联容器（例如std::unordered_set、std::unordered_map、std::unordered_multiset和std::unordered_multimap）时，自定义哈希函数可以根据特定的应用场景提高性能。以下是关于自定义哈希函数的一些建议：
- 保持哈希函数简单：一个好的哈希函数应该简单且快速。不需要使用复杂的算法，简单的算法通常能提供足够的性能。
- 尽量避免哈希冲突：一个优秀的哈希函数应尽量减少哈希冲突，这样容器才能更有效地执行插入、查找和删除操作。
- 保持分布均匀：哈希函数应该将数据均匀地分布在整个哈希表中。这有助于避免哈希表的某些部分过于拥挤，从而提高容器的性能。
以下是一个自定义哈希函数的示例：
struct CustomHash { std::size_t operator()(const std::string &key) const { std::size_t hashValue = 0; // 逐个字符累加其ASCII值 for (const char &c : key) { hashValue += static_cast<std::size_t>(c); } // 返回累加后的ASCII值作为哈希值 return hashValue; } }; std::unordered_set<std::string, CustomHash> customUnorderedSet;
需要注意的是，自定义哈希函数可能会受到应用场景的影响，因此在实际应用中，需要根据具体情况选择或设计合适的哈希函数。在某些场景下，标准库提供的哈希函数（例如std::hash）可能已经足够高效。在这种情况下，可以不需要自定义哈希函数。
使用emplace操作提高效率
使用emplace操作是提高关联容器性能的一个有效方法。emplace操作是C++11引入的，用于在容器中直接构造元素，而不是先构造一个临时对象，然后再将其插入容器。
与insert操作相比，emplace操作在插入新元素时可以减少一次对象的构造和销毁。这意味着，如果对象的构造和析构开销较大，使用emplace操作可以显著提高性能。
下面是一个使用emplace操作的示例：
#include <set> #include <string> int main() { std::set<std::string> mySet; // 使用insert操作插入元素 std::string value1 = "example"; mySet.insert(value1); // 使用emplace操作插入元素 mySet.emplace("example"); return 0; }
在上述代码中，使用insert操作插入元素时，首先创建了一个std::string对象value1，然后将其插入到mySet中。相反，使用emplace操作时，直接在mySet中构造了一个std::string对象，从而避免了临时对象的创建。
这种性能优势在关联容器（如std::map、std::multimap、std::unordered_map和std::unordered_multimap）中更加明显，因为这些容器中的元素通常包含键值对。emplace操作可以减少这些键值对的复制次数，从而提高插入速度。在使用emplace操作时，传递给它的参数应与容器中元素的构造函数参数相匹配。
有效管理容器容量和负载因子
管理容器的容量和负载因子对于关联容器（尤其是无序关联容器）的性能非常重要。容量是指容器能够容纳的元素的数量，而负载因子是指容器中当前元素数量与容器容量的比值。当负载因子过高时，容器中的元素可能会变得过于密集，从而导致性能下降。
容量管理
为了提高性能，可以在插入元素之前预先分配足够的容量。这可以通过使用reserve成员函数来实现。这样可以避免在插入过程中多次重新分配内存和重新哈希元素。例如：
#include <unordered_set> int main() { std::unordered_set<int> mySet; // 预先分配足够的容量 mySet.reserve(100); // 插入元素 for (int i = 0; i < 100; ++i) { mySet.insert(i); } return 0; }
负载因子管理
管理负载因子对于无序关联容器（如std::unordered_set、std::unordered_map、std::unordered_multiset和std::unordered_multimap）的性能至关重要。在插入元素时，如果负载因子超过了容器的最大负载因子（默认值通常为1.0），容器会自动增加容量并重新哈希元素。
可以通过以下方式管理负载因子：
- 使用
max_load_factor成员函数设置容器的最大负载因子。这样可以根据需要调整容器在何时重新分配内存和重新哈希的时机。较低的最大负载因子值可能会导致更频繁的内存分配和哈希，但查找性能可能会更好。较高的最大负载因子值可能导致查找性能下降，但内存分配和哈希操作的频率较低。 - 使用
rehash或reserve成员函数手动触发重新哈希操作。当知道容器中将要插入大量元素时，可以提前调用rehash或reserve为容器分配足够的内存，从而避免在插入过程中多次触发重新哈希操作。
关联容器的实际应用案例
频繁查询的字典管理
在实际应用中，关联容器经常用于管理字典，尤其是在需要频繁查询的场景。例如，一个程序可能需要将单词与其定义或翻译相关联。在这种情况下，关联容器提供了高效的查找、插入和删除操作，可以大大提高程序的性能。
以下是一个简单的示例，展示了如何使用std::map容器实现一个英汉词典：
#include <iostream> #include <map> #include <string> int main() { // 使用std::map容器存储英汉词典 std::map<std::string, std::string> dictionary; // 添加一些单词及其对应的翻译 dictionary["hello"] = "你好"; dictionary["world"] = "世界"; dictionary["computer"] = "计算机"; dictionary["apple"] = "苹果"; // 查询单词 std::string word = "hello"; auto it = dictionary.find(word); if (it != dictionary.end()) { std::cout << "The Chinese translation of '" << word << "' is: " << it->second << std::endl; } else { std::cout << "The word '" << word << "' is not in the dictionary." << std::endl; } return 0; }
在这个例子中，std::map容器以英文单词作为键，以对应的中文翻译作为值。当需要查找某个单词的翻译时，std::map可以在对数时间内找到对应的值。这使得关联容器成为存储和管理字典的理想选择。如果查询性能非常关键，可以考虑使用std::unordered_map来进一步提高查找速度。
实际应用案例还包括数据库缓存、配置文件管理、符号表、网络路由表等。关联容器在这些场景中可以提供高效的数据管理和查询操作。
任务调度系统的优先级管理
在实际应用中，关联容器也可以用于实现任务调度系统的优先级管理。任务调度系统通常需要在不同优先级的任务之间进行调度，以便优先执行重要任务。在这种情况下，可以使用std::multimap或std::multiset容器根据任务的优先级对任务进行排序。
以下是一个简单的示例，展示了如何使用std::multimap容器实现一个基于优先级的任务调度系统：
#include <iostream> #include <map> #include <string> // 任务结构体 struct Task { int id; std::string description; }; int main() { // 使用std::multimap容器根据优先级管理任务 std::multimap<int, Task> taskScheduler; // 添加任务及其优先级（较低的整数值表示较高的优先级） taskScheduler.insert({2, {1, "Send an email to the manager"}}); taskScheduler.insert({1, {2, "Fix the critical bug"}}); taskScheduler.insert({3, {3, "Write a report"}}); taskScheduler.insert({2, {4, "Update the documentation"}}); // 按优先级顺序执行任务 std::cout << "Executing tasks in priority order:" << std::endl; for (const auto& taskItem : taskScheduler) { const Task& task = taskItem.second; std::cout << "Task ID: " << task.id << ", Description: " << task.description << std::endl; } return 0; }
在这个例子中，std::multimap容器将任务的优先级作为键，任务结构体作为值。通过遍历std::multimap容器，可以按照优先级顺序执行任务。std::multimap容器能够处理具有相同优先级的任务，将它们一起存储。
类似地，可以使用std::multiset容器实现基于优先级的任务调度系统。关键在于为std::multiset提供一个自定义的比较函数，以便根据任务的优先级对任务进行排序。
任务调度系统的实际应用案例包括操作系统进程调度、网络数据包调度、消息队列调度等。关联容器在这些场景中可以有效地对任务进行优先级管理和执行。
图结构数据的邻接表表示
关联容器也可用于表示图结构数据的邻接表。邻接表是一种用于表示有向图或无向图中顶点之间的边的数据结构。在邻接表中，每个顶点都与一个包含其邻居顶点的列表相关联。这种数据结构可以方便地查询顶点之间的连接关系，从而进行图遍历和其他图操作。
下面是一个使用std::unordered_map表示邻接表的例子：
#include <iostream> #include <unordered_map> #include <vector> #include <string> int main() { // 使用std::unordered_map容器表示图的邻接表 std::unordered_map<std::string, std::vector<std::string>> adjacencyList; // 添加边 adjacencyList["A"] = {"B", "C"}; adjacencyList["B"] = {"A", "D", "E"}; adjacencyList["C"] = {"A", "F"}; adjacencyList["D"] = {"B"}; adjacencyList["E"] = {"B", "F"}; adjacencyList["F"] = {"C", "E"}; // 查询顶点的邻居 std::string vertex = "B"; std::vector<std::string> neighbors = adjacencyList[vertex]; std::cout << "Neighbors of vertex " << vertex << ": "; for (const auto& neighbor : neighbors) { std::cout << neighbor << " "; } std::cout << std::endl; return 0; }
在这个例子中，std::unordered_map容器的键是图中的顶点，值是与该顶点相邻的顶点列表。通过查询std::unordered_map容器，可以轻松获取顶点的邻居。
如果希望对顶点进行排序，可以使用std::map容器。此外，对于表示边权重的加权图，可以将std::vector替换为std::vector>（或其他权重类型），以便存储顶点的邻居及其对应的权重。
关联容器可以方便地表示图结构数据的邻接表，并支持高效地执行图遍历、查找邻居、添加或删除边等操作。
总结
关联容器在C++标准库中提供了一组非常强大且实用的数据结构，用于管理具有键值关系的数据。在实际项目中，了解并掌握关联容器的基本操作和原理，将对我们解决复杂问题和优化性能起到至关重要的作用。以下是关联容器的几个关键要点：
- 掌握关联容器的基本操作和原理：为了在实际项目中有效地应用关联容器，我们需要熟练掌握它们的基本操作，例如插入、删除、查找和遍历。同时，了解其内部实现原理和性能特点，有助于我们选择适当的关联容器，从而满足应用场景的需求。
- 熟悉关联容器在实际项目中的应用：关联容器具有广泛的应用价值，如频繁查询的字典管理、任务调度系统的优先级管理以及图结构数据的邻接表表示等。在实际项目中灵活运用关联容器，可以帮助我们更有效地解决问题，提升代码质量。
- 提高数据结构操作的效率：通过选择合适的关联容器和使用合适的操作，可以大大提高数据结构操作的效率。例如，使用emplace操作以提高插入效率，管理容器容量和负载因子以优化容器性能，以及为关联容器定制比较函数和哈希函数以获得更好的性能。这些技巧在实际项目中都能为我们带来显著的性能优化。
总之，关联容器是C++标准库中非常实用的一组数据结构。通过掌握它们的基本操作和原理、熟悉它们在实际项目中的应用，以及学会提高数据结构操作的效率，我们将能够充分利用关联容器的强大功能，有效地解决实际项目中的问题。
