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 是理想的选择。😊