STL中的set容器的一點總結

1.關于set

C++ STL 之是以得到廣泛的贊譽，也被很多人使用，不隻是提供了像vector, string, list等友善的容器，更重要的是STL封裝了許多複雜的資料結構算法和大量常用資料結構操作。vector封裝數組，list封裝了連結清單，map和set封裝了二叉樹等，在封裝這些資料結構的時候，STL按照程式員的使用習慣，以成員函數方式提供的常用操作，如：插入、排序、删除、查找等。讓使用者在STL使用過程中，并不會感到陌生。

關于set，必須說明的是set關聯式容器。set作為一個容器也是用來存儲同一資料類型的資料類型，并且能從一個資料集合中取出資料，在set中每個元素的值都唯一，而且系統能根據元素的值自動進行排序。應該注意的是set中數元素的值不能直接被改變。C++ STL中标準關聯容器set, multiset, map, multimap内部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統計性能要好于一般平衡二叉樹，是以被STL選擇作為了關聯容器的内部結構。

 關于set有下面幾個問題：

（1）為何map和set的插入删除效率比用其他序列容器高？

大部分人說，很簡單，因為對于關聯容器來說，不需要做記憶體拷貝和記憶體移動。說對了，确實如此。set容器内所有元素都是以節點的方式來存儲，其節點結構和連結清單差不多，指向父節點和子節點。結構圖可能如下：

　　A

  / \

B C

/ \ / \

  D E F G

是以插入的時候隻需要稍做變換，把節點的指針指向新的節點就可以了。删除的時候類似，稍做變換後把指向删除節點的指針指向其他節點也OK了。這裡的一切操作就是指針換來換去，和記憶體移動沒有關系。

（2）為何每次insert之後，以前儲存的iterator不會失效？

iterator這裡就相當于指向節點的指針，記憶體沒有變，指向記憶體的指針怎麼會失效呢(當然被删除的那個元素本身已經失效了)。相對于vector來說，每一次删除和插入，指針都有可能失效，調用push_back在尾部插入也是如此。因為為了保證内部資料的連續存放，iterator指向的那塊記憶體在删除和插入過程中可能已經被其他記憶體覆寫或者記憶體已經被釋放了。即使時push_back的時候，容器内部空間可能不夠，需要一塊新的更大的記憶體，隻有把以前的記憶體釋放，申請新的更大的記憶體，複制已有的資料元素到新的記憶體，最後把需要插入的元素放到最後，那麼以前的記憶體指針自然就不可用了。特别時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。

（3）當資料元素增多時，set的插入和搜尋速度變化如何？

如果你知道log2的關系你應該就徹底了解這個答案。在set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結果，有32個元素，最多比較5次。那麼有10000個呢？最多比較的次數為log10000，最多為14次，如果是20000個元素呢？最多不過15次。看見了吧，當資料量增大一倍的時候，搜尋次數隻不過多了1次，多了1/14的搜尋時間而已。你明白這個道理後，就可以安心往裡面放入元素了。

2.set中常用的方法

begin()     　　 ,傳回set容器的第一個元素

end() 　　　　 ,傳回set容器的最後一個元素

clear()   　　     ,删除set容器中的所有的元素

empty() 　　　,判斷set容器是否為空

max_size() 　 ,傳回set容器可能包含的元素最大個數

size() 　　　　 ,傳回目前set容器中的元素個數

rbegin　　　　 ,傳回的值和end()相同

rend()　　　　 ,傳回的值和rbegin()相同

寫一個程式練一練這幾個簡單操作吧： 

View Code

運作結果：

小結：插入3之後雖然插入了一個1，但是我們發現set中最後一個值仍然是3哈，這就是set 。還要注意begin() 和 end()函數是不檢查set是否為空的，使用前最好使用empty()檢驗一下set是否為空.

count() 用來查找set中某個某個鍵值出現的次數。這個函數在set并不是很實用，因為一個鍵值在set隻可能出現0或1次，這樣就變成了判斷某一鍵值是否在set出現過了。

示例代碼：

equal_range() ，傳回一對定位器，分别表示第一個大于或等于給定關鍵值的元素和 第一個大于給定關鍵值的元素，這個傳回值是一個pair類型，如果這一對定位器中哪個傳回失敗，就會等于end()的值。具體這個有什麼用途我還沒遇到過~~~

erase(iterator)  ,删除定位器iterator指向的值

erase(first,second),删除定位器first和second之間的值

erase(key_value),删除鍵值key_value的值

看看程式吧：

小結：set中的删除操作是不進行任何的錯誤檢查的，比如定位器的是否合法等等，是以用的時候自己一定要注意。

find()  ，傳回給定值值得定位器，如果沒找到則傳回end()。

insert(key_value); 将key_value插入到set中 ，傳回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已經在set中，則iterator表示的key_value在set中的位置。

inset(first,second);将定位器first到second之間的元素插入到set中，傳回值是void.

lower_bound(key_value) ，傳回第一個大于等于key_value的定位器

upper_bound(key_value)，傳回最後一個大于等于key_value的定位器