MyException - 我的异常网
当前位置:我的异常网» 综合 » STL之set集合器皿 【转】

STL之set集合器皿 【转】

www.MyException.Cn  网友分享于:2013-09-28  浏览:0次
STL之set集合容器 【转】

      set集合容器实现了红黑树(Red-Black Tree)的平衡二叉检索树的的数据结构,在插入元素时,它会自动调整二叉树的排列,把该元素放到适当的位置,以确保每个子树根节点的键值大于左子树所有节点的键值,而小于右子树所有节点的键值;另外,还得确保根节点的左子树的高度与有字数的高度相等,这样,二叉树的高度最小,从而检索速度最快。要注意的是,它不会重复插入相同键值的元素,而采取忽略处理。

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

        构造set集合的主要目的是为了快速检索,使用set前,需要在程序头文件中包含声明“#include<set>”。

1.创建set集合对象

           创建set对象时,需要指定元素的类型,这一点和其他容器一样。

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

2.元素的插入与中序遍历

        采用inset()方法把元素插入到集合中,插入规则在默认的比较规则下,是按元素值从小到大插入,如果自己指定了比较规则函数,则按自定义比较规则函数插入。使用前向迭代器对集合中序遍历,结果正好是元素排序后的结果。

  1. #include<iostream>  
  2. #include<set>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     set<int> s;  
  7.     s.insert(5); //第一次插入5,可以插入  
  8.     s.insert(1);  
  9.     s.insert(6);  
  10.     s.insert(3);  
  11.     s.insert(5); //第二次插入5,重复元素,不会插入  
  12.     set<int>::iterator it; //定义前向迭代器  
  13.     //中序遍历集合中的所有元素  
  14.     for(it = s.begin(); it != s.end(); it++)  
  15.     {  
  16.         cout << *it << " ";  
  17.     }  
  18.     cout << endl;  
  19.     return 0;  
  20. }  
  21. //运行结果:1 3 5 6  

3.元素的方向遍历

        使用反向迭代器reverse_iterator可以反向遍历集合,输出的结果正好是集合元素的反向排序结果。它需要用到rbegin()和rend()两个方法,它们分别给出了反向遍历的开始位置和结束位置。

  1. #include<iostream>  
  2. #include<set>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     set<int> s;  
  7.     s.insert(5); //第一次插入5,可以插入  
  8.     s.insert(1);  
  9.     s.insert(6);  
  10.     s.insert(3);  
  11.     s.insert(5); //第二次插入5,重复元素,不会插入  
  12.     set<int>::reverse_iterator rit; //定义反向迭代器  
  13.     //反向遍历集合中的所有元素  
  14.     for(rit = s.rbegin(); rit != s.rend(); rit++)  
  15.     {  
  16.         cout << *rit << " ";  
  17.     }  
  18.     cout << endl;  
  19.     return 0;  
  20. }  
  21. //运行结果:6 5 3 1  

4.元素的删除

        与插入元素的处理一样,集合具有高效的删除处理功能,并自动重新调整内部的红黑树的平衡。删除的对象可以是某个迭代器位置上的元素、等于某键值的元素、一个区间上的元素和清空集合。

  1. #include<iostream>  
  2. #include<set>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     set<int> s;  
  7.     s.insert(5); //第一次插入5,可以插入  
  8.     s.insert(1);  
  9.     s.insert(6);  
  10.     s.insert(3);  
  11.     s.insert(5); //第二次插入5,重复元素,不会插入  
  12.     s.erase(6); //删除键值为6的元素  
  13.     set<int>::reverse_iterator rit; //定义反向迭代器  
  14.     //反向遍历集合中的所有元素  
  15.     for(rit = s.rbegin(); rit != s.rend(); rit++)  
  16.     {  
  17.         cout << *rit << " ";  
  18.     }  
  19.     cout << endl;   
  20.     set<int>::iterator it;  
  21.   
  22.     it = s.begin();  
  23.     for(int i = 0; i < 2; i++)  
  24.         it = s.erase(it);   
  25.     for(it = s.begin(); it != s.end(); it++)  
  26.         cout << *it << " ";  
  27.     cout << endl;  
  28.   
  29.     s.clear();  
  30.     cout << s.size() << endl;  
  31.   
  32.     return 0;  
  33. }  
  34. /* 
  35. 运行结果: 
  36. 5 3 1 
  37. 0     
  38. */  

5.元素的检索

          使用find()方法对集合进行检索,如果找到查找的的键值,则返回该键值的迭代器位置;否则,返回集合最后一个元素后面的一个位置,即end()。

  1. #include<iostream>  
  2. #include<set>  
  3. using namespace std;  
  4. int main()  
  5. {  
  6.     set<int> s;  
  7.     s.insert(5); //第一次插入5,可以插入  
  8.     s.insert(1);  
  9.     s.insert(6);  
  10.     s.insert(3);  
  11.     s.insert(5); //第二次插入5,重复元素,不会插入  
  12.     set<int>::iterator it;  
  13.     it = s.find(6); //查找键值为6的元素  
  14.     if(it != s.end())  
  15.         cout << *it << endl;  
  16.     else  
  17.         cout << "not find it" << endl;  
  18.     it = s.find(20);  
  19.     if(it != s.end())  
  20.         cout << *it << endl;  
  21.     else  
  22.         cout << "not find it" << endl;  
  23.     return 0;  
  24. }  
  25. /* 
  26. 运行结果: 
  27. not find it    
  28. */  

下面这种方法也能判断一个数是否在集合中:

  1. #include <cstdio>  
  2. #include <set>  
  3. using namespace std;  
  4. int main() {  
  5.     set <int> s;  
  6.     int a;  
  7.     for(int i = 0; i < 10; i++)  
  8.         s.insert(i);  
  9.     for(int i = 0; i < 5; i++) {  
  10.         scanf("%d", &a);  
  11.         if(!s.count(a)) //不存在  
  12.             printf("does not exist\n");  
  13.         else  
  14.             printf("exist\n");  
  15.     }  
  16.     return 0;  
  17. }  


6.自定义比较函数

         使用insert将元素插入到集合中去的时候,集合会根据设定的比较函数奖该元素放到该放的节点上去。在定义集合的时候,如果没有指定比较函数,那么采用默认的比较函数,即按键值从小到大的顺序插入元素。但在很多情况下,需要自己编写比较函数。

编写比较函数有两种方法。

(1)如果元素不是结构体,那么可以编写比较函数。下面的程序比较规则为按键值从大到小的顺序插入到集合中。

  1. #include<iostream>  
  2. #include<set>  
  3. using namespace std;  
  4. struct mycomp  
  5. //自定义比较函数,重载“()”操作符  
  6.     bool operator() (const int &a, const int &b)  
  7.     {  
  8.         if(a != b)  
  9.             return a > b;  
  10.         else  
  11.             return a > b;  
  12.     }  
  13. };  
  14. int main()  
  15. {  
  16.     set<int, mycomp> s; //采用比较函数mycomp  
  17.     s.insert(5); //第一次插入5,可以插入  
  18.     s.insert(1);  
  19.     s.insert(6);  
  20.     s.insert(3);  
  21.     s.insert(5); //第二次插入5,重复元素,不会插入  
  22.     set<int,mycomp>::iterator it;  
  23.     for(it = s.begin(); it != s.end(); it++)  
  24.         cout << *it << " ";  
  25.     cout << endl;  
  26.     return 0;  
  27. }  
  28. /* 
  29. 运行结果:6 5 3 1   
  30. */  

(2)如果元素是结构体,那么可以直接把比较函数写在结构体内。

    1. #include<iostream>  
    2. #include<set>  
    3. #include<string>  
    4. using namespace std;  
    5. struct Info  
    6. {  
    7.     string name;  
    8.     double score;  
    9.     bool operator < (const Info &a) const // 重载“<”操作符,自定义排序规则  
    10.     {  
    11.         //按score由大到小排序。如果要由小到大排序,使用“>”即可。  
    12.         return a.score < score;  
    13.     }  
    14. };  
    15. int main()  
    16. {  
    17.     set<Info> s;  
    18.     Info info;  
    19.   
    20.     //插入三个元素  
    21.     info.name = "Jack";  
    22.     info.score = 80;  
    23.     s.insert(info);  
    24.     info.name = "Tom";  
    25.     info.score = 99;  
    26.     s.insert(info);  
    27.     info.name = "Steaven";  
    28.     info.score = 60;  
    29.     s.insert(info);  
    30.   
    31.     set<Info>::iterator it;  
    32.     for(it = s.begin(); it != s.end(); it++)  
    33.         cout << (*it).name << " : " << (*it).score << endl;   
    34.     return 0;  
    35. }  
    36. /* 
    37. 运行结果: 
    38. Tom : 99 
    39. Jack : 80 
    40. Steaven : 60 
    41. */ 

文章评论

做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
每天工作4小时的程序员
每天工作4小时的程序员
那些争议最大的编程观点
那些争议最大的编程观点
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我的丈夫是个程序员
我的丈夫是个程序员
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员必看的十大电影
程序员必看的十大电影
为什么程序员都是夜猫子
为什么程序员都是夜猫子
旅行,写作,编程
旅行,写作,编程
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
代码女神横空出世
代码女神横空出世
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
10个调试和排错的小建议
10个调试和排错的小建议
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
漫画:程序员的工作
漫画:程序员的工作
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员应该关注的一些事儿
程序员应该关注的一些事儿
中美印日四国程序员比较
中美印日四国程序员比较
总结2014中国互联网十大段子
总结2014中国互联网十大段子
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
如何成为一名黑客
如何成为一名黑客
老程序员的下场
老程序员的下场
Java程序员必看电影
Java程序员必看电影
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员都该阅读的书
程序员都该阅读的书
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
我是如何打败拖延症的
我是如何打败拖延症的
鲜为人知的编程真相
鲜为人知的编程真相
程序员的鄙视链
程序员的鄙视链
一个程序员的时间管理
一个程序员的时间管理
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有