C++ std::unordered_multiset 详细使用指南

std::unordered_multiset 是 C++ STL 提供的一个 无序关联容器，允许存储 多个相同元素，并基于哈希表实现。它支持平均时间复杂度为 O(1) 的插入、删除和查找操作，适用于需要快速访问且允许元素重复的场景。

1. 基本特性

2. 头文件与声明

#include <unordered_set>  // 必须包含此头文件

// 声明语法
std::unordered_multiset<T> ums;  // 默认哈希函数和比较规则
std::unordered_multiset<T, Hash, KeyEqual> ums;  // 自定义哈希和比较

• T：元素类型（需支持哈希函数和相等比较）。

• Hash：自定义哈希函数（默认 std::hash<T>）。

• KeyEqual：自定义比较函数（默认 std::equal_to<T>）。

3. 基本操作
(1) 插入元素

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> ums;

    // 方式 1: insert()
    ums.insert(3);
    ums.insert(1);
    ums.insert(2);
    ums.insert(3);  // 允许重复

    // 方式 2: emplace()（直接构造元素）
    ums.emplace(4);
    ums.emplace(3);  // 允许重复

    // 输出所有元素（顺序不固定）
    for (const auto& val : ums) {
        std::cout << val << " ";  // 可能的输出: 3 1 2 3 4 3
    }
    std::cout << std::endl;

    return 0;
}

(2) 访问元素
std::unordered_multiset 不支持 operator[] 和 at()（因元素可重复），需通过迭代器或范围查询访问：

// 查找元素 3 的第一个位置
auto it = ums.find(3);
if (it != ums.end()) {
    std::cout << "找到元素: " << *it << std::endl;  // 输出: 3
}

// 统计元素 3 的出现次数
size_t count = ums.count(3);  // 返回 3
std::cout << "元素3出现次数: " << count << std::endl;

(3) 删除元素

// 删除所有值为 3 的元素
size_t removed = ums.erase(3);  // 返回删除的元素数量

// 删除指定迭代器的元素
auto it = ums.find(1);
if (it != ums.end()) {
    ums.erase(it);  // 删除元素 1
}

// 删除迭代器范围 [first, last)
ums.erase(ums.begin(), ums.find(2));

(4) 遍历元素

// 遍历所有元素
for (const auto& val : ums) {
    std::cout << val << " ";
}

// 通过桶遍历（高级用法）
size_t bucket_count = ums.bucket_count();
for (size_t i = 0; i < bucket_count; ++i) {
    std::cout << "Bucket "<< i << ": ";
    for (auto it = ums.begin(i); it != ums.end(i); ++it) {
        std::cout << "{" << *it << "} ";
    }
    std::cout << std::endl;
}

4. 自定义哈希函数与比较规则
当元素为自定义类型时，需提供哈希函数和比较函数：

#include <string>
#include <functional>

struct Person {
    std::string name;
    int age;

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

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

// 自定义比较函数（可选，默认使用 operator==）
struct PersonEqual {
    bool operator()(const Person& lhs, const Person& rhs) const {
        return lhs.name == rhs.name && lhs.age == rhs.age;
    }
};

// 声明容器
std::unordered_multiset<Person, PersonHash, PersonEqual> ump;

5. 桶相关操作
std::unordered_multiset 的底层哈希表由多个桶组成，相同元素的哈希值可能分布在不同桶中：

// 获取桶的数量
size_t bucket_count = ums.bucket_count();

// 获取元素所在的桶编号
size_t bucket_index = ums.bucket(3);

// 获取桶的大小
size_t bucket_size = ums.bucket_size(bucket_index);

6. 性能调优参数

// 设置最大负载因子
ums.max_load_factor(0.5);

// 预分配 200 个桶
ums.rehash(200);

7. 典型应用场景
(1) 统计重复元素

// 统计单词出现次数（允许重复）
std::unordered_multiset<std::string> wordCount;
wordCount.insert("apple");
wordCount.insert("banana");
wordCount.insert("apple");

// 遍历所有元素
for (const auto& word : wordCount) {
    std::cout << word << " ";
}
// 输出可能为: apple banana apple

(2) 多值集合

// 存储用户评论（允许重复评论）
std::unordered_multiset<std::string> comments;
comments.insert("Great!");
comments.insert("Useful");
comments.insert("Great!");

8. 与 std::multiset 的区别

9. 注意事项

1. 无序性：元素存储顺序与插入顺序无关，仅由哈希函数决定。

2. 哈希冲突：冲突严重时性能下降，需合理设计哈希函数。

3. 自定义类型：必须提供哈希函数和比较函数，否则编译错误。

4. 迭代器失效：删除元素可能导致部分迭代器失效。

10. 总结
std::unordered_multiset 是处理 允许重复的无序元素 的高效工具，适用于需要快速插入、删除和查找的场景。通过合理使用哈希函数和桶操作，可以进一步优化性能。以下是其核心优势：
• ✅ 允许重复元素，灵活性高。

• ✅ 平均 O(1) 时间复杂度，适合高频操作。

• ✅ 支持自定义哈希和比较规则，扩展性强。

示例代码：

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> ums;
    ums.insert(5);
    ums.insert(2);
    ums.insert(8);
    ums.insert(2);

    // 遍历输出
    for (const auto& val : ums) {
        std::cout << val << " ";
    }
    // 可能的输出: 2 5 8 2

    return 0;
}

通过灵活运用 std::unordered_multiset，可以高效解决需要快速存取且允许重复的实际问题。