轉(zhuǎn)載自：http://blog.csdn.net/LYHVOYAGE/article/details/22989659

set集合容器實(shí)現(xiàn)了紅黑樹(shù)（Red-Black Tree）的平衡二叉檢索樹(shù)的的數(shù)據(jù)結(jié)構(gòu)， 在插入元素時(shí)，它會(huì)自動(dòng)調(diào)整二叉樹(shù)的排列，把該元素放到適當(dāng)?shù)奈恢?#xff0c;以確保每個(gè)子樹(shù)根節(jié)點(diǎn)的鍵值大于左子樹(shù)所有節(jié)點(diǎn)的鍵值，而小于右子樹(shù)所有節(jié)點(diǎn)的鍵值； 另外，還得確保根節(jié)點(diǎn)的左子樹(shù)的高度與有字?jǐn)?shù)的高度相等，這樣，二叉樹(shù)的高度最小，從而檢索速度最快。要注意的是，它不會(huì)重復(fù)插入相同鍵值的元素，而采取 忽略處理。

? ? ? ? 平衡二叉檢索樹(shù)的檢索使用中序遍歷算法，檢索效率高于vector、deque、和list的容器。另外，采用中序遍歷算法可將鍵值由小到大遍歷出來(lái)，所以，可以理解為平衡二叉檢索樹(shù)在插入元素時(shí)，就會(huì)自動(dòng)將元素按鍵值從小到大的順序排列。

? ? ? ? 構(gòu)造set集合的主要目的是為了快速檢索，使用set前，需要在程序頭文件中包含聲明“#include<set>”。

1.創(chuàng)建set集合對(duì)象

? ? ? ? ? ?創(chuàng)建set對(duì)象時(shí)，需要指定元素的類(lèi)型，這一點(diǎn)和其他容器一樣。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

int?main()??

{??

????set<int>?s;??

????return?0;??

}??

2.元素的插入與中序遍歷

? ? ? ? 采用inset()方法把元素插入到集合中，插入規(guī)則在默認(rèn)的比較規(guī)則下，是按元素值從小到大插入，如果自己指定了比較規(guī)則函數(shù)，則按自定義比較規(guī)則函數(shù)插入。使用前向迭代器對(duì)集合中序遍歷，結(jié)果正好是元素排序后的結(jié)果。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

int?main()??

{??

????set<int>?s;??

????s.insert(5);?//第一次插入5，可以插入??

????s.insert(1);??

????s.insert(6);??

????s.insert(3);??

????s.insert(5);?//第二次插入5，重復(fù)元素，不會(huì)插入??

????set<int>::iterator?it;?//定義前向迭代器??

????//中序遍歷集合中的所有元素??

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

????{??

????????cout?<<?*it?<<?"?";??

????}??

????cout?<<?endl;??

????return?0;??

}??

//運(yùn)行結(jié)果：1?3?5?6??

3.元素的方向遍歷

? ? ? ? 使用反向迭代器reverse_iterator可以反向遍歷集合，輸出的結(jié)果正好是集合元素的反向排序結(jié)果。它需要用到rbegin()和rend()兩個(gè)方法，它們分別給出了反向遍歷的開(kāi)始位置和結(jié)束位置。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

int?main()??

{??

????set<int>?s;??

????s.insert(5);?//第一次插入5，可以插入??

????s.insert(1);??

????s.insert(6);??

????s.insert(3);??

????s.insert(5);?//第二次插入5，重復(fù)元素，不會(huì)插入??

????set<int>::reverse_iterator?rit;?//定義反向迭代器??

????//反向遍歷集合中的所有元素??

????for(rit?=?s.rbegin();?rit?!=?s.rend();?rit++)??

????{??

????????cout?<<?*rit?<<?"?";??

????}??

????cout?<<?endl;??

????return?0;??

}??

//運(yùn)行結(jié)果：6?5?3?1??

4.元素的刪除

? ? ? ? 與插入元素的處理一樣，集合具有高效的刪除處理功能，并自動(dòng)重新調(diào)整內(nèi)部的紅黑樹(shù)的平衡。刪除的對(duì)象可以是某個(gè)迭代器位置上的元素、等于某鍵值的元素、一個(gè)區(qū)間上的元素和清空集合。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

int?main()??

{??

????set<int>?s;??

????s.insert(5);?//第一次插入5，可以插入??

????s.insert(1);??

????s.insert(6);??

????s.insert(3);??

????s.insert(5);?//第二次插入5，重復(fù)元素，不會(huì)插入??

????s.erase(6);?//刪除鍵值為6的元素??

????set<int>::reverse_iterator?rit;?//定義反向迭代器??

????//反向遍歷集合中的所有元素??

????for(rit?=?s.rbegin();?rit?!=?s.rend();?rit++)??

????{??

????????cout?<<?*rit?<<?"?";??

????}??

????cout?<<?endl;???

????set<int>::iterator?it;??

??

????it?=?s.begin();??

????for(int?i?=?0;?i?<?2;?i++)??

????????it?=?s.erase(it);???

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

????????cout?<<?*it?<<?"?";??

????cout?<<?endl;??

??

????s.clear();??

????cout?<<?s.size()?<<?endl;??

??

????return?0;??

}??

/*?

運(yùn)行結(jié)果：?

5?3?1?

5?

0?????

*/??

5.元素的檢索

? ? ? ? ? 使用find()方法對(duì)集合進(jìn)行檢索，如果找到查找的的鍵值，則返回該鍵值的迭代器位置；否則，返回集合最后一個(gè)元素后面的一個(gè)位置，即end()。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

int?main()??

{??

????set<int>?s;??

????s.insert(5);?//第一次插入5，可以插入??

????s.insert(1);??

????s.insert(6);??

????s.insert(3);??

????s.insert(5);?//第二次插入5，重復(fù)元素，不會(huì)插入??

????set<int>::iterator?it;??

????it?=?s.find(6);?//查找鍵值為6的元素??

????if(it?!=?s.end())??

????????cout?<<?*it?<<?endl;??

????else??

????????cout?<<?"not?find?it"?<<?endl;??

????it?=?s.find(20);??

????if(it?!=?s.end())??

????????cout?<<?*it?<<?endl;??

????else??

????????cout?<<?"not?find?it"?<<?endl;??

????return?0;??

}??

/*?

運(yùn)行結(jié)果：?

6?

not?find?it????

*/??

下面這種方法也能判斷一個(gè)數(shù)是否在集合中：

[cpp] view plaincopy

#include?<cstdio>??

#include?<set>??

using?namespace?std;??

int?main()?{??

????set?<int>?s;??

????int?a;??

????for(int?i?=?0;?i?<?10;?i++)??

????????s.insert(i);??

????for(int?i?=?0;?i?<?5;?i++)?{??

????????scanf("%d",?&a);??

????????if(!s.count(a))?//不存在??

????????????printf("does?not?exist\n");??

????????else??

????????????printf("exist\n");??

????}??

????return?0;??

}??

6.自定義比較函數(shù)

? ? ? ? ?使用insert將元素插入到集合中去的時(shí)候，集合會(huì)根據(jù)設(shè)定的比較函數(shù)獎(jiǎng)該元素放到該放的節(jié)點(diǎn)上去。在定義集合的時(shí)候，如果沒(méi)有指定比較函數(shù)，那么采用默認(rèn)的比較函數(shù)，即按鍵值從小到大的順序插入元素。但在很多情況下，需要自己編寫(xiě)比較函數(shù)。

編寫(xiě)比較函數(shù)有兩種方法。

(1)如果元素不是結(jié)構(gòu)體，那么可以編寫(xiě)比較函數(shù)。下面的程序比較規(guī)則為按鍵值從大到小的順序插入到集合中。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

using?namespace?std;??

struct?mycomp??

{?//自定義比較函數(shù)，重載“（）”操作符??

????bool?operator()?(const?int?&a,?const?int?&b)??

????{??

????????if(a?!=?b)??

????????????return?a?>?b;??

????????else??

????????????return?a?>?b;??

????}??

};??

int?main()??

{??

????set<int,?mycomp>?s;?//采用比較函數(shù)mycomp??

????s.insert(5);?//第一次插入5，可以插入??

????s.insert(1);??

????s.insert(6);??

????s.insert(3);??

????s.insert(5);?//第二次插入5，重復(fù)元素，不會(huì)插入??

????set<int,mycomp>::iterator?it;??

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

????????cout?<<?*it?<<?"?";??

????cout?<<?endl;??

????return?0;??

}??

/*?

運(yùn)行結(jié)果：6?5?3?1???

*/??

(2)如果元素是結(jié)構(gòu)體，那么可以直接把比較函數(shù)寫(xiě)在結(jié)構(gòu)體內(nèi)。

[cpp] view plaincopy

#include<iostream>??

#include<set>??

#include<string>??

using?namespace?std;??

struct?Info??

{??

????string?name;??

????double?score;??

????bool?operator?<?(const?Info?&a)?const?//?重載“<”操作符，自定義排序規(guī)則??

????{??

????????//按score由大到小排序。如果要由小到大排序，使用“>”即可。??

????????return?a.score?<?score;??

????}??

};??

int?main()??

{??

????set<Info>?s;??

????Info?info;??

??

????//插入三個(gè)元素??

????info.name?=?"Jack";??

????info.score?=?80;??

????s.insert(info);??

????info.name?=?"Tom";??

????info.score?=?99;??

????s.insert(info);??

????info.name?=?"Steaven";??

????info.score?=?60;??

????s.insert(info);??

??

????set<Info>::iterator?it;??

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

????????cout?<<?(*it).name?<<?"?:?"?<<?(*it).score?<<?endl;???

????return?0;??

}??

/*?

運(yùn)行結(jié)果：?

Tom?:?99?

Jack?:?80?

Steaven?:?60?

*/?

轉(zhuǎn)載于:https://www.cnblogs.com/PrayG/p/5719600.html

總結(jié)

以上是生活随笔為你收集整理的STL -set的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。