C++知识点 STL容器2—set

~set~

  set可能算是一种比较冷门的STL容器了,

  喜欢用它的人觉得set真牛逼

  不喜欢它的人觉得set真垃圾

  很不幸,我属于第一种


 

   set作为一种封装好的数据容器

  最吸引人的地方是它的自动排序功能

  这也就是说你可以拥有一个实时的排好序的序列

  或者可以用一个序列同时实现大根堆和小根堆

  时间复杂度和空间都是两者和的1/2

  善于运用set的自动排序特性可以为解题省去不少麻烦

  啊就爽,就很爽。

  继承STL容器的传统

  set也有它自己专属的头文件 <set>

  这个头文件内包含两种容器

  set和multiset

  set是自动排序还附带去重的序列(有序集合),其中的元素不可重复

  multiset是自动排序不去重的序列(有序多重集),其中可以有许多相同的元素

  个人感觉在实际OI问题中比较常用的是multiset这种不去重的

  两者的实现原理都是一颗我不会打的红黑树,它们支持的函数基本相同


  步入正题

  首先我们来看一下怎么声明一个set和multiset并往其中插入元素

 #include <iostream>
 #include <set>
 using namespace std;
 struct Node {
       int l, r, val;
 }; 
 bool operator <(const Node &a, const Node &b)
     { return a.val < b.val; }
 int main()
 {
     set<int> p;//声明方式与其他容器并无太大差异 
     multiset<int> q;
     set<Node> fuc;//压入set的东西类型必须定义"<" 
 }

  当然,你也可以这么写(友元版)

 #include <iostream>
 #include <set>
 using namespace std;
 struct Node {
     int l, r, val;
     bool friend operator <(const Node &a, const Node &b)
     {return a.val < b.val;}
     set<Node> fuc;   
 }; 
 int main()
 {
     set<int> p; 
     multiset<int> q;
 } 

  这样就完成了以普通数据类型和结构体的sethemultiset的声明

  同时切记:set和multiset内的数据类型必须已定义小于号

  学完了声明就该学如何往容器内插入元素

  (size函数,empty函数,clear函数在set中也有,与在vector中作用无异,故此处不提)

  与vector不同,往set内插入元素不需要指定位置

  元素进入set后自动根据“<”的定义找到自己的位置

  set和multiset都使用insert函数插入元素

  时间复杂度为O(logn)

  代码如下

 #include <iostream>
 #include <set>
 using namespace std;
 int x;
 int main()
 {
     set<int> p; 
     multiset<int> q;
     int n;
     cin>>n;
     for(int i = 1; i <= n; i++)
     {
         cin>>x;
         q.insert(x);
         p.insert(x);
     }
 }

  如此即可实现向set p和multiset q中插入n个元素

  插入完元素后我们可以对这些元素进行操作

  首先需要注意的是set不支持随机访问

  也就是说不能通过下标的方式访问set中的元素

  想想也很好理解,即使这货能用下标你也不知道排完序后哪个元素是哪个

  所以set给了我们与之替代的两种数据查找方式

  迭代器(可以理解为STL的指针)和find函数

  set的迭代器声明方式与在vector中的声明方式无异

  同样是声明一个名为it的迭代器

  有set<int>::iterator it;

  如果++it,

  则it指向set中的下一个元素

  因为set是有序集合,所以++it所表示的元素就是刚好比it所指向的元素大的第一个元素

  同时set也有begin和end函数用来取队首和队尾(的迭代器)

  begin在set中取的是最小元素的迭代器

  end函数跟vector中一样返回队尾下个元素的迭代器

  所以--end()表示的是队尾元素的迭代器

  我们看一段遍历set的代码来帮助我们理解这些抽象的概念

 #include <iostream>
 #include <set>
 using namespace std;
 int main()
 {
     set<int> a;
     multiset<int> b;
     a.insert(1);
     a.insert(2);
     a.insert(3);
     a.insert(1);
     b.insert(1);
     b.insert(2);
     b.insert(3);
     b.insert(1);
     cout<<"set 中的元素依次是 ";
     for(set<int>::iterator it = a.begin(); it != a.end(); it++)
     cout<<*it<<" "; 
     cout<<endl;
     cout<<"multiset 中的元素依次是 ";
     for(multiset<int>::iterator it = b.begin(); it != b.end(); it++)
     cout<<*it<<" ";
     cout<<endl;
     return 0;
} 

  程序输出结果是

 set 中的元素依次是 1 2 3
 multiset 中的元素依次是 1 1 2 3

  在这个例子中我们可以了解到set中迭代器的用法和set与multiset的本质区别

  有助于我们搞明白并在程序上实现set的基本操作

  了解了迭代器

  我们再来看看我认为能与迭代器平起平坐帮了大忙的find函数

  find函数能够找到set中大小为x的元素并返回指向该元素的迭代器。

  如果set中并不存在元素x则返回s.end()

  x 多次出现则返回第一次出现时的迭代器

  样例如下

 #include <iostream>
 #include <set>
 using namespace std;
 int main()
 {
     set<int> p;
     multiset<int> q;
     p.insert(1);
     p.insert(2);
     p.insert(3);
     p.insert(1);
     q.insert(1);
     q.insert(2);
     q.insert(3);
     q.insert(1);
     int a = *p.find(1);
     int b = *q.find(3);
     cout<<a<<"    "<<b<<endl;
     return 0;  
 }

  聪明的你已经看出来了

  我这么写返回的一定是要查找的那个数

  其实就是没屁用

  啊就有的题可能会出现需要用到find函数的地方(装不下去了)

  在实际应用中,我们需要对不需要的元素进行删除

  set给了我们一个强大的数据删除函数erase()

  括号内既可以是一个迭代器

  erase删除这个迭代器所指的元素

  括号内也可以是个值或者啥东西

  erase在set或multiset中查找并删除和括号内这个东西一样的全部元素

  那问题来了

  在用multiset解决实际问题时

  很多情况下我们并不想把所有相同的元素都删除

  只想删除一个两个或几个(erase说没门儿

  此时find函数突然出现

  “劳资返回的是迭代器hahahahaha”

  于是你就可以用find函数定位到元素x第一次出现的位置并返回此时的迭代器

  再用erase通过迭代器删除的功能删除这个x

  由于multiset恒为有序所以删除哪个x无关紧要

  反正修改后的multiset都一样

  所以我们就解决了这个问题(find函数大放异彩)

  

 

上一篇:c++的 set 和 multiset 容器


下一篇:STL源码剖析学习记录(二)