|
set是STL中一種標(biāo)準(zhǔn)關(guān)聯(lián)容器（vector,list,string,deque都是序列容器，而set，multiset，map，multimap是標(biāo)準(zhǔn)關(guān)聯(lián)容器），它底層使用平衡的搜索樹——紅黑樹實(shí)現(xiàn)，插入刪除操作時(shí)僅僅需要指針操作節(jié)點(diǎn)即可完成，不涉及到內(nèi)存移動(dòng)和拷貝，所以效率比較高。set，顧名思義是“集合”的意思，在set中元素都是唯一的，而且默認(rèn)情況下會(huì)對(duì)元素自動(dòng)進(jìn)行升序排列，支持集合的交(set_intersection),差(set_difference) 并(set_union)，對(duì)稱差(set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允許重復(fù)那么可以使用multiset #include<set> #include<iterator> #include<iostream> using namespace std; int main() { set<int>eg1; //插入 eg1.insert(1); eg1.insert(100); eg1.insert(5); eg1.insert(1);//元素1因?yàn)橐呀?jīng)存在所以set中不會(huì)再次插入1 eg1.insert(10); eg1.insert(9); //遍歷set，可以發(fā)現(xiàn)元素是有序的 set<int>::iterator set_iter=eg1.begin(); cout<<"Set named eg1:"<<endl; for(;set_iter!=eg1.end();set_iter++) cout<<*set_iter<<" "; cout<<endl; //使用size()函數(shù)可以獲得當(dāng)前元素個(gè)數(shù) cout<<"Now there are "<<eg1.size()<<" elements in the set eg1"<<endl; if(eg1.find(200)==eg1.end())//find()函數(shù)可以查找元素是否存在 cout<<"200 isn't in the set eg1"<<endl; set<int>eg2; for(int i=6;i<15;i++) eg2.insert(i); cout<<"Set named eg2:"<<endl; for(set_iter=eg2.begin();set_iter!=eg2.end();set_iter++) cout<<*set_iter<<" "; cout<<endl; //獲得兩個(gè)set的并 set<int>eg3; cout<<"Union:"; set_union(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));//注意第五個(gè)參數(shù)的形式 copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," ")); cout<<endl; //獲得兩個(gè)set的交，注意進(jìn)行集合操作之前接收結(jié)果的set要調(diào)用clear()函數(shù)清空一下 eg3.clear(); set_intersection(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); cout<<"Intersection:"; copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," ")); cout<<endl; //獲得兩個(gè)set的差 eg3.clear(); set_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); cout<<"Difference:"; copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," ")); cout<<endl; //獲得兩個(gè)set的對(duì)稱差，也就是假設(shè)兩個(gè)集合分別為A和B那么對(duì)稱差為AUB-A∩B eg3.clear(); set_symmetric_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin())); copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," ")); cout<<endl; return 0; set會(huì)對(duì)元素進(jìn)行排序，那么問題也就出現(xiàn)了排序的規(guī)則是怎樣的呢？上面的示例代碼我們發(fā)現(xiàn)對(duì)int型的元素可以自動(dòng)判斷大小順序，但是對(duì)char*就不會(huì)自動(dòng)用strcmp進(jìn)行判斷了，更別說是用戶自定義的類型了，事實(shí)上set的標(biāo)準(zhǔn)形式是set<Key, Compare, Alloc>，
下面給出一個(gè)關(guān)鍵字類型為char*的示例代碼 #include<iostream> int main() set<const char*,ltstr> A(a, a + N); cout << "Set A: "; cout << "Union: "; cout << "Intersection: "; 其中的ltstr也可以這樣定義 更加通用的應(yīng)用方式那就是數(shù)據(jù)類型也是由用戶自定義的類來替代，比較的函數(shù)自定義，甚至可以加上二級(jí)比較，比如首先按照總分?jǐn)?shù)排序，對(duì)于分?jǐn)?shù)相同的按照id排序，下面是示例代碼 #include<set> return false; int main() /*
 set/multiset會(huì)根據(jù)待定的排序準(zhǔn)則，自動(dòng)將元素排序。兩者不同在于前者不允許元素重復(fù)，而后者允許。1) 不能直接改變?cè)刂?，因?yàn)槟菢訒?huì)打亂原本正確的順序，要改變?cè)刂当仨毾葎h除舊元素，則插入新元素2) 不提供直接存取元素的任何操作函數(shù)，只能通過迭代器進(jìn)行間接存取，而且從迭代器角度來看，元素值是常數(shù)3) 元素比較動(dòng)作只能用于型別相同的容器(即元素和排序準(zhǔn)則必須相同)set模板原型：//Key為元素(鍵值)類型template <class Key, class Compare=less<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) >從原型可以看出，可以看出比較函數(shù)對(duì)象及內(nèi)存分配器采用的是默認(rèn)參數(shù)，因此如果未指定，它們將采用系統(tǒng)默認(rèn)方式，另外，利用原型，可以有效地輔助分析創(chuàng)建對(duì)象的幾種方式 */ #include <iostream> #include <string>#include <set>using namespace std;struct strLess{ bool operator() (const char *s1, const char *s2) const { return strcmp(s1, s2) < 0; }};void printSet(set<int> s){copy(s.begin(), s.end(), ostream_iterator<int>(cout, ", ") );// set<int>::iterator iter;// for (iter = s.begin(); iter != s.end(); iter++)// //cout<<"set["<<iter-s.begin()<<"]="<<*iter<<", "; //Error// cout<<*iter<<", ";cout<<endl;}void main(){//創(chuàng)建set對(duì)象，共5種方式，提示如果比較函數(shù)對(duì)象及內(nèi)存分配器未出現(xiàn)，即表示采用的是系統(tǒng)默認(rèn)方式//創(chuàng)建空的set對(duì)象，元素類型為int，set<int> s1; //創(chuàng)建空的set對(duì)象，元素類型char*，比較函數(shù)對(duì)象(即排序準(zhǔn)則)為自定義strLessset<const char*, strLess> s2( strLess); //利用set對(duì)象s1,拷貝生成set對(duì)象s2set<int> s3(s1); //用迭代區(qū)間[&first, &last)所指的元素，創(chuàng)建一個(gè)set對(duì)象int iArray[] = {13, 32, 19};set<int> s4(iArray, iArray + 3);//用迭代區(qū)間[&first, &last)所指的元素，及比較函數(shù)對(duì)象strLess，創(chuàng)建一個(gè)set對(duì)象const char* szArray[] = {"hello", "dog", "bird" };set<const char*, strLess> s5(szArray, szArray + 3, strLess() );//元素插入：//1,插入value，返回pair配對(duì)對(duì)象，可以根據(jù).second判斷是否插入成功。(提示:value不能與set容器內(nèi)元素重復(fù))//pair<iterator, bool> insert(value)//2,在pos位置之前插入value，返回新元素位置，但不一定能插入成功//iterator insert(&pos, value)//3,將迭代區(qū)間[&first, &last)內(nèi)所有的元素，插入到set容器//void insert[&first, &last)cout<<"s1.insert() : "<<endl;for (int i = 0; i <5 ; i++) s1.insert(i*10);printSet(s1);cout<<"s1.insert(20).second = "<<endl;;if (s1.insert(20).second) cout<<"Insert OK!"<<endl;else cout<<"Insert Failed!"<<endl;cout<<"s1.insert(50).second = "<<endl;if (s1.insert(50).second){cout<<"Insert OK!"<<endl; printSet(s1);}else cout<<"Insert Failed!"<<endl;cout<<"pair<set<int>::iterator::iterator, bool> p;\np = s1.insert(60);\nif (p.second):"<<endl;pair<set<int>::iterator::iterator, bool> p;p = s1.insert(60);if (p.second){cout<<"Insert OK!"<<endl; printSet(s1);}else cout<<"Insert Failed!"<<endl;//元素刪除//1,size_type erase(value) 移除set容器內(nèi)元素值為value的所有元素，返回移除的元素個(gè)數(shù)//2,void erase(&pos) 移除pos位置上的元素，無返回值//3,void erase(&first, &last) 移除迭代區(qū)間[&first, &last)內(nèi)的元素，無返回值//4,void clear()， 移除set容器內(nèi)所有元素cout<<"\ns1.erase(70) = "<<endl;s1.erase(70);printSet(s1);cout<<"s1.erase(60) = "<<endl;s1.erase(60);printSet(s1);cout<<"set<int>::iterator iter = s1.begin();\ns1.erase(iter) = "<<endl;set<int>::iterator iter = s1.begin();s1.erase(iter);printSet(s1);//元素查找//count(value)返回set對(duì)象內(nèi)元素值為value的元素個(gè)數(shù)//iterator find(value)返回value所在位置，找不到value將返回end()//lower_bound(value),upper_bound(value), equal_range(value) 略cout<<"\ns1.count(10) = "<<s1.count(10)<<", s1.count(80) = "<<s1.count(80)<<endl;cout<<"s1.find(10) : ";if (s1.find(10) != s1.end()) cout<<"OK!"<<endl;else cout<<"not found!"<<endl;cout<<"s1.find(80) : ";if (s1.find(80) != s1.end()) cout<<"OK!"<<endl;else cout<<"not found!"<<endl;//其它常用函數(shù)cout<<"\ns1.empty()="<<s1.empty()<<", s1.size()="<<s1.size()<<endl;set<int> s9;s9.insert(100);cout<<"s1.swap(s9) :"<<endl;s1.swap(s9);cout<<"s1: "<<endl;printSet(s1);cout<<"s9: "<<endl;printSet(s9);//lower_bound,upper_bound,equal_range(略)}///////////////i測(cè)試結(jié)果/////////////////////////s1.insert() :0, 10, 20, 30, 40,s1.insert(20).second =Insert Failed!s1.insert(50).second =Insert OK!0, 10, 20, 30, 40, 50,pair<set<int>::iterator::iterator, bool> p;p = s1.insert(60);if (p.second):Insert OK!0, 10, 20, 30, 40, 50, 60,s1.erase(70) =0, 10, 20, 30, 40, 50, 60,s1.erase(60) =0, 10, 20, 30, 40, 50,set<int>::iterator iter = s1.begin();s1.erase(iter) =10, 20, 30, 40, 50,s1.count(10) = 1, s1.count(80) = 0s1.find(10) : OK!s1.find(80) : not found!s1.empty()=0, s1.size()=5s1.swap(s9) :s1:100,s9:10, 20, 30, 40, 50, |
|
|
