C++ STL中 `set` 和 `multiset` 简单对比
在 C++ STL 中，set 和 multiset 都是用于存储唯一或重复元素的关联容器，但它们在处理元素的唯一性和特性方面有显著的区别。以下是这两个容器的详细比较：
1. 数据结构
set：基于红黑树（自平衡的二叉搜索树）实现，存储元素时保证每个元素的唯一性。multiset：同样基于红黑树实现，但允许存储重复元素，即同一个值可以出现多次。
2. 元素的唯一性
set：每个元素必须是唯一的。如果尝试插入一个已存在的元素，它将不会被插入。multiset：允许多个相同的元素，因此可以存储重复的值。
3. 查找、插入、删除效率
-
set：- 查找、插入和删除操作的平均时间复杂度为 O(log n)，因为需要在红黑树中维护元素的顺序。
-
multiset：- 查找、插入和删除的平均时间复杂度也为 O(log n)，却可以存储多个相同的元素。
4. 迭代和访问
set：可以按顺序遍历元素（默认是升序），每个键只有一个值。multiset：同样可以按顺序遍历元素，重复的元素会按插入顺序排列。
5. 应用场景
-
set：- 适用于需要唯一性且希望元素自动排序的场合，例如计算不同单词的数量、存储唯一的配置项等。
-
multiset：- 适用于需要存储重复值并保持有序的场合，例如统计字符出现频率、投票结果等。
示例代码
以下是使用 set 和 multiset 的简单示例：
#include <iostream>
#include <set>int main() {// 使用 setstd::set<int> uniqueSet = {3, 1, 2, 2, 4};std::cout << "Set (无重复)：";for (int num : uniqueSet) {std::cout << num << " "; // 输出去重后的元素}// 使用 multisetstd::multiset<int> orderedMultiset = {3, 1, 2, 2, 4};std::cout << "\nMultiset (允许重复)：";for (int num : orderedMultiset) {std::cout << num << " "; // 输出有序且允许重复的元素}std::cout << std::endl;return 0;
}
结论
选择 set 还是 multiset 主要依赖于需求：
- 如果需要确保元素的唯一性并按顺序管理，它是选择 set 的最佳时机。
- 如果需要处理重复元素，并且希望仍然有序，那么 multiset 是理想的选择。😊