一、set和multiset基礎

set和multiset會根據特定的排序準則，自動將元素進行排序。不同的是后者允許元素重復而前者不允許。

需要包含頭文件：

#include <set>

set和multiset都是定義在std空間里的類模板：

1 template<class _Kty, 2 class _Pr = less<_Kty>, 3 class _Alloc = allocator<_Kty> > 4 class set 1 template<class _Kty, 2 class _Pr = less<_Kty>, 3 class _Alloc = allocator<_Kty> > 4 class multiset

?

只要是可復賦值、可拷貝、可以根據某個排序準則進行比較的型別都可以成為它們的元素。第二個參數用來定義排序準則。缺省準則less是一個仿函數，以operator<對元素進行比較。

?

所謂排序準則，必須定義strict weak ordering，其意義如下：

1、必須使反對稱的。

對operator<而言，如果x<y為真，則y<x為假。

2、必須使可傳遞的。

對operator<而言，如果x<y為真，且y<z為真，則x<z為真。

3、必須是非自反的。

對operator<而言，x<x永遠為假。

因為上面的這些特性，排序準則可以用于相等性檢驗，就是說，如果兩個元素都不小于對方，則它們相等。

?

二、set和multiset的功能

和所有關聯式容器類似，通常使用平衡二叉樹完成。事實上，set和multiset通常以紅黑樹實作而成。

自動排序的優點是使得搜尋元素時具有良好的性能，具有對數時間復雜度。但是造成的一個缺點就是：

不能直接改變元素值。因為這樣會打亂原有的順序。

改變元素值的方法是：先刪除舊元素，再插入新元素。

存取元素只能通過迭代器，從迭代器的角度看，元素值是常數。

?

三、操作函數

構造函數和析構函數

set的形式可以是：

有兩種方式可以定義排序準則：

1、以template參數定義：

?1 set<int,greater<int>> col1;?

此時，排序準則就是型別的一部分。型別系統確保只有排序準則相同的容器才能被合并。

程序實例：

?

1 #include <iostream> 2 #include <set> 3 using namespace std; 4 5 int main() 6 { 7 set<int> s1; 8 set<int,greater<int> > s2; 9 10 for (int i = 1;i < 6;++i) 11 { 12 s1.insert(i); 13 s2.insert(i); 14 } 15 if(s1 == s2) 16 cout << "c1 equals c2 !" << endl; 17 else 18 cout << "c1 not equals c2 !" << endl; 19 }

?

程序運行會報錯。但是如果把s1的排序準則也指定為greater<int>便運行成功。

?

2、以構造函數參數定義。

這種情況下，同一個型別可以運用不同的排序準則，而排序準則的初始值或狀態也可以不同。如果執行期才獲得排序準則，而且需要用到不同的排序準則，這種方式可以派上用場。

程序實例：

?

1 #include <iostream> 2 #include "print.hpp" 3 #include <set> 4 using namespace std; 5 6 template <class T> 7 class RuntimeCmp{ 8 public: 9 enum cmp_mode{normal,reverse}; 10 private: 11 cmp_mode mode; 12 public: 13 RuntimeCmp(cmp_mode m = normal):mode(m){} 14 15 bool operator()(const T &t1,const T &t2) 16 { 17 return mode == normal ? t1 < t2 : t2 < t1; 18 } 19 20 bool operator==(const RuntimeCmp &rc) 21 { 22 return mode == rc.mode; 23 } 24 }; 25 26 typedef set<int,RuntimeCmp<int> > IntSet; 27 28 void fill(IntSet& set); 29 30 int main() 31 { 32 IntSet set1; 33 fill(set1); 34 PRINT_ELEMENTS(set1,"set1:"); 35 36 RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse); 37 38 IntSet set2(reverse_order); 39 fill(set2); 40 PRINT_ELEMENTS(set2,"set2:"); 41 42 set1 = set2;//assignment:OK 43 set1.insert(3); 44 PRINT_ELEMENTS(set1,"set1:"); 45 46 if(set1.value_comp() == set2.value_comp())//value_comp <span style="font-family: verdana, arial, helvetica, sans-serif; ">Returns the comparison object associated with the container</span> 47 cout << "set1 and set2 have the same sorting criterion" << endl; 48 else 49 cout << "set1 and set2 have the different sorting criterion" << endl; 50 } 51 52 void fill(IntSet &set) 53 { 54 set.insert(4); 55 set.insert(7); 56 set.insert(5); 57 set.insert(1); 58 set.insert(6); 59 set.insert(2); 60 set.insert(5); 61 }

?

運行結果：

?

?

雖然set1和set2的而比較準則本身不同，但是型別相同，所以可以進行賦值操作。

?

?

非變動性操作

注意：元素比較操作只能用于型別相同的容器。

特殊的搜尋函數

賦值

賦值操作兩端的容器必須具有相同的型別，但是比較準則本身可以不同，但是其型別必須相同。如果比較準則的不同，準則本身也會被賦值或交換。

迭代器相關函數

元素的插入和刪除

注意：插入函數的返回值不完全相同。

set提供的插入函數：

pair<iterator,bool> insert(const value_type& elem); iterator insert(iterator pos_hint, const value_type& elem);

?

multiset提供的插入函數：

iterator insert(const value_type& elem); iterator insert(iterator pos_hint, const value_type& elem);

?

返回值型別不同的原因是set不允許元素重復，而multiset允許。當插入的元素在set中已經包含有同樣值的元素時，插入就會失敗。所以set的返回值型別是由pair組織起來的兩個值：

?

第一個元素返回新元素的位置，或返回現存的同值元素的位置。第二個元素表示插入是否成功。

set的第二個insert函數，如果插入失敗，就只返回重復元素的位置！

但是，所有擁有位置提示參數的插入函數的返回值型別是相同的。這樣就確保了至少有了一個通用型的插入函數，在各種容器中有共通接口。

?

注意：還有一個返回值不同的情況是：作用于序列式容器和關聯式容器的erase()函數：

序列式容器的erase()函數：

?

iterator erase(iterator pos); iterator erase(iterator beg, iterator end);

?

關聯式容器的erase()函數：

void erase(iterator pos); void erase(iterator beg, iterator end);

?

這完全是為了性能的考慮。因為關聯式容器都是由二叉樹實現，搜尋某元素并返回后繼元素可能很費時。

五、set應用示例：

?

1 #include <iostream> 2 #include <set> 3 using namespace std; 4 5 int main() 6 { 7 typedef set<int,greater<int> > IntSet; 8 IntSet s1; 9 10 s1.insert(4); 11 s1.insert(3); 12 s1.insert(5); 13 s1.insert(1); 14 s1.insert(6); 15 s1.insert(2); 16 s1.insert(5); 17 //the inserted element that has the same value with a element existed is emitted 18 19 copy(s1.begin(),s1.end(),ostream_iterator<int>(cout," ")); 20 cout << endl << endl; 21 22 pair<IntSet::iterator,bool> status = s1.insert(4); 23 if(status.second) 24 cout << "4 is inserted as element " 25 << distance(s1.begin(),status.first) + 1 << endl; 26 else 27 cout << "4 already exists in s1" << endl; 28 copy(s1.begin(),s1.end(),ostream_iterator<int>(cout," ")); 29 cout << endl << endl; 30 31 set<int> s2(s1.begin(),s1.end());//default sort criterion is less< 32 copy(s2.begin(),s2.end(),ostream_iterator<int>(cout," ")); 33 cout << endl << endl; 34 }

?

上述程序最后新產生一個set：s2，默認排序準則是less。以s1的元素作為初值。

?

注意：s1和s2有不同的排序準則，所以他們的型別不同，不能直接進行相互賦值或比較。

運行結果：

轉載于:https://www.cnblogs.com/ECJTUACM-873284962/p/6759537.html

總結

以上是生活随笔為你收集整理的C++ STL学习之容器set和multiset (补充材料)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。