欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

STL之set的应用

程序员文章站 2022-04-04 09:54:01
Set是STL中的一个容器,特点是其中包含的元素值是唯一的,set根据其底层实现机制分为hash存储和红黑树存储两种方式,这两种结构最本质的区别就是有序和无序,红黑树的存储是有序的而hash表是无序存储,但它并不影响set的最主要的用法就是查找,而从查找角度来说hash表是更优于红黑树,从时间复杂度 ......

  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 }