背景開發：核心技術與應用實踐3.5.1 set是什麼

<b>3.5　set</b>

<b></b>

<b>3.5.1　set是什麼</b>

c++ stl之是以得到廣泛的贊譽，也被很多人使用，不隻是提供了像vector、string、list等友善的容器，更重要的是stl封裝了許多複雜的資料結構算法和大量

常用資料結構操作。vector封裝數組，list封裝了連結清單，map和set封裝了二叉樹等，在封裝這些資料結構的時候，stl按照程式員的使用習慣，以成員函數方式提供的常用操作，如：插入、排序、删除、查找等。讓使用者在stl使用過程中，并不會感到陌生。

關于set，必須說明的是set關聯式容器。set作為一個容器也是用來存儲同一資料類型的資料類型，并且能從一個資料集合中取出資料，在set中每個元素的值都唯一的，而且系統能根據元素的值自動進行排序。應該注意的是set中數元素的值不能直接被改變。c++

stl中标準關聯容器set、multiset、map、multimap内部采用的都是紅黑樹。紅黑樹的統計性能要好于一般平衡二叉樹，是以被stl選擇作為了關聯容器的内部結構。

關于set有下面幾個問題需要注意。

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

表面上看，因為對于關聯容器來說，不需要做記憶體拷貝和記憶體移動。set容器内所有元素都是以節點的方式來存儲，其節點結構和連結清單差不多，指向父節點和子節點，set的結構圖如圖3-6所示。

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

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

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

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

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