专业视角:set 和 multiset的原理与应用解析
文章目录
- 前言
- 关联式容器
- 键值对
- 树形结构的关联式容器
- set
- 1. `set` 的定义
- 注意以下八点:
- 2. `set` 的常用操作
- 3. `set` 的迭代器
- 4. `set` 的底层实现
- 5. 自定义排序(比较器)
- 6. `set` 与 `multiset` 的区别
- 7. 示例:`set` 的完整代码
- multiset
前言
关联式容器
在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
那什么是关联式容器?它与序列式容器有什么区别?
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的
键值对,在数据检索时比序列式容器效率更高。
键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代
表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然
有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应
该单词,在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义:
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
树形结构的关联式容器
根据应用场景的不同,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结
构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使
用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一
个容器。
set
1. set
的定义
set
是 C++ 标准库中的一个关联容器,它存储的是唯一的元素,并且自动按一定的顺序排列元素。它通常基于平衡二叉搜索树(如红黑树)实现,提供 <u>O(log n)</u>
的查找、插入和删除时间复杂度。
特别记住两点:不重复,有序!
与 vector
或 list
等容器不同,set
会自动维护元素的顺序,通常是升序排序,但可以通过自定义比较函数来改变排序规则。
- set的模板参数列表:
T: set中存放元素的类型,实际在底层存储<value, value>的键值对。
Compare:set中元素默认按照小于来比较,也可以自己定义比较方式。
Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理
构造方式:
// 1. 默认构造函数
// 创建一个空的 set,元素类型为 int,使用默认的比较函数 less<int>
set<int> set1;
// 2. 范围构造函数
// 使用迭代器指定的范围来初始化 set
vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
set<int> set2(vec.begin(), vec.end());
// 由于 set 中元素唯一,重复元素会被自动去除,且会按升序排列
// 3. 拷贝构造函数
// 创建一个新的 set,它是另一个 set 的副本
set<int> set3(set2);
// 4. 移动构造函数
// 从另一个 set 中移动元素到新的 set 中,原 set 会变为空
set<int> set4(move(set3));
// 5. 初始化列表构造函数
// 使用初始化列表来初始化 set
set<int> set5 = {10, 20, 30, 40, 50};
- set是按照一定次序存储元素的容器
- 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。- 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行
排序。- set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对
子集进行直接迭代。- set在底层是用二叉搜索树(红黑树)实现的。
注意以下八点:
1. 与 map
/multimap
** 的区别:set
中只存 **value
- 区别:
map
和multimap
是键值对容器,每个元素是一个<key, value>
对。set
中存储的仅是value
,但底层实现实际上将value
视为<value, value>
的键值对,这样可以复用相同的底层数据结构(如红黑树)。
- 插入元素:
std::set<int> s;
s.insert(5); // 只插入 value,而不是 <key, value>
- `set` 中插入的只是单个值,而不是键值对。
2. 插入元素时,不需要构造键值对
- 由于
set
只需要存储value
,插入时直接提供单个值即可。底层数据结构会将其视为键值对<value, value>
,但用户无需关心这些细节。
示例:
std::set<int> s;
s.insert(10); // 只需要传递单个值
s.insert(20); // 不需要键值对
这种简化让 set
使用起来更加方便,因为它的重点是值本身,而不是键值关联。
3. set
中的元素不可以重复
- 特点:
set
保证存储的所有元素是唯一的。 - 实现方式:
- 当插入一个元素时,
set
会根据比较规则(通常是<
运算符)检查是否已经存在。 - 如果存在,则插入失败。
- 当插入一个元素时,
示例:
std::set<int> s;
s.insert(5); // 插入成功
s.insert(5); // 插入失败,值已经存在
应用场景:
- 去重。当需要去除数组或序列中的重复元素时,可以使用
<font style="color:rgba(0, 0, 0, 0.85);">std::set</font>
或<font style="color:rgba(0, 0, 0, 0.85);">std::unordered_set</font>
。将一组重复元素转化为唯一集合:
std::vector<int> v = {1, 2, 2, 3, 4, 4};
std::set<int> s(v.begin(), v.end()); // 自动去重
4. 使用 set
的迭代器遍历,可以得到有序序列
- 特点:
set
自动维护元素的顺序(通常是升序)。 - 遍历方式:
使用迭代器(begin()
和end()
)可以顺序访问元素。
示例:
std::set<int> s = {3, 1, 2};
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出:1 2 3
}
5. 默认按照“小于”比较排序
- 排序规则:
默认情况下,set
按照<
运算符来比较元素。 - 自定义规则:
可以通过传入自定义比较器来改变排序方式。
示例:默认升序排序:
std::set<int> s = {3, 1, 2};
for (int x : s) {
std::cout << x << " "; // 输出:1 2 3
}
自定义降序排序:
std::set<int, std::greater<int>> s = {3, 1, 2};
for (int x : s) {
std::cout << x << " "; // 输出:3 2 1
}
6. 查找某个元素的时间复杂度为 O(log₂ n)
- 原因:
set
底层实现基于红黑树(自平衡二叉搜索树),其深度为O(log₂ n)
。- 插入、删除和查找的时间复杂度都与树的高度成正比,因此为
O(log₂ n)
。
示例:
std::set<int> s = {3, 1, 2};
auto it = s.find(2); // 查找值为 2 的元素
if (it != s.end()) {
std::cout << "Found: " << *it << std::endl;
} else {
std::cout << "Not found!" << std::endl;
}
7. set
中的元素不允许修改
- 原因:
set
的底层实现依赖元素的排序规则。如果允许修改元素的值,可能破坏集合的有序性。- 一旦元素被插入,红黑树会根据该值的位置平衡树的结构。如果值被修改,这种平衡可能失效。
示例:
std::set<int> s = {1, 2, 3};
auto it = s.find(2);
// *it = 5; // 错误,不能直接修改元素
如果需要修改 set
中的元素,必须先删除该元素,再插入修改后的值:
s.erase(it); // 删除元素
s.insert(5); // 插入新值
8. 底层实现使用红黑树
- 红黑树简介:
红黑树是一种自平衡二叉搜索树,具有以下特点:
这些规则确保树的高度在 O(log₂ n)
范围内,从而保证插入、删除、查找操作的高效性。
- 每个节点要么是红色,要么是黑色。
- 树根是黑色。
- 红节点的子节点必须是黑色(即红节点不能连续)。
- 从根节点到任何叶子节点的路径中,黑节点数量相同。
红黑树在 set
中的作用:
- 确保
set
的元素总是有序。 - 保证查找、插入、删除的时间复杂度为
O(log₂ n)
。
2. set
的常用操作
- 插入元素:
insert()
方法插入一个元素。如果元素已经存在,则插入会失败,set
保证元素唯一性。
std::set<int> s;
s.insert(1); // 插入元素 1
s.insert(2); // 插入元素 2
s.insert(1); // 插入失败,因为 1 已经存在
- 删除元素:
erase()
方法用于删除指定的元素或通过迭代器删除元素。
s.erase(1); // 删除元素 1
- 查找元素:使用
find()
查找元素,如果找到返回指向该元素的迭代器,若找不到返回end()
迭代器。
auto it = s.find(2); // 查找元素 2
if (it != s.end()) {
std::cout << "Found: " << *it << std::endl;
}
- 访问元素:
set
中的元素不能通过下标访问,必须使用迭代器。
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出 set 中的元素
}
- 大小和空检查:
size()
方法返回容器中元素的个数,empty()
判断容器是否为空。
std::cout << "Size: " << s.size() << std::endl;
if (s.empty()) {
std::cout << "Set is empty." << std::endl;
}
lower_bound(value)
功能:返回指向第一个**不小于 **value
的元素的迭代器。如果容器中不存在这样的元素,则返回指向 end()
的迭代器。
用法:常用于查找某个值或**第一个****大于等于**该值的元素。
示例代码
set<int> s = {10, 20, 30, 40, 50};
int value = 25;
auto it = s.lower_bound(value); // 查找第一个不小于25的元素
if (it != s.end()) {
cout << "Lower bound of " << value << ": " << *it << endl; // 输出 30
} else {
cout << "No element found." << endl;
}
upper_bound(value)
- 功能:返回指向**第一个大于**** **
**value**
的元素的迭代器。如果容器中不存在这样的元素,则返回指向end()
的迭代器。 - 用法:常用于查找某个值的下一个元素,或第一个大于该值的元素。
示例代码
set<int> s = {10, 20, 30, 40, 50};
int value = 25;
auto it = s.upper_bound(value); // 查找第一个大于25的元素
if (it != s.end()) {
cout << "Upper bound of " << value << ": " << *it << endl; // 输出 30
} else {
cout << "No element found." << endl;
}
3. set
的迭代器
set
提供了双向迭代器,允许遍历容器中的元素。
begin()
:返回指向容器第一个元素的迭代器。end()
:返回指向容器尾后位置的迭代器,即指向容器中最后一个元素的下一个位置。rbegin()
:返回指向容器最后一个元素的反向迭代器。rend()
:返回指向容器第一个元素前一个位置的反向迭代器。
示例:
std::set<int> s = {3, 1, 2};
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出:1 2 3
}
std::cout << std::endl;
for (auto it = s.rbegin(); it != s.rend(); ++it) {
std::cout << *it << " "; // 输出:3 2 1
}
4. set
的底层实现
set
是基于平衡二叉搜索树(如红黑树或 AVL 树)实现的,这使得set
能够提供O(log n)
的查找、插入和删除操作。- 每个节点包含一个元素和指向左右子节点的指针。树是自平衡的,即插入或删除操作后,树会通过旋转操作保持平衡,保证操作的时间复杂度为
O(log n)
。
5. 自定义排序(比较器)
默认情况下,set
会按升序排列元素。如果想要按降序排列,或者按自定义规则排列,可以传入自定义的比较器。
例如,按降序排列:
#include <set>
std::set<int, std::greater<int>> s; // 使用 greater<int> 进行降序排列
s.insert(3);
s.insert(1);
s.insert(2);
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出:3 2 1
}
6. set
与 multiset
的区别
1. 元素唯一性
set
:不允许重复的元素。multiset
:允许存储重复的元素。
2. 插入规则
set
:插入时会检查是否已有相同的元素,如果存在,则插入失败。multiset
:可以插入相同的元素,multiset
会记录每个重复值。
3. 元素计数
set
:每个值在集合中最多出现一次,count()
的返回值是0
或1
。multiset
:可以存储相同的元素,count()
返回指定值的出现次数。
4. 查找和删除
set
:find()
:返回指定元素的迭代器(如果存在)。erase()
:删除指定值的唯一实例。
multiset
:find()
:返回指向第一个匹配值的迭代器。erase()
:删除某个值的所有实例,或者通过迭代器删除指定的单个实例。
5. 其他特性
- 两者底层都使用红黑树,时间复杂度为
O(log n)
。 - 都是有序容器,默认按升序排列元素。
#include <iostream>
#include <set>
int main() {
// 创建 set 和 multiset
std::set<int> mySet;
std::multiset<int> myMultiset;
// 插入元素
mySet.insert(5);
mySet.insert(3);
mySet.insert(5); // 重复插入失败
myMultiset.insert(5);
myMultiset.insert(3);
myMultiset.insert(5); // 重复插入成功
// 遍历元素
std::cout << "set elements: ";
for (const auto& elem : mySet) {
std::cout << elem << " ";
}
std::cout << "\n";
std::cout << "multiset elements: ";
for (const auto& elem : myMultiset) {
std::cout << elem << " ";
}
std::cout << "\n";
// 查找元素
auto itSet = mySet.find(5);
if (itSet != mySet.end()) {
std::cout << "Found 5 in set.\n";
}
auto itMultiset = myMultiset.find(5);
if (itMultiset != myMultiset.end()) {
std::cout << "Found 5 in multiset.\n";
}
// 统计元素数量
std::cout << "Count of 5 in set: " << mySet.count(5) << "\n";
std::cout << "Count of 5 in multiset: " << myMultiset.count(5) << "\n";
// 删除元素
mySet.erase(5); // 删除唯一的 5
myMultiset.erase(5); // 删除所有 5
// 遍历删除后的容器
std::cout << "set after erase: ";
for (const auto& elem : mySet) {
std::cout << elem << " ";
}
std::cout << "\n";
std::cout << "multiset after erase: ";
for (const auto& elem : myMultiset) {
std::cout << elem << " ";
}
std::cout << "\n";
return 0;
}
输出示例
set elements: 3 5
multiset elements: 3 5 5
Found 5 in set.
Found 5 in multiset.
Count of 5 in set: 1
Count of 5 in multiset: 2
set after erase: 3
multiset after erase: 3
总结
- 相同点:
- 都是有序容器,支持高效的插入、查找和删除操作(
O(log n)
)。 - 使用迭代器遍历时,元素按照排序规则输出。
- 都是有序容器,支持高效的插入、查找和删除操作(
- 不同点:
set
不允许重复元素,multiset
允许。set.count(x)
的值是0
或1
,而multiset.count(x)
可以大于 1。
选择 set
或 multiset
,取决于是否需要支持重复的元素存储。
7. 示例:set
的完整代码
#include <iostream>
#include <set>
int main() {
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array+sizeof(array)/sizeof(array));
cout << s.size() << endl;
// 正向打印set中的元素,从打印结果中可以看出:set可去重
for (auto& e : s)
cout << e << " ";
cout << endl;
// 使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";
cout << endl;
// set中值为3的元素出现了几次
cout << s.count(3) << endl;
// 创建一个空的 set 容器
std::set<int> s;
// 插入元素
s.insert(3);
s.insert(1);
s.insert(2);
// 遍历 set 并输出元素
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出:1 2 3
}
std::cout << std::endl;
// 查找元素
auto it = s.find(2);
if (it != s.end()) {
std::cout << "Found: " << *it << std::endl;
}
// 删除元素
s.erase(2);
// 输出删除后的元素
for (auto it = s.begin(); it != s.end(); ++it) {
std::cout << *it << " "; // 输出:1 3
}
std::cout << "\nSize: " << s.size() << std::endl;
std::cout << "Is empty: " << s.empty() << std::endl;
return 0;
}
输出:
1 2 3
Found: 2
1 3
Size: 2
Is empty: 0
multiset
- multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。
- 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成
的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值**不能在容器
**中进行修改(因为元素总是const的),但可以从容器中插入或删除。 - 在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则
进行排序。 - multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢,但当使用迭
代器遍历时会得到一个有序序列。 - multiset底层结构为二叉搜索树(红黑树)。
注意:
- multiset中再底层中存储的是<value, value>的键值对
- mtltiset的插入接口中只需要插入即可
- 与set的区别是,multiset中的元素可以重复,set是中value是唯一的
- 使用迭代器对multiset中的元素进行遍历,可以得到有序的序列
- multiset中的元素不能修改
- 在multiset中找某个元素,时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
- multiset的作用:可以对元素进行有重复的排序
- 📜 [ 声明 ] 由于作者水平有限,本文有错误和不准确之处在所难免,
- 本人也很想知道这些错误,恳望读者批评指正!
- 我是:勇敢滴勇~感谢大家的支持!