STL 之 set的应用

关于set

Set是STL中的一个容器，特点是其中包含的元素值是唯一的，set根据其底层实现机制分为hash存储和红黑树存储两种方式，这两种结构最本质的区别就是有序和无序，红黑树的存储是有序的而hash表是无序存储，但它并不影响set的最主要的用法就是查找，而从查找角度来说hash表是更优于红黑树，从时间复杂度进行分析，红黑树的时间复杂度为O(logN)，而hash表的时间复杂度为O(1)。所以说hash表构建的set更高效。所以在对时间要求比较严格的情况下，可以优先采用hash表构建的set，即unordered_set。

平衡二叉检索树的检索使用中序遍历算法，检索效率高于vector、deque、和list的容器。另外，采用中序遍历算法可将键值由小到大遍历出来，所以可以理解为平衡二叉检索树在插入元素时，就会自动将元素按键值从小到大的顺序排列。

使用Set的主要目的是为了快速检索，特点是相同的值不存，存入的值按照顺序排列好。

当集合中的元素增加时，搜索集合速度的变化趋势如下

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

程序中应包含头文件

#include <set>

set常用操作

1.创建集合

set<int> s;

2.插入元素

s.insert(item);

3.正向访问元素

使用迭代器iterator

set<int>::iterator it;

for (it = s.begin(); it != s.end(); it++) {

    cout << *it << endl;

}

4.逆向访问元素

使用逆向迭代器reverse_iterator

set<int>::reverse_iterator rit;

for (rit = rbegin(); rit != rend(); rit++){

    cout << *rit << endl;

}

5.删除元素

s.erase(item);

s.erase(it);  //it是指向集合中某元素的一迭代器，**使用之后尤其注意it迭代器指向的位置，set中的erase没有自检功能**

6.检索元素

set<int>::iterator it;
it = s.find(item);        //查找集合中值为item的元素并把地址返回给迭代器it

7.检索某一元素是否存在于集合中

count方法本身时检测集合中某一元素的出现次数，但在集合中不存在重复元素，因此count就变为检测元素是否存在的方法

s.count(item);

8.集合中的元素数

s.size();

9.检测集合是否为空

s.empty();

10.清除集合中的所有元素

s.clear();

Set常用函数：

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

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

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

　　get_allocator() 返回集合的分配器

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

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

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

　　rbegin() 返回指向集合中最后一个元素的反向迭代器

　　rend() 返回指向集合中第一个元素的反向迭代器

　　swap() 交换两个集合变量

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

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

巴特西