set和multiset会根据特定的排序准则，自动将元素排序。两者不同之处在于multiset 允许元素重复而 set 不允许。如下图:
使用set或multiset，必须先包含头文件:
#include <set>
上述两个类型都被定义为命名空间std内的class template:
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是能进行排序的数据类型。第二个参数是进行排序的规则,默认为升序(小于,<),第三个是内存分配器,不用管。
set 和multiset通常用平衡二叉树(balanced binary tree,确切说是红黑树)实现。这样在插入数据时能自动排序,使得查找元素时有良好性能。其查找函数具有对数O(logn)时间复杂度。
但是,自动排序也造成set和multiset的一个重要限制:你**不能直接改变元素值，**因为这样会打乱原本正确的顺序。
从其接口也能反映这种情况:
set和multiset不提供任何函数可以直接访问元素。
通过迭代器访问元素时都是常量。
1.1 定义及初始化🍗
set的定义和初始化如下:
#include <set>
#include <iostream>
using namespace std;
//输出s(升序)的所有数据
void Show(const set<int>& s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
//输出s(降序)的所有数据
void Show(const set<int,greater<int>>&s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
int main()
{
set <int> s0;//创建一个空的int set集合
s0.insert(5); //插入数据
s0.insert(3);
s0.insert(1);
s0.insert(2);
s0.insert(4);
s0.insert(4);//相同数据插入失败
set <int> s1(s0); //利用原来的set对象,创建一个新的set对象
set <int> s2 = s1;//同上
set <int> s3(s0.begin(), --s0.end());//利用迭代器创建一个新的set对象
set <int> s4{ 1, 6, 3, 5, 4, 2 };//利用初始化列表创建一个set对象,可以无序
cout << "s0:"; Show(s0); //输出数据
cout << "s1:"; Show(s1);
cout << "s2:"; Show(s2);
cout << "s3:"; Show(s3);
cout << "s4:"; Show(s4);
cout << "降序的集合" << endl;
set <int, greater<int> > s5; //创建一个降序的set集合
s5.insert(10);//插入数据
s5.insert(40);
s5.insert(30);
s5.insert(20);
cout << "s5:"; Show(s5);//输出数据
return 0;
}
multiset定义和初始化如下:
#include <set>
#include <iostream>
using namespace std;
//输出s(升序)的所有数据
void Show(const multiset<int>& s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
//输出s(降序)的所有数据
void Show(const multiset<int, greater<int>>& s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
int main()
{
multiset <int> s0;//创建一个空的int set集合
s0.insert(5); //插入数据
s0.insert(3);
s0.insert(1);
s0.insert(2);
s0.insert(4);
s0.insert(4);//可以插入相同数据
multiset <int> s1(s0); //利用原来的set对象,创建一个新的set对象
multiset <int> s2 = s1;//同上
multiset <int> s3(s0.begin(), --s0.end());//利用迭代器创建一个新的set对象
multiset <int> s4{ { 1, 6, 3, 5, 4, 2 } };//利用初始化列表创建一个set对象
cout << "s0:"; Show(s0); //输出数据
cout << "s1:"; Show(s1);
cout << "s2:"; Show(s2);
cout << "s3:"; Show(s3);
cout << "s4:"; Show(s4);
cout << "降序的集合" << endl;
multiset <int, greater<int> > s5; //创建一个降序的set集合
s5.insert(10);//插入数据
s5.insert(40);
s5.insert(30);
s5.insert(20);
cout << "s5:"; Show(s5);//输出数据
return 0;
}
1.2 向set和multiset中添加元素和删除元素🍗
通过insert函数插入数据。通过erase删除元素。
//输出s(升序)的所有数据
void Show(const set<int>& s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
int main()
{
set<int> s1;
s1.insert(4);
s1.insert(1);
s1.insert(5);
s1.insert(2);
cout << "s1:"; Show(s1);
s1.erase(2);
cout << "删除2后,s1:"; Show(s1);
s1.clear();
cout << "清空后,s1:"; Show(s1);
return 0;
}
1.3 常用迭代器🍗
set和multiset支持双向迭代器,不支持随机迭代器,可以往前和往后,但不能+1,-1(这是随机迭代器)等。
常用的迭代器如下:
s.begin()
第一个元素的迭代器
s.end()
最后一个元素的下一个位置迭代器(尾后迭代器或尾迭代器)
s.cbegin()
第一个元素的常量迭代器(不修改元素内容)
s.cend()
尾后常量迭代器(不修改元素内容)
s.rbegin()
第一个反向迭代器
s.rend()
尾后反向迭代器
int main()
{
set<int> s1;
s1.insert(4);
s1.insert(1);
s1.insert(5);
s1.insert(2);
cout << "从头到尾输出s1:";
for (auto p = s1.begin(); p != s1.end(); p++)
cout << *p << " ";
cout << endl;
cout << "从后往前输出s1:";
for (auto p = s1.rbegin(); p != s1.rend(); p++)
cout << *p << " ";
cout << endl;
auto p = s1.begin();
cout << "第二个元素:"<< * (++p) << endl;//输出第二个元素
cout << "第一个元素:"<< * (--p) << endl;//输出第一个元素
//cout << *(p + 1) << endl;//错误
return 0;
}
1.4 set和multiset常用的运算符🍗
set和multiset类既支持常用的=,==,!=,< , >等运算符,也可以通过调用其成员函数来执行相应的操作。下面列举了其常用的操作。详细情况可以参考set或multiset帮助手册。
//输出s(升序)的所有数据
void Show(const set<int>& s)
{
for (auto i : s)
cout << i << " ";
cout << endl;
}
int main()
{
set<int> s1;
s1.insert(4);
s1.insert(1);
s1.insert(5);
s1.insert(2);
cout << "s1:"; Show(s1);
set<int> s2;
s2 = s1;
cout << "s2:"; Show(s2);
if (s1 == s2)
cout << "s1 == s2" << endl;
s2.insert(7);
cout << "往s2插入7后,";
if (s1 > s2)
cout << "s1 > s2" ;
else if (s1 < s2)
cout << "s1 < s2" ;
//cout << s1[1] << endl;//错误
return 0;
}
1.5 set和multiset常用成员函数🍗
下面列举set和multiset对象常用的成员函数,详细的介绍请查看帮助手册。
1.6 set应用场景🍗
set在C++中是一个内部自动有序且不含重复元素的容器，它的应用场景广泛且多样。以下是一些set的常见应用场景：
1.自动排序
如果需要对元素保持持续的排序状态，如维持一个按字母顺序排列的单词列表、存储并维护一个按年龄升序或降序排列的人口数据库等，std::set 可以实现这一功能。每次插入新元素，容器都会自动调整元素的顺序。
当然如果仅仅是排序,可以使用sort函数进行排序.
sort排序是在排序瞬间的,如果又插入新的数据可能不再有序
set的有序是持续的,不管插入还是删除数据它始终有序
2.快速查找
由于set内部采用了高效的平衡查找二叉树（如红黑树），因此它提供快速的查找性能。包括检查元素是否已存在（.count() 或 .find()）、查找特定值的下一个/前一个元素（迭代器操作）。这对于实现诸如查找词汇表中的下一个更大词、或者在游戏中查找排名高于当前玩家的下一个玩家等场景很有用。
本篇完！🍗
