C++unordered multiset

C++ unordered_multiset

`unordered_multiset`是C++标准模板库(STL)中的一个关联容器，它存储不重复或可重复的元素，且不按特定顺序排列。与`unordered_set`不同，`unordered_multiset`允许存储多个相同的元素。它基于哈希表实现，因此插入、删除和查找操作的平均时间复杂度为O(1)。

基本特性

• 无序存储：元素不按任何特定顺序排列。
• 允许重复：可以存储多个相同的元素。
• 哈希表实现：基于哈希函数快速访问元素。
• 高效操作：平均时间复杂度为O(1)，最坏情况下为O(n)。

头文件与声明

使用`unordered_multiset`需要包含头文件`<unordered_set>`，并使用`std`命名空间。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_multiset<int> nums = {1, 2, 2, 3, 4, 4, 4};
    for (int num : nums) {
        std::cout << num << " ";
    }
    return 0;
}

输出：

4 4 4 3 2 2 1

常用成员函数

以下是`unordered_multiset`的常用操作：

函数	描述
insert(value)	插入一个元素
erase(value)	删除一个或多个元素
find(value)	查找元素，返回迭代器
count(value)	返回元素出现的次数
size()	返回容器中元素的数量
empty()	检查容器是否为空
clear()	清空容器

示例：插入与删除

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_multiset<std::string> words;
    words.insert("apple");
    words.insert("banana");
    words.insert("apple");  // 允许重复

    std::cout << "Count of 'apple': " << words.count("apple") << std::endl;

    words.erase("apple");  // 删除所有"apple"
    std::cout << "Count after erase: " << words.count("apple") << std::endl;
    return 0;
}

输出：

Count of 'apple': 2
Count after erase: 0

实际应用案例

`unordered_multiset`常用于需要快速统计元素频率的场景，例如：

案例：统计单词频率

#include <unordered_set>
#include <iostream>
#include <vector>

void countWords(const std::vector<std::string>& text) {
    std::unordered_multiset<std::string> wordCount;
    for (const auto& word : text) {
        wordCount.insert(word);
    }

    for (const auto& word : wordCount) {
        std::cout << word << ": " << wordCount.count(word) << std::endl;
    }
}

int main() {
    std::vector<std::string> text = {"hello", "world", "hello", "cpp", "world"};
    countWords(text);
    return 0;
}

输出：

world: 2
cpp: 1
hello: 2

高级特性

自定义哈希函数

默认情况下，`unordered_multiset`使用`std::hash`计算哈希值。如果需要自定义类型，需提供哈希函数：

#include <unordered_set>
#include <string>

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

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

int main() {
    std::unordered_multiset<Person, PersonHash> people;
    people.insert({"Alice", 30});
    people.insert({"Bob", 25});
    return 0;
}

性能优化

通过调整桶的数量和负载因子可以优化性能：

std::unordered_multiset<int> nums;
nums.reserve(100);  // 预分配空间
nums.max_load_factor(0.7);  // 设置最大负载因子

与其它容器的比较

容器	有序性	重复元素	实现方式
std::set	有序	不允许	红黑树
std::multiset	有序	允许	红黑树
std::unordered_set	无序	不允许	哈希表
std::unordered_multiset	无序	允许	哈希表

总结

`unordered_multiset`是一个高效的容器，适用于需要快速插入、删除和查找的场景，且允许重复元素。通过合理使用哈希函数和性能优化，可以进一步提升其效率。