C++STL set的用法总结

前言

set集合容器：实现了红黑树的平衡二叉检索树的数据结构，插入元素时，它会自动调整二叉树的排列，把元素放到适当的位置，以保证每个子树根节点键值大于左子树所有节点的键值，小于右子树所有节点的键值；另外，还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器，另外使用中序遍历可将键值按照从小到大遍历出来。
构造set集合主要目的是为了快速检索，不可直接去修改键值。

1.常用操作

头文件：#include<set>

set的操作有很多，下面是几种比较常用的

1.元素插入：s.insert(2);      //把2放入到集合中
2.元素删除：s.erase(2);       //删除键值为2的元素
3.元素清空：s.clear();        //删除元素中所有元素
4.元素检索：s.find(2);        //在s中查找2，若找到，返回该元素迭代器的位置，否则，返回最后一个元素后面一个位置。
5.集合是否为空：s.empty();    //集合为空时返回true
6.检查元素个数：s.count(2);   // 返回值为2的元素的个数
7.二分查找：s.lower_bound(2); //返回指向大于（或等于）2的第一个元素的迭代器
           s.upper_bound(2); //返回大于2的迭代器
8.集合元素个数：s.size()      //集合中元素的数目

2.用法详细

标准库提供set关联容器分为：

1，按关键字有序保存元素：set(关键字即值，即只保存关键字的容器)；multiset(关键字可重复出现的set)；

2，无序集合：unordered_set(用哈希函数组织的set)；unordered_multiset(哈希组织的set，关键字可以重复出现)。

set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。
在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。

set具备的两个特点：
set中的元素都是排序好的
set中的元素都是唯一的，没有重复的

set容器中只能存储键，是单纯的键的集合，其中键是不能重复的。
set支持大部分的map的操作，但是set不支持下标的操作

3.代码示例

1、set对象的定义和初始化
set对象的定义和初始化方法包括：

set<T> s;
set<T> s(s1);
set<T> s(b, e);

2、set中数据的插入
与map不同，set中数据只能通过insert()函数进行插入。

#include <stdio.h>
#include <vector>
#include <set>
 
using namespace std;
 
int main(){
        vector<int> v;
        for (int i = 0; i < 10; i++){
                v.push_back(i);
                v.push_back(i);
        }
 
        set<int> s;
        s.insert(v.begin(), v.end());
        set<int>::iterator it;
        for (it = s.begin(); it != s.end(); it++){
                printf("%d\t", *it);
        }
        printf("\n");
 
        s.insert(10);
        for (it = s.begin(); it != s.end(); it++){
                printf("%d\t", *it);
        }
        printf("\n");
 
        return 0;
}

3、从set中查找和读取元素
从set中查找同样可以使用count()函数和find()函数

#include <stdio.h>
#include <vector>
#include <set>
 
using namespace std;
 
int main(){
        vector<int> v;
        for (int i = 0; i < 10; i++){
                v.push_back(i);
                v.push_back(i);
        }
 
        set<int> s;
        s.insert(v.begin(), v.end());
        set<int>::iterator it;
        for (it = s.begin(); it != s.end(); it++){
                printf("%d\t", *it);
        }
        printf("\n");
 
        printf("%d\n", s.count(9));
        printf("%d\n", *(s.find(9)));
        return 0;
}

4、从set中删除元素
从set中删除元素使用到的函数是erase()函数，主要有以下的几种形式：

erase(k);
erase§;
erase(b, e);
其中，p表示的迭代器指向的元素，b和e分别是迭代器的开始和结束。

#include <stdio.h>
#include <vector>
#include <set>
 
using namespace std;
 
int main(){
        vector<int> v;
        for (int i = 0; i < 10; i++){
                v.push_back(i);
                v.push_back(i);
        }
 
        set<int> s(v.begin(), v.end());
        set<int>::iterator it;
        for (it = s.begin(); it != s.end(); it++){
                if (*it == 5){
                        break;
                }
        }
        s.erase(it, s.end());
 
        set<int>::iterator it_1;
        for (it_1 = s.begin(); it_1 != s.end(); it_1++){
                printf("%d\t", *it_1);
        }
        printf("\n");
 
        return 0;
}

后记

关于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的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。