C++集合与多重集合的深入解析

### C++ 集合与多重集合的深入解析 #### 1. 集合与多重集合概述 集合（Set）和多重集合（Multiset）容器会根据特定的排序准则自动对元素进行排序。二者的区别在于，多重集合允许元素重复，而集合不允许。 要使用集合或多重集合，需要包含头文件 `<set>`： ```cpp #include <set> ``` 在命名空间 `std` 中，它们被定义为类模板： ```cpp namespace std { template <typename T, typename Compare = less<T>, typename Allocator = allocator<T> > class set; template <typename T, typename Compare = less<T>, typename Allocator = allocator<T> > class multiset; } ``` 集合或多重集合的元素可以是任何根据排序准则可比较的类型 `T`。可选的第二个模板参数定义排序准则，若未传递特殊排序准则，则使用默认准则 `less`，它通过 `<` 运算符对元素进行排序。可选的第三个模板参数定义内存模型，默认内存模型是 `allocator`，由 C++ 标准库提供。 排序准则必须定义严格弱序，具有以下四个属性： 1. **反对称性**：对于 `<` 运算符，如果 `x < y` 为真，则 `y < x` 为假；对于谓词 `op()`，如果 `op(x, y)` 为真，则 `op(y, x)` 为假。 2. **传递性**：对于 `<` 运算符，如果 `x < y` 为真且 `y < z` 为真，则 `x < z` 为真；对于谓词 `op()`，如果 `op(x, y)` 为真且 `op(y, z)` 为真，则 `op(x, z)` 为真。 3. **非自反性**：对于 `<` 运算符，`x < x` 始终为假；对于谓词 `op()`，`op(x, x)` 始终为假。 4. **等价传递性**：大致来说，如果 `a` 等价于 `b` 且 `b` 等价于 `c`，则 `a` 等价于 `c`。对于 `<` 运算符，如果 `!(a < b) && !(b < a)` 为真且 `!(b < c) && !(c < b)` 为真，则 `!(a < c) && !(c < a)` 为真；对于谓词 `op()`，如果 `op(a, b)`、`op(b, a)`、`op(b, c)` 和 `op(c, b)` 都为假，则 `op(a, c)` 和 `op(c, a)` 为假。 根据这些属性，排序准则也用于检查元素的等价性。即如果两个元素都不小于对方（或者 `op(x, y)` 和 `op(y, x)` 都为假），则认为它们是重复元素。对于多重集合，等价元素的顺序是随机但稳定的，插入和删除操作会保留等价元素的相对顺序（自 C++11 起保证）。 #### 2. 集合与多重集合的能力 集合和多重集合通常实现为平衡二叉树（如红黑树）。自动排序的主要优点是在搜索具有特定值的元素时，二叉树的性能良好，搜索函数具有对数复杂度。例如，在包含 1000 个元素的集合或多重集合中搜索元素，成员函数执行的树搜索平均只需要线性搜索（遍历所有元素的搜索算法）五十分之一的比较次数。 然而，自动排序也对集合和多重集合施加了一个重要限制：不能直接更改元素的值，因为这样可能会破坏正确的顺序。要修改元素的值，必须先移除具有旧值的元素，然后插入具有新值的元素。其接口体现了这一特性： - 集合和多重集合不提供直接访问元素的操作。 - 通过迭代器的间接访问有一个限制，从迭代器的角度看，元素值是常量。 #### 3. 集合与多重集合的操作 ##### 3.1 创建、复制和销毁 可以通过两种方式定义排序准则： 1. **作为模板参数**：例如 `std::set<int, std::greater<int>> coll;`，此时排序准则是类型的一部分，类型系统确保只有具有相同排序准则的容器才能组合。 2. **作为构造函数参数**：适用于在运行时处理排序准则，或者需要相同数据类型但不同排序准则的情况。 如果未传递特殊排序准则，则使用默认的排序准则 `less<>`，通过 `<` 运算符对元素进行排序。排序准则也用于检查同一容器中两个元素的等价性（即查找重复元素）。 集合和多重集合的构造函数和析构函数如下表所示： | 操作 | 效果 | | --- | --- | | `set c` | 默认构造函数，创建一个空的集合/多重集合 | | `set c(op)` | 创建一个使用 `op` 作为排序准则的空集合/多重集合 | | `set c(c2)` | 复制构造函数，创建另一个相同类型集合/多重集合的副本 | | `set c = c2` | 复制构造函数，创建另一个相同类型集合/多重集合的副本 | | `set c(rv)` | 移动构造函数，创建一个新的相同类型集合/多重集合，获取右值 `rv` 的内容（自 C++11 起） | | `set c = rv` | 移动构造函数，创建一个新的相同类型集合/多重集合，获取右值 `rv` 的内容（自 C++11 起） | | `set c(beg, end)` | 创建一个由范围 `[beg, end)` 中的元素初始化的集合/多重集合 | | `set c(beg, end, op)` | 创建一个使用排序准则 `op`，由范围 `[beg, end)` 中的元素初始化的集合/多重集合 | | `set c(initlist)` | 创建一个由初始化列表 `initlist` 中的元素初始化的集合/多重集合（自 C++11 起） | | `set c = initlist` | 创建一个由初始化列表 `initlist` 中的元素初始化的集合/多重集合（自 C++11 起） | | `c.~set()` | 销毁所有元素并释放内存 | 这里的 `set` 可以是以下类型之一： | 类型 | 效果 | | --- | --- | | `set<Elem>` | 默认使用 `less<> (operator <)` 排序的集合 | | `set<Elem, Op>` | 默认使用 `Op` 排序的集合 | | `multiset<Elem>` | 默认使用 `less<> (operator <)` 排序的多重集合 | | `multiset<Elem, Op>` | 默认使用 `Op` 排序的多重集合 | 使用这种方式检查等价性有三个优点： 1. 只需要传递一个参数作为排序准则。 2. 不需要为元素类型提供 `==` 运算符。 3. 可以对等价性和相等性有不同的定义（但这可能会引起混淆）。 需要注意的是，如果使用 `==` 运算符比较两个容器，会使用元素的 `==` 运算符比较两个容器中的元素，这意味着元素类型必须提供 `==` 运算符。 ##### 3.2 非修改操作 集合和多重集合提供了常见的非修改操作，用于查询大小和进行比较，如下表所示： | 操作 | 效果 | | --- | --- | | `c.key_comp()` | 返回比较准则 | | `c.value_comp()` | 返回作为整体值的比较准则（与 `key_comp()` 相同） | | `c.empty()` | 返回容器是否为空（等价于 `size() == 0`，但可能更快） | | `c.size()` | 返回当前元素的数量 | | `c.max_size()` | 返回可能的最大元素数量 | | `c1 == c2` | 返回 `c1` 是否等于 `c2`（调用元素的 `==` 运算符） | | `c1 != c2` | 返回 `c1` 是否不等于 `c2`（等价于 `!(c1 == c2)`） | | `c1 < c2` | 返回 `c1` 是否小于 `c2` | | `c1 > c2` | 返回 `c1` 是否大于 `c2`（等价于 `c2 < c1`） | | `c1 <= c2` | 返回 `c1` 是否小于或等于 `c2`（等价于 `!(c2 < c1)`） | | `c1 >= c2` | 返回 `c1` 是否大于或等于 `c2`（等价于 `!(c1 < c2)`） | 比较操作仅适用于相同类型的容器，即元素和排序准则必须具有相同的类型，否则会在编译时发生类型错误。 ##### 3.3 特殊搜索操作 由于集合和多重集合针对快速搜索元素进行了优化，它们提供了特殊的搜索函数，这些函数是同名通用算法的特殊版本，应优先使用这些优化版本以实现对数复杂度，而不是通用算法的线性复杂度。特殊搜索操作如下表所示： | 操作 | 效果 | | --- | --- | | `c.count(val)` | 返回值为 `val` 的元素数量 | | `c.find(val)` | 返回值为 `val` 的第一个元素的位置（如果未找到则返回 `end()`） | | `c.lower_bound(val)` | 返回 `val` 应该插入的第一个位置（第一个 `>= val` 的元素） | | `c.upper_bound(val)` | 返回 `val` 应该插入的最后一个位置（第一个 `> val` 的元素） | | `c.equal_range(val)` | 返回所有值等于 `val` 的元素的范围（即 `val` 应该插入的第一个和最后一个位置） | 以下是使用 `lower_bound()`、`upper_bound()` 和 `equal_range()` 的示例代码： ```cpp // cont/setrange1.cpp #include <iostream> #include <set> using namespace std; int main () { set<int> c; c.insert(1); c.insert(2); c.insert(4); c.insert(5); c.insert(6); cout << "lower_bound(3): " << *c.lower_bound(3) << endl; cout << "upper_bound(3): " << *c.upper_bound(3) << endl; cout << "equal_range(3): " << *c.equal_range(3).first << " " << *c.equal_range(3).second << endl; cout << endl; cout << "lower_bound(5): " << *c.lower_bound(5) << endl; cout << "upper_bound(5): " << *c.upper_bound(5) << endl; cout << "equal_range(5): " << *c.equal_range(5).first << " " << *c.equal_range(5).second << endl; } ``` 程序的输出如下： ``` lower_bound(3): 4 upper_bound(3): 4 equal_range(3): 4 4 lower_bound(5): 5 upper_bound(5): 6 equal_range(5): 5 6 ``` 如果使用多重集合代替集合，程序的输出相同。 ##### 3.4 赋值操作 集合和多重集合仅提供所有容器都有的基本赋值操作，如下表所示： | 操作 | 效果 | | --- | --- | | `c = c2` | 将 `c2` 的所有元素赋值给 `c` | | `c = rv` | 移动赋值，将右值 `rv` 的所有元素赋值给 `c`（自 C++11 起） | | `c = initlist` | 将初始化列表 `initlist` 的所有元素赋值给 `c`（自 C++11 起） | | `c1.swap(c2)` | 交换 `c1` 和 `c2` 的数据 | | `swap(c1, c2)` | 交换 `c1` 和 `c2` 的数据 | 对于这些操作，两个容器必须具有相同的类型，特别是比较准则的类型必须相同，尽管比较准则本身可能不同。