C++STL（五）无序关联容器

目录

1、std::unordered_set

构造函数

迭代器

迭代器失效

容量操作

修改

查找

桶操作

哈希策略

code示例

2、std::unordered_map

构造函数

元素访问

容量操作

修改

查找

桶、哈希操作

code示例

3、std::unordered_multiset

4、unordered_multimap

---

1、std::unordered_set

C++ 标准模板库（STL）中的一个无序关联容器，用于存储唯一元素。它基于哈希表实现，支持快速的插入、删除和查找操作。既然底层是哈希表那么常见的哈希问题 哈希函数：将元素映射到哈希表的桶（bucket）中。冲突解决：使用链地址法（Separate Chaining）或开放地址法（Open Addressing）解决哈希冲突。动态扩容：当元素数量超过负载因子（load factor）时，哈希表会自动扩容。

构造函数 unordered_set()默认构造函数，创建一个空的 unordered_setunordered_set(const unordered_set& other)拷贝构造函数unordered_set(initializer_list<T> init)使用初始化列表创建 unordered_set 迭代器

begin(), end(): 返回指向第一个元素和最后一个元素之后位置的迭代器。

cbegin(), cend(): 返回常量迭代器

迭代器失效

erase：删除元素时指向被删除元素的迭代器失效。rehash：重新哈希时，所有迭代器失效。

insert：插入元素不会使其他迭代器失效。

容量操作

empty(): 判空。size(): 求元素数量。max_size(): 返回 unordered_set 可以容纳的最大元素数量

修改

clear(): 清除 unordered_set 中的所有元素。    insert(const T& value): 插入元素。

erase(iterator pos): 删除指定位置pos处元素。erase(const T& value): 删除值为value的元素

swap(unordered_set& other): 交换两个 unordered_set 的内容

查找 find(const T& value): 返回指向值为 value 的元素的迭代器，如果未找到则返回 end()count(const T& value): 返回值为 value 的元素的数量（对于 unordered_set，结果为 0 或 1）equal_range(const T& value): 返回一个包含 lower_bound 和 upper_bound 的 pair 桶操作

bucket_count(): 返回桶的数量。    bucket_size(size_type n): 返回第 n 个桶中的元素数量。

bucket(const T& value): 返回值为 value 的元素所在的桶的索引。

哈希策略

max_load_factor(): 返回最大负载因子。rehash(size_type n): 设置桶的数量为至少 n。

reserve(size_type n): 预留至少 n 个元素的存储空间； load_factor(): 返回当前负载因子

code示例 #include <iostream> #include <unordered_set> int main() { //构造 std::unordered_set<int> us1; // 空 unordered_set std::unordered_set<int> us = {1, 2, 3, 4, 5}; // 使用初始化列表创建 unordered_set //元素访问 for (int i : us) { std::cout << i << " "; // 输出: 5 4 3 2 1（顺序不确定） } std::cout << std::endl; for (auto it = us.begin(); it != us.end(); ++it) { std::cout << *it << " "; // 输出: 5 4 3 2 1（顺序不确定） } //容量 std::cout << "us.empty(): " << us.empty() << std::endl; // 输出: 0 (false) std::cout << "us.size(): " << us.size() << std::endl; // 输出: 5 std::cout << "us.max_size(): " << us.max_size() << std::endl; // 输出: 一个很大的数 //修改 us.insert(6); // 插入新元素 us.emplace(7); us.erase(2); // 删除值为 2 的元素 (7 6 5 4 3 1) //us.clear(); 清空集合 //查找 auto it = us.find(3); if (it != us.end()) { std::cout << "Found: " << *it << std::endl; // 输出: Found: 3 } std::cout << "us.count(3): " << us.count(3) << std::endl; // 输出: 1 std::cout << "us.count(6): " << us.count(6) << std::endl; // 输出: 0 auto range = us.equal_range(3); if (range.first != range.second) { std::cout << "Equal range: " << *range.first << std::endl; // 输出: 3 } else { std::cout << "No range found." << std::endl; } //桶操作 std::cout << "Bucket count: " << us.bucket_count() << std::endl; // 输出: 桶的数量 std::cout << "Bucket size for bucket 0: " << us.bucket_size(0) << std::endl; // 输出: 第 0 个桶中的元素数量 std::cout << "Bucket for value 3: " << us.bucket(3) << std::endl; // 输出: 值为 3 的元素所在的桶的索引 //哈希操作 std::cout << "Load factor: " << us.load_factor() << std::endl; // 输出: 当前负载因子 std::cout << "Max load factor: " << us.max_load_factor() << std::endl; // 输出: 最大负载因子 us.rehash(10); // 设置桶的数量为至少 10 us.reserve(20); // 预留至少 20 个元素的存储空间 return 0; } 2、std::unordered_map

std::unordered_map是 C++ 标准模板库（STL）中的一个无序关联容器，用于存储键值对（key-value pairs）。它基于哈希表实现，支持快速的插入、删除和查找操作，同样具有哈希的一些特性

构造函数 unordered_map():   默认构造函数，创建一个空的 unordered_mapunordered_map(const unordered_map& other):   拷贝构造函数unordered_map(initializer_list<std::pair<const Key, T>> init):   使用初始化列表创建 unordered_map 元素访问

operator[](const Key& key):  返回键为 key 的值的引用，如果键不存在则插入一个默认值

at(const Key& key):  返回键为 key 的值的引用，如果键不存在则抛出 std::out_of_range 异常

容量操作

empty(): 判空。size(): 求键值对数量。max_size(): 返回可以容纳的最大键值对数量

修改     clear(): 清除 unordered_map 中的所有键值对。    insert(const std::pair<const Key, T>& value): 插入键值对。    erase(iterator pos): 删除指定位置 pos 处的键值对。    erase(const Key& key): 删除键为 key 的键值对。    swap(unordered_map& other): 交换两个 unordered_map 的内容。 查找 find(const Key& key): 返回指向键为 key 的键值对的迭代器，如果未找到则返回 end()count(const Key& key): 返回键为 key 的键值对的数量（对于 unordered_map结果为 0 或 1）equal_range(const Key& key): 返回一个包含 lower_bound 和 upper_bound 的 pair 桶、哈希操作

与unordered_set类似，只有bucket(const Key& key): 返回键为 key 的键值对所在的桶的索引

code示例 #include <iostream> #include <unordered_map> int main() { std::unordered_map<int, std::string> um1; // 空 unordered_map std::unordered_map<int, std::string> um = {{1, "one"}, {2, "two"}, {3, "three"}}; // 使用初始化列表创建 unordered_map //元素访问 std::cout << "um[2]: " << um[2] << std::endl; // 输出: two std::cout << "um.at(3): " << um.at(3) << std::endl; // 输出: three um[4] = "four"; // 插入新键值对 std::cout << "um[4]: " << um[4] << std::endl; // 输出: four //容量 std::cout << "um.empty(): " << um.empty() << std::endl; // 输出: 0 (false) std::cout << "um.size(): " << um.size() << std::endl; // 输出: 4 std::cout << "um.max_size(): " << um.max_size() << std::endl; // 输出: 一个很大的数 um.insert({5, "five"}); // 插入新键值对 um.erase(2); // 删除键为 2 的键值对 auto it = um.find(3); if (it != um.end()) { std::cout << "Found: " << it->second << std::endl; // 输出: Found: three } std::cout << "um.count(2): " << um.count(2) << std::endl; // 输出: 0 std::cout << "um.count(4): " << um.count(4) << std::endl; // 输出: 1 auto range = um.equal_range(2); if (range.first != range.second) { std::cout << "Equal range: " << range.first->second << std::endl; } else { std::cout << "No range found." << std::endl; //No range found } std::cout << "Bucket count: " << um.bucket_count() << std::endl; // 输出: 桶的数量 std::cout << "Bucket size for bucket 0: " << um.bucket_size(0) << std::endl; // 输出: 第 0 个桶中的键值对数量 std::cout << "Bucket for key 2: " << um.bucket(2) << std::endl; // 输出: 键为 2 的键值对所在的桶的索引 std::cout << "Load factor: " << um.load_factor() << std::endl; // 输出: 当前负载因子 std::cout << "Max load factor: " << um.max_load_factor() << std::endl; // 输出: 最大负载因子 um.rehash(10); // 设置桶的数量为至少 10 um.reserve(20); // 预留至少 20 个键值对的存储空间 return 0; } 3、std::unordered_multiset 特性unordered_setunordered_multiset元素唯一性只允许存储唯一元素允许存储重复元素插入操作如果元素已存在，插入操作不会成功可以插入多个相同的元素查找元素使用 count() 返回 0 或 1使用 count() 返回元素的出现次数内存开销通常较小，因为只存储唯一元素可能稍大，因为需要存储重复元素适用场景适用于需要唯一元素的场景，如集合运算适用于需要重复元素的场景，如频率统计迭代器迭代器指向唯一元素迭代器可以指向重复元素性能插入、查找、删除操作平均时间复杂度 O(1)插入、查找、删除操作平均时间复杂度 O(1)元素访问通过迭代器访问唯一元素通过迭代器访问所有元素，包括重复元素 #include <iostream> #include <unordered_set> int main() { // 1. 创建 unordered_multiset std::unordered_multiset<int> myMultiSet; // 2. 插入元素 myMultiSet.insert(1); myMultiSet.insert(2); myMultiSet.insert(2); // 插入重复元素 myMultiSet.insert(3); myMultiSet.insert(1); // 再次插入 1 // 3. 输出元素 std::cout << "unordered_multiset 中的元素: "; for (const auto& item : myMultiSet) { std::cout << item << " "; // 输出所有元素，包括重复元素 } std::cout << std::endl; // 4. 查找元素 auto it = myMultiSet.find(2); if (it != myMultiSet.end()) { std::cout << "找到元素 2" << std::endl; } else { std::cout << "未找到元素 2" << std::endl; } // 5. 计数元素 std::cout << "元素 1 的出现次数: " << myMultiSet.count(1) << std::endl; // 输出 2 std::cout << "元素 2 的出现次数: " << myMultiSet.count(2) << std::endl; // 输出 2 std::cout << "元素 4 的出现次数: " << myMultiSet.count(4) << std::endl; // 输出 0 // 6. 删除元素 myMultiSet.erase(2); // 删除一个 2 std::cout << "删除一个 2 后的元素: "; for (const auto& item : myMultiSet) { std::cout << item << " "; // 输出剩余元素 } std::cout << std::endl; // 7. 删除所有指定元素 myMultiSet.erase(1); // 删除所有 1 std::cout << "删除所有 1 后的元素: "; for (const auto& item : myMultiSet) { std::cout << item << " "; // 输出剩余元素 } std::cout << std::endl; // 8. 清空 unordered_multiset myMultiSet.clear(); std::cout << "清空后元素数量: " << myMultiSet.size() << std::endl; // 输出 0 return 0; } 4、unordered_multimap 内置函数unordered_mapunordered_multimap元素访问operator[]支持。如果键不存在，则插入默认值。不支持。at支持。如果键不存在，则抛出异常。不支持。容量操作  empty  size  max_size修改器clear支持支持insert支持。如果键已存在，则不会插入。支持。允许插入重复键。emplace支持。如果键已存在，则不会插入。支持。允许插入重复键。emplace_hint支持。如果键已存在，则不会插入。支持。允许插入重复键。try_emplace (C++17)支持。如果键已存在，则不会插入。不支持。erase支持。删除指定键的键值对。支持。删除指定键的所有键值对。swap支持支持extract (C++17)支持。提取指定键的节点支持。提取指定键的节点merge (C++17)支持。从另一个容器合并节点支持。从另一个容器合并节点查找操作find支持。返回指向第一个匹配键的迭代器。支持。返回指向第一个匹配键的迭代器count支持。返回匹配键的数量（0 或 1）。支持。返回匹配键的数量（可能大于 1）contains (C++20)支持。检查容器是否包含指定键。支持。检查容器是否包含指定键

equal_range

支持。返回匹配键的范围（最多一个键值对）支持。返回匹配键的范围（可能有多个键值对）桶操作   

bucket_count        bucket_size        bucket

哈希操作load_factor    max_load_factor        rehash        reserve #include <iostream> #include <unordered_map> int main() { // 1. 创建 unordered_multimap std::unordered_multimap<int, std::string> myMultiMap; // 2. 插入元素 myMultiMap.insert({1, "apple"}); myMultiMap.insert({2, "banana"}); myMultiMap.insert({2, "berry"}); // 插入重复键 myMultiMap.insert({3, "cherry"}); myMultiMap.insert({1, "apricot"}); // 再次插入键 1 // 3. 输出元素 std::cout << "unordered_multimap 中的元素: " << std::endl; for (const auto& pair : myMultiMap) { std::cout << pair.first << ": " << pair.second << std::endl; // 输出所有键值对 } // 4. 查找元素 auto range = myMultiMap.equal_range(2); std::cout << "键 2 对应的值: "; for (auto it = range.first; it != range.second; ++it) { std::cout << it->second << " "; // 输出所有对应值 } std::cout << std::endl; // 5. 计数元素 std::cout << "键 1 的出现次数: " << myMultiMap.count(1) << std::endl; // 输出 2 std::cout << "键 2 的出现次数: " << myMultiMap.count(2) << std::endl; // 输出 2 std::cout << "键 4 的出现次数: " << myMultiMap.count(4) << std::endl; // 输出 0 // 6. 删除元素 myMultiMap.erase(2); // 删除所有键为 2 的元素 std::cout << "删除键 2 后的元素: " << std::endl; for (const auto& pair : myMultiMap) { std::cout << pair.first << ": " << pair.second << std::endl; // 输出剩余元素 } // 7. 清空 unordered_multimap myMultiMap.clear(); std::cout << "清空后元素数量: " << myMultiMap.size() << std::endl; // 输出 0 return 0; }