一个基于红黑树的平衡二叉搜索树，它存储的元素是唯一的键，其中每个键都是唯一的，且无法修改。set 内部的数据会按照关键字以字母序自动排列。
头文件
#include
构造
-
set<类型> 标识符;
-
利用vector进行构造
常用函数
| void insert(const value_type& value) | 向 set 中插入一个键，如果键已存在，则插入操作会被忽略 |
|---|---|
| iterator find(const Key& key) | 返回一个指向键为 key 的元素的迭代器。如果找不到，则返回 set.end() |
| size_type erase(const key_type& key) | 删除键为 key 的元素，返回删除的元素数量 |
| void clear() | 移除 set 中的所有元素 |
| size_type count(const Key& key) const | 返回具有给定键 key 的元素数量。由于 set 中的键是唯一的，此函数返回值只能是 0 或 1 |
| iterator begin() | 返回指向 set 第一个元素的迭代器 |
| iterator end() | 返回指向 set 末尾的迭代器 |
| bool empty() const | 如果 set 为空，则返回 true |
| size_type size() const | 返回 set 中的元素数量 |
| void swap(set& other) | 与另一个 set 交换内容 |
set的优势
set 适用于需要存储唯一元素并且经常进行查找、插入和删除操作的场景。由于它是基于红黑树实现的，这些操作的时间复杂度为 O(log n)，保证了即使在大量元素的情况下也有良好的性能。此外，由于元素是自动排序的，set 也常用于需要有序元素的场景。
实例
#include<bits/stdc++.h>
using namespace std;
template <class T>
// 输出set全部值的函数
void printset (const set <T> &s) {
for(auto it=s.begin(); it!=s.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main(){
// 1、普通构造
set <int> s;
cout << "1、构造: "; printset(s);
// 2、vector构造
vector <int> v = {1, 5, 7};
set <int> st(v.begin(), v.end());
cout << "2、vector构造: "; printset(st);
// 3、insert插入
st.insert(3);
cout << "3、插入: "; printset(st);
// 4、自动排序
st.insert(2);
cout << "4、自动排序: "; printset(st);
// 5、长度函数
cout << "5、长度函数: " << st.size() <<endl;
// 6、重复插入
st.insert(2);
cout << "6、重复插入: "; printset(st);
// 7、其他数据类型
set <string> str_st;
str_st.insert("hongdou");
str_st.insert("lvdou");
str_st.insert("huangdou");
cout << "7、字符串set: "; printset(str_st);
return 0;
}
运行结果
结构体set
set内部会自动排序，那么，理论上只要能够进行排序的数据类型和STL容器都可以放到set里进行存储。 **BUT!!**大部分情况我们并不会这么做，这需要我们重新设计数据结构，其对应的复杂度和成本都比较高。 不过，结构体set的使用方法，还是比较简单，只需要重载小于号即可。
#include<bits/stdc++.h>
using namespace std;
template <class T>
// 输出set全部值的函数
void printset (const set <T> &s) {
for(auto it=s.begin(); it!=s.end(); it++) {
cout << it->id << " " << it->name << endl;
}
}
struct NODE {
string name;
int id;
// 重载小于号
bool operator < (const NODE &a) const {
return id < a.id;
}
};
int main(){
set <NODE> st;
st.insert({"haha", 2});
st.insert({"hehe", 1});
st.insert({"hihi", 0});
printset(st);
return 0;
}
运行结果
multiset
multiset 和 set 都是 C++ 标准库中基于红黑树实现的容器，用于存储排序的数据。它们之间的主要区别在于对元素唯一性的处理：
set中的元素必须是唯一的。如果尝试插入一个已经存在于set中的元素，该操作将不会执行。multiset允许存储重复的元素。也就是说，可以有多个具有相同值的元素存在于std::multiset中。
共 1 条回复
image.png