跳到主要内容

C++ unordered_multiset

简介​

unordered_multiset 是C++ STL（标准模板库）中的一个容器，它允许存储重复的键值，并且以无序的方式组织元素。该容器在C++11标准中被引入，它是基于哈希表实现的，因此提供了接近O(1)的平均查找、插入和删除时间复杂度。

与 std::multiset 相比，unordered_multiset 不会对元素进行排序，因此在不需要元素有序的情况下，它通常能提供更好的性能。

关键特点
  • 允许重复键值
  • 无序存储（基于哈希表）
  • 快速查找、插入和删除操作
  • 需要哈希函数支持

头文件和命名空间​

在使用 unordered_multiset 之前，需要包含相应的头文件：

cpp
#include <unordered_set> // 注意：unordered_multiset 定义在 unordered_set 头文件中

unordered_multiset 位于 std 命名空间内，所以使用时需要：

cpp
std::unordered_multiset<int> myMultiset; // 示例声明

或者使用 using 指令：

cpp
using namespace std;
unordered_multiset<int> myMultiset;

创建和初始化​

基本创建方式​

cpp
// 创建一个空的unordered_multiset
std::unordered_multiset<int> nums1;

// 使用初始化列表创建
std::unordered_multiset<int> nums2 = {1, 2, 3, 2, 1};

// 使用迭代器范围创建
std::vector<int> vec = {5, 6, 7, 5};
std::unordered_multiset<int> nums3(vec.begin(), vec.end());

// 拷贝构造
std::unordered_multiset<int> nums4(nums2);

自定义哈希函数和比较器​

对于自定义类型，需要提供哈希函数和相等比较器：

cpp
struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

// 创建使用自定义哈希函数的unordered_multiset
std::unordered_multiset<Person, PersonHash> people;

基本操作​

插入元素​

cpp
std::unordered_multiset<int> nums;

// 插入单个元素
nums.insert(10);
nums.insert(20);
nums.insert(10);  // 可以插入重复值

// 插入迭代器范围的元素
std::vector<int> vec = {30, 40, 30};
nums.insert(vec.begin(), vec.end());

// 使用emplace直接构造并插入元素（效率更高）
nums.emplace(50);

查找元素​

cpp
std::unordered_multiset<int> nums = {1, 2, 3, 2, 1};

// 查找元素
auto it = nums.find(2);
if (it != nums.end()) {
    std::cout << "找到元素: " << *it << std::endl;
}

// 统计元素出现次数
std::cout << "元素2出现的次数: " << nums.count(2) << std::endl;

// 检查元素是否存在
if (nums.contains(3)) {  // C++20特性
    std::cout << "元素3存在" << std::endl;
}

// 查找特定值的所有实例
auto range = nums.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

删除元素​

cpp
std::unordered_multiset<int> nums = {1, 2, 3, 2, 1};

// 删除特定值的一个实例
nums.erase(nums.find(1));

// 删除特定值的所有实例
nums.erase(2);

// 使用迭代器范围删除
auto range = nums.equal_range(1);
nums.erase(range.first, range.second);

// 清空容器
nums.clear();

容量操作​

cpp
std::unordered_multiset<int> nums = {1, 2, 3, 2, 1};

// 检查容器是否为空
if (!nums.empty()) {
    std::cout << "容器不为空" << std::endl;
}

// 获取元素数量
std::cout << "元素数量: " << nums.size() << std::endl;

// 获取容器当前桶数
std::cout << "桶数量: " << nums.bucket_count() << std::endl;

// 获取负载因子(load factor)，即元素数量/桶数量
std::cout << "负载因子: " << nums.load_factor() << std::endl;

迭代和遍历​

cpp
std::unordered_multiset<int> nums = {1, 2, 3, 2, 1};

// 使用迭代器遍历
for (auto it = nums.begin(); it != nums.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

// 使用范围for循环(C++11及之后)
for (const auto& num : nums) {
    std::cout << num << " ";
}
std::cout << std::endl;
注意

unordered_multiset 中元素的遍历顺序不是固定的，而且可能在插入或删除操作后发生变化。这是因为内部哈希表可能需要重新分配以保持性能。

哈希表操作​

unordered_multiset 提供了一些操作其底层哈希表的方法：

cpp
std::unordered_multiset<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// 调整桶的数量
nums.rehash(20);  // 设置至少20个桶
nums.reserve(100);  // 预留足够的空间存储100个元素

// 查看特定桶的信息
for (size_t i = 0; i < nums.bucket_count(); ++i) {
    std::cout << "桶 " << i << " 包含 " << nums.bucket_size(i) << " 个元素" << std::endl;
}

// 获取元素所在的桶
std::cout << "元素5在桶 " << nums.bucket(5) << " 中" << std::endl;

性能考虑​

unordered_multiset 的性能特点：

性能警告

当存在大量哈希冲突时，unordered_multiset 的性能会从O(1)劣化至O(n)。选择合适的哈希函数和负载因子对于维持良好性能至关重要。

实际应用场景​

计数问题​

使用 unordered_multiset 统计字符出现频率：

cpp
#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::string text = "hello world hello cpp";
    std::unordered_multiset<char> characters;
    
    // 插入所有字符
    for (char c : text) {
        characters.insert(c);
    }
    
    // 输出每个字符的频率
    std::cout << "字符频率统计：" << std::endl;
    for (char c = 'a'; c <= 'z'; ++c) {
        size_t count = characters.count(c);
        if (count > 0) {
            std::cout << c << ": " << count << std::endl;
        }
    }
    
    return 0;
}

输出示例：

字符频率统计：
c: 1
d: 1
e: 2
h: 2
l: 5
o: 3
p: 2
r: 1
w: 1

多值映射关系​

记录学生选修的多门课程：

cpp
#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_multiset<std::string> courseEnrollments;
    
    // 添加学生选课记录
    courseEnrollments.insert("Math");
    courseEnrollments.insert("Physics");
    courseEnrollments.insert("Chemistry");
    courseEnrollments.insert("Math");      // 多个学生选了数学
    courseEnrollments.insert("Physics");   // 多个学生选了物理
    courseEnrollments.insert("Biology");
    courseEnrollments.insert("Math");      // 又一个学生选了数学
    
    // 显示每门课程的学生数量
    std::cout << "课程注册统计：" << std::endl;
    std::cout << "数学: " << courseEnrollments.count("Math") << " 名学生" << std::endl;
    std::cout << "物理: " << courseEnrollments.count("Physics") << " 名学生" << std::endl;
    std::cout << "化学: " << courseEnrollments.count("Chemistry") << " 名学生" << std::endl;
    std::cout << "生物: " << courseEnrollments.count("Biology") << " 名学生" << std::endl;
    std::cout << "计算机: " << courseEnrollments.count("Computer Science") << " 名学生" << std::endl;
    
    return 0;
}

输出示例：

课程注册统计：
数学: 3 名学生
物理: 2 名学生
化学: 1 名学生
生物: 1 名学生
计算机: 0 名学生

unordered_multiset vs 其他容器​

让我们比较 unordered_multiset 与相关容器的区别：

特性unordered_multisetmultisetunordered_setset
允许重复值✅✅❌❌
元素排序❌✅❌✅
查找复杂度平均O(1)O(log n)平均O(1)O(log n)
内部实现哈希表红黑树哈希表红黑树
迭代器类型前向迭代器双向迭代器前向迭代器双向迭代器

总结​

unordered_multiset 是C++ STL中一个强大的容器，适用于需要存储重复元素且不关心顺序，但需要高效查找、插入和删除操作的场景。它的主要特点包括：

  • 基于哈希表实现，提供平均常数时间复杂度的操作
  • 允许存储重复键值
  • 元素无序存储
  • 支持自定义哈希函数和比较器

这些特性使它在处理需要多值关联的数据集、频率统计等问题上表现出色。然而，在需要排序数据或内存开销敏感的场景中，可能需要考虑其他容器类型。

练习​

  1. 创建一个 unordered_multiset 并计算给定文本中每个单词的出现频率。
  2. 实现一个简单的图结构，使用 unordered_multiset 存储边的信息。
  3. 编写一个程序，比较 unordered_multiset 和 multiset 在大数据集上的性能差异。
  4. 创建一个自定义类型并实现合适的哈希函数，然后使用 unordered_multiset 存储该类型。
  5. 使用 unordered_multiset 实现一个简单的文本索引系统，根据关键词快速查找包含该词的所有文档。

延伸阅读​

  • C++ 标准库中的哈希函数如何工作
  • 哈希冲突的解决策略与性能影响
  • 选择合适的容器：何时使用 unordered_multiset 而非其他容器
  • 自定义哈希函数的最佳实践
  • C++20中 unordered_multiset 的新特性