目录
set是一种容器，用于存储一组唯一的元素，并按照一定的排序规则进行排序。set中的元素是按照升序排序的，默认情况下，它使用元素的比较运算符(<)来进行排序。
set的定义和结构如下：
template<class Key,class Compare = less<key>,
class Allocator = allocator<Key>>
class set;Key: 表示存储在set中的元素的类型
Compare:表示元素之间的比较函数对象的类型，默认为less，即按照元素的值进行比较
Allocator: 表示用于分配内存的分配器类型，默认为allocator。
set的内部实现使用了红黑树(一种自平衡的二又搜索树)来存储元素，并保持元素的有序性这使得在set中插入、删除和查找元素的时间复杂度都是对数时间，即O(lo n)。set中的元素是唯一的，即不允许重复的元素存在。当插入一个重复的元素时，set会自动忽略该元素。
函数?????????????????????????????? ?? 描述???????????????????? ? ? ?? ??? 平均时间复杂度?????? 最坏时间复杂度
insert ? ?????????????????? 向集合中插入元素?????????????????? ? ? ?? ????? O(logn)?????? O(logn)
erase ? ???????????????? ? 向集合中移除元素?????????????? ???? ? ? ? ???? O(logn)??????? O(logn)
find ?? ?????????????????? ?? 查找集合中的元素?????????????????????????????? O(logn)??????? O(logn)
lower_bound ?? ???? ? 返回第一个不小于给定值的迭代器 ???? O(logn)??????? O(logn)
upper_bound ? ?????? 返回第一个大于给定值的迭代器 ???????? O(logn)??????? O(logn)
size ? ???????????????????? 返回集合中元素的数量 ?????? ????????????? ?? O(1)??????? ? ? ?? O(1)
empty ? ????????????????? 检查集合是否为空 ????????????????????????????? O(1)????? ? ? ? ?? O(1)
clear ? ??????????????????? 清空集合 ??????????????????????????????????????????? O(1)???? ? ? ? ?? ? O(1)
begin ? ??????????????????? 返回指向集合起始位置的迭代器 ?????? O(1)???? ? ? ? ?? ? O(1)
end ? ??????????????????? 返回指向集合末尾位置的迭代器 ???????? O(1)???? ? ? ? ?? ? O(1)
rbegin ????????????????? 返回指向集合末尾位置的逆向迭代器 ?? O(1)???? ? ? ? ?? ? O(1)
swap ???????????????? 返回指向集合起始位置的逆向迭代器????? O(1)???? ? ? ? ?? ? O(1)
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int, greater<int>>mySet;//set<int>mySet;
mySet.insert(25);
mySet.insert(17);
mySet.insert(39);
mySet.insert(42);
for (const auto& elem : mySet)
{
cout << elem << ' ';
}
cout << endl;
return 0;
}#include<iostream>
#include<set>
using namespace std;
struct mycompare
{
bool operator()(const int& a, const int& b)const
{
return a > b;
}
};
int main()
{
set<int, mycompare>mySet;//set<int>mySet;
mySet.insert(25);
mySet.insert(17);
mySet.insert(39);
mySet.insert(42);
for (const auto& elem : mySet)
{
cout << elem << ' ';
}
cout << endl;
return 0;
}multiset容器允许存储重复的元素
函数?????????????????????????????? ?? 描述???????????????????? ? ? ?? ??? 平均时间复杂度?????? 最坏时间复杂度
insert ? ?????????????????? 向集合中插入元素?????????????????? ? ? ?? ????? O(logn)?????? O(logn)
erase ? ???????????????? ? 向集合中移除元素?????????????? ???? ? ? ? ???? O(logn)??????? O(logn)
find ?? ?????????????????? ?? 查找集合中的元素?????????????????????????????? O(logn)??????? O(logn)
lower_bound ?? ???? ? 返回第一个不小于给定值的迭代器 ???? O(logn)??????? O(logn)
upper_bound ? ?????? 返回第一个大于给定值的迭代器 ???????? O(logn)??????? O(logn)
size ? ???????????????????? 返回集合中元素的数量 ?????? ????????????? ?? O(1)??????? ? ? ?? O(1)
empty ? ????????????????? 检查集合是否为空 ????????????????????????????? O(1)????? ? ? ? ?? O(1)
clear ? ??????????????????? 清空集合 ??????????????????????????????????????????? O(1)???? ? ? ? ?? ? O(1)
begin ? ??????????????????? 返回指向集合起始位置的迭代器 ?????? O(1)???? ? ? ? ?? ? O(1)
end ? ??????????????????? 返回指向集合末尾位置的迭代器 ???????? O(1)???? ? ? ? ?? ? O(1)
rbegin ????????????????? 返回指向集合末尾位置的逆向迭代器 ?? O(1)???? ? ? ? ?? ? O(1)
rend????????????????????? 返回指向多重集合起始位置的逆向迭代器O(1)???????????? O(1)
没有特定的顺序
函数?????????????????????????????? ?? 描述???????????????????? ? ? ?? ??? 平均时间复杂度?????? 最坏时间复杂度
insert ? ?????????????????? 向集合中插入元素?????????????????? ? ? ?? ????? O(1)?????????????? O(n)
erase ? ???????????????? ? 向集合中移除元素?????????????? ???? ? ? ? ???? O(1)??????????????? O(n)
find ?? ?????????????????? ?? 查找集合中的元素?????????????????????????????? O(1)??????????????? O(n)
count????????????????????? 返回元素在集合中出现次数? ??????????? ?? O(1)??????? ? ? ?? O(n)
size ? ???????????????????? 返回集合中元素的数量 ?????? ????????????? ?? O(1)??????? ? ? ?? O(1)
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int>mySet;
//插入元素
mySet.insert(25);
mySet.insert(17);
mySet.insert(39);
mySet.insert(42);
for (const auto& elem : mySet)
{
cout << elem << ' ';
}
cout << endl;
//查找元素
int search = 25;
auto it = mySet.find(search);
if (it != mySet.end())
{
cout << search << "found in the set." << endl;
}
else
{
cout << search << "not found in the set." << endl;
}
//移除元素
int removeValue = 42;
mySet.erase(removeValue);
//再次遍历集合
cout << "Set elements after removal:";
for (const auto& elem : mySet)
{
cout << elem << ' ';
}
cout << endl;
//clear
mySet.clear();
if (mySet.empty())
{
cout << "Set is empty." << endl;
}
else
{
cout << "Set is not empty" << endl;
}
return 0;
}answer:
17 25 39 42
25found in the set.
Set elements after removal:17 25 39
Set is empty.