STL之set的应用

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

  这里我们重点针对红黑树存储的set分析。

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

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

 

  程序中应包含头文件

#include <set>

 

 

一、创建集合

1 #include <iostream>
2 #include <set>
3 using namespace std;
4 
5 int main() {
6     set<int> s;
7 
8     return 0;
9 }

 

二、向集合中插入元素

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     set<int> s;
 7 
 8     s.insert(5);
 9     s.insert(3);
10     s.insert(6);
11     s.insert(1);
12     s.insert(8);
13     s.insert(5);
14 
15     return 0;
16 }

 

三、集合元素正向遍历

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     set<int> s;
 7 
 8     s.insert(5);
 9     s.insert(3);
10     s.insert(6);
11     s.insert(1);
12     s.insert(8);
13     s.insert(5);
14 
15     set<int>::iterator it;    //定义一个前向迭代器
16     for (it = s.begin(); it != s.end(); it++) {
17         cout << *it << ' ';
18     }
19     cout << endl;
20 
21     return 0；
22 }

 

四、集合元素的逆向遍历

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     set<int> s;
 7 
 8     s.insert(5);
 9     s.insert(3);
10     s.insert(6);
11     s.insert(1);
12     s.insert(8);
13     s.insert(5);
14 
15     set<int>::reverse_iterator rit;        //定义一个逆向迭代器
16     for (rit = s.rbegin(); rit != s.rend(); rit++) {
17         cout << *rit << ' ';
18     }
19     cout << endl;
20 
21     return 0；
22 }

 

五、集合元素的删除

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     set<int> s;
 7 
 8     s.insert(5);
 9     s.insert(3);
10     s.insert(6);
11     s.insert(1);
12     s.insert(8);
13     s.insert(5);
14 
15     set<int>::iterator it;    //定义一个前向迭代器
16     for (it = s.begin(); it != s.end(); it++) {
17         cout << *it << ' ';
18     }
19     cout << endl;
20 
21     //删除集合中的单一元素
22     //方法1：用find找到元素再删除
23     it = s.find(5);
24     if (it != s.end()) {
25         s.erase(it);
26     }
27 
28     //方法2：直接删除数据
29     s.erase(5);
30 
31     //删除某范围内的元素
32     it = s.find(3);
33     s.erase(s.begin(), it);
34 
35     return 0;
36 }

 

六、检索集合中的元素

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     set<int> s;
 7 
 8     s.insert(5);
 9     s.insert(3);
10     s.insert(6);
11     s.insert(1);
12     s.insert(8);
13     s.insert(5);
14 
15     ///检索集合中的元素
16     it = s.find(8);
17     if (it != s.end())
18         cout << *it << endl;
19     else
20         cout << "Not find!" << endl;
21 
22     return 0;
23 }

 

七、其他

1 //检测某一元素在集合中是否存在
2 s.count(6);
3 
4 //集合中元素数目
5 s.size();
6 
7 //清除集合中的所有元素
8 s.clear();

 

Set常用函数：

set成员函数:begin()--返回指向第一个元素的迭代器

set成员函数:clear()--清除所有元素

set成员函数:count()--返回某个值元素的个数

set成员函数:empty()--如果集合为空，返回true

set成员函数:end()--返回指向最后一个元素的迭代器

set成员函数:equal_range()--返回集合中与给定值相等的上下限的两个迭代器

set成员函数:erase()--删除集合中的元素

set成员函数:find()--返回一个指向被查找到元素的迭代器

set成员函数:get_allocator()--返回集合的分配器

set成员函数:insert()--在集合中插入元素

set成员函数:lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

set成员函数:key_comp()--返回一个用于元素间值比较的函数

set成员函数:max_size()--返回集合能容纳的元素的最大限值

set成员函数:rbegin()--返回指向集合中最后一个元素的反向迭代器

set成员函数:rend()--返回指向集合中第一个元素的反向迭代器

set成员函数:size()--集合中元素的数目

set成员函数:swap()--交换两个集合变量

set成员函数:upper_bound()--返回大于某个值元素的迭代器

set成员函数:value_comp()--返回一个用于比较元素间的值的函数

 

样例程序：

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int main() {
 6     ///创建一个集合
 7     set<int> s;
 8 
 9     ///向集合中插入元素
10     s.insert(5);
11     s.insert(3);
12     s.insert(6);
13     s.insert(1);
14     s.insert(8);
15     s.insert(5);    //集合中不存在重复元素，因此这个元素不会被插入
16 
17     ///集合元素的正向遍历
18     set<int>::iterator it;    //定义一个前向迭代器
19     for (it = s.begin(); it != s.end(); it++) {
20         cout << *it << ' ';
21     }
22     cout << endl;
23 
24     ///集合元素的逆向遍历
25     set<int>::reverse_iterator rit;
26     for (rit = s.rbegin(); rit != s.rend(); rit++) {
27         cout << *rit << ' ';
28     }
29     cout << endl;
30 
31     ///删除集合中的元素
32     //set<int>::iterator it;    //此处应有此语句，但因为前面已经定义了迭代器，为避免重定义这里不再定义
33     ///方法1：用find找到元素再删除
34     it = s.find(5);
35     if (it != s.end()) {
36         s.erase(it);    //删除单一元素
37     }
38     ///方法2：直接删除数据
39     //s.erase(5);
40     for (it = s.begin(); it != s.end(); it++) {
41         cout << *it << ' ';
42     }
43     cout << endl;
44     ///删除某范围内的元素
45     it = s.find(3);
46     s.erase(s.begin(), it);
47     for (it = s.begin(); it != s.end(); it++) {
48         cout << *it << ' ';
49     }
50     cout << endl;
51 
52     ///检索集合中的元素
53     //set<int>::iterator it    //此处应有此语句，但因为前面已经定义了迭代器，为避免重定义这里不再定义
54     it = s.find(8);
55     if (it != s.end())
56         cout << *it << endl;
57     else
58         cout << "Not find!" << endl;
59 
60     it = s.find(20);
61     if (it != s.end())
62         cout << *it << endl;
63     else
64         cout << "Not find!" << endl;
65 
66     ///返回某个值得元素个数，对一个集合来说，某元素只会存在一次，因此这个函数可以检测某元素在集合中是否存在
67     cout << s.count(6) << endl;    //返回某个值元素的个数
68 
69     ///集合中元素数目
70     cout << s.size() << endl;
71 
72     ///清除所有元素
73     s.clear();
74 
75     return 0;
76 }