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）时，哈希表会自动扩容。

构造函数

迭代器

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 的内容

查找

桶操作

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）。它基于哈希表实现，支持快速的插入、删除和查找操作，同样具有哈希的一些特性

构造函数

元素访问

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

#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

#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;
}