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 }