Set(集合)

简介 

        关于set，必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree，其插入删除查找的效率是稳定的O(logn)。这个效率是很高的，当然设计合适的hash函数速度更快O（1），但对于一般的问题这个已经足够了，而且简单书写。)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。 

日常用处

自动去重，自动排序

---

set中的常用方法

常用的操作就是 遍历容器，插入、删除元素，统计元素出现次数

1. begin()--返回指向第一个元素的迭代器

2. end()--返回指向最后一个元素的迭代器

3. count()--返回某个值元素的个数

4. empty()--判断集合是否为空，是则返回true

5. clear()--清除所有元素

6 .insert()--在集合中插入元素

7. erase()--删除集合中的元素（）

8. size()--集合中当前的元素个数    

9. swap()--交换两个集合变量   

10.find()--返回一个指向被查找到元素的迭代器 

11. lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

12.upper_bound()--返回大于某个值元素的迭代器   

13. max_size()--返回集合能容纳的元素的最大限值

14. value_comp()--返回一个用于比较元素间的值的函数   

15. rbegin()--返回指向集合中最后一个元素的反向迭代器（返回的值和end()相同）

16. rend()--返回指向集合中第一个元素的反向迭代器（返回的值和rbegin()相同）

17.key_comp()--返回一个用于元素间值比较的函数

18.equal_range()--返回集合中与给定值相等的上下限的两个迭代器

19. get_allocator()--返回集合的分配器

set的创建和初始化

#include <iostream>
#include <set>
#include <functional>
using namespace std;
set<int> s;

int main(){
   set<int > seta; //默认是小于比较器less<int>的set

   set<int, greater<int> > setb; //创建一个带大于比较器的set，需包含头文件functional

   int a[5] = {1,2,3,4,5};
   set<int > setc(a,a+5); //数组a初始化一个set；

   set<int > setd(setc.begin(),setc.end()); //setc初始化一个set
   //上述两例均为区间初始化

   set<int > sete(setd); //拷贝构造创建set
   return 0;
}

 

set的遍历

这里涉及了迭代器的知识

#include<set>
using namespace std;
int main(){
    set<int>st; //定义了一个int类型的集合，名称为st
    st.insert(1); st.insert(7);    st.insert(4);
    st.insert(0);
    for(set<int>::iterator it = st.begin();it!=st.end();++it){
        printf("%d ",*it);
    }
}
可以看出迭代器的使用和指针类似 ， 也是通过解引用运算符 *it来获取值，也可以通过++ -- 移动。
也可以单个取出元素
set<int>::iterator it = st.begin();
printf("%d\n",*it);
 
注意这里的.begin()代表了set中的首元素位置，而.end()代表的是尾元素位置的下一个位置。
STL中很多容器都是这样的左闭右开区间，不用去深究。

 

 

---

 

关于set有下面几个问题：

（1）为何map和set的插入删除效率比用其他序列容器高？

大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

 

　　A
　  / \
　 B C
　/ \ / \
  D E F G

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

---

TIPS： 对于需要集合中存在重复元素的情况，STL中也封装的multiset，用法和set几乎一样，这里不再赘述。

推荐的习题：按照各路大牛博客中的STL分类去刷就行，我推荐一个多么痛的领悟，第六届山东省ACM程序设计竞赛B题

题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=3252

http://codeforces.com/contest/620/problem/C

 

具体详解传送门