或許有得人能回答出來大概原因，但要徹底明白，還需要了解STL的底層數(shù)據(jù)結(jié)構(gòu)。

C++ STL 之所以得到廣泛的贊譽，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封裝了許多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算法和大量常用數(shù)據(jù)結(jié)構(gòu)操作。vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時候，STL按照程序員的使用習(xí)慣，以成員函數(shù)方式提供的常用操作，如：插入、排序、刪除、查找等。讓用戶在STL使用過程中，并不會感到陌生。

C++ STL中標準關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-Black Tree)。RB樹的統(tǒng)計性能要好于一般的平衡二叉樹(有些書籍根據(jù)作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。本文并不會介紹詳細AVL樹和RB樹的實現(xiàn)以及他們的優(yōu)劣，關(guān)于RB樹的詳細實現(xiàn)參看紅黑樹: 理論與實現(xiàn)(理論篇)。本文針對開始提出的幾個問題的回答，來向大家簡單介紹map和set的底層數(shù)據(jù)結(jié)構(gòu)。

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

大部分人說，很簡單，因為對于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動。說對了，確實如此。map和set容器內(nèi)所有元素都是以節(jié)點的方式來存儲，其節(jié)點結(jié)構(gòu)和鏈表差不多，指向父節(jié)點和子節(jié)點。結(jié)構(gòu)圖可能如下：

            A
           / \
          B   C
         / \ / \
        D  E F  G

因此插入的時候只需要稍做變換，把節(jié)點的指針指向新的節(jié)點就可以了。刪除的時候類似，稍做變換后把指向刪除節(jié)點的指針指向其他節(jié)點就OK了。這里的一切操作就是指針換來換去，和內(nèi)存移動沒有關(guān)系。

為何每次insert之后，以前保存的iterator不會失效？

看見了上面答案的解釋，你應(yīng)該已經(jīng)可以很容易解釋這個問題。iterator這里就相當于指向節(jié)點的指針，內(nèi)存沒有變，指向內(nèi)存的指針怎么會失效呢(當然被刪除的那個元素本身已經(jīng)失效了)。相對于vector來說，每一次刪除和插入，指針都有可能失效，調(diào)用push_back在尾部插入也是如此。因為為了保證內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了。即使時push_back的時候，容器內(nèi)部空間可能不夠，需要一塊新的更大的內(nèi)存，只有把以前的內(nèi)存釋放，申請新的更大的內(nèi)存，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后，那么以前的內(nèi)存指針自然就不可用了。特別時在和find等算法在一起使用的時候，牢記這個原則：不要使用過期的iterator。

為何map和set不能像vector一樣有個reserve函數(shù)來預(yù)分配數(shù)據(jù)？

我以前也這么問，究其原理來說時，引起它的原因在于在map和set內(nèi)部存儲的已經(jīng)不是元素本身了，而是包含元素的節(jié)點。也就是說map內(nèi)部使用的Alloc并不是map<Key, Data, Compare, Alloc>聲明的時候從參數(shù)中傳入的Alloc。例如：

map<int, int, less<int>, Alloc<int> > intmap;

這時候在intmap中使用的allocator并不是Alloc<int>, 而是通過了轉(zhuǎn)換的Alloc，具體轉(zhuǎn)換的方法時在內(nèi)部通過Alloc<int>::rebind重新定義了新的節(jié)點分配器，詳細的實現(xiàn)參看徹底學(xué)習(xí)STL中的Allocator。其實你就記住一點，在map和set內(nèi)面的分配器已經(jīng)發(fā)生了變化，reserve方法你就不要奢望了。

當數(shù)據(jù)元素增多時（10000和20000個比較），map和set的插入和搜索速度變化如何？

如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個答案。在map和set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結(jié)果，有32個元素，最多比較5次。那么有10000個呢？最多比較的次數(shù)為log10000，最多為14次，如果是20000個元素呢？最多不過15次?？匆娏税?，當數(shù)據(jù)量增大一倍的時候，搜索次數(shù)只不過多了1次，多了1/14的搜索時間而已。你明白這個道理后，就可以安心往里面放入元素了。

最后，對于map和set Winter還要提的就是它們和一個c語言包裝庫的效率比較。在許多unix和linux平臺下，都有一個庫叫isc，里面就提供類似于以下聲明的函數(shù):

void tree_init(void **tree);
void *tree_srch(void **tree, int (*compare)(), void *data);
void tree_add(void **tree, int (*compare)(), void *data, void (*del_uar)());
int tree_delete(void **tree, int (*compare)(), void *data,void (*del_uar)());
int tree_trav(void **tree, int (*trav_uar)());
void tree_mung(void **tree, void (*del_uar)());

許多人認為直接使用這些函數(shù)會比STL map速度快，因為STL map中使用了許多模板什么的。其實不然，它們的區(qū)別并不在于算法，而在于內(nèi)存碎片。如果直接使用這些函數(shù)，你需要自己去new一些節(jié)點，當節(jié)點特別多，而且進行頻繁的刪除和插入的時候，內(nèi)存碎片就會存在，而STL采用自己的Allocator分配內(nèi)存，以內(nèi)存池的方式來管理這些內(nèi)存，會大大減少內(nèi)存碎片，從而會提升系統(tǒng)的整體性能。Winter在自己的系統(tǒng)中做過測試，把以前所有直接用isc函數(shù)的代碼替換成map，程序速度基本一致。當時間運行很長時間后（例如后臺服務(wù)程序），map的優(yōu)勢就會體現(xiàn)出來。從另外一個方面講，使用map會大大降低你的編碼難度，同時增加程序的可讀性。何樂而不為？