STL中map、set的數(shù)據(jù)結(jié)構(gòu)及底層實現(xiàn)

1、STL 中 map. set 的據(jù)結(jié)構(gòu)及底層實摘要：本文列出幾個基本的STL map和STL set的問題，通過解答這些問題講解了 STL關(guān) 聯(lián)容器內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，最后提出了關(guān)于UNIX/LINUX自帶平衡二叉樹庫函數(shù)和map, set 選擇問題，并分析了 map, set的優(yōu)勢之處。對于希望深入學(xué)習(xí)STL和希望了解STL map 等關(guān)聯(lián)容器底層數(shù)據(jù)結(jié)構(gòu)的朋友來說，有一定的參考價值。vector （向量）STL中標(biāo)準(zhǔn)而安全的數(shù)組。只能在vector的“前面”增加數(shù)據(jù)。deque（雙端隊列double-ended queue） 功能上和vector相似，但是可以在前后兩端向其中添加數(shù)據(jù)。list

2、 （列表）一標(biāo)一次只可以移動一步。如果你對鏈表已經(jīng)很熟悉，那么STL中的list 則是一個雙向鏈表（每個節(jié)點有指向前驅(qū)和指向后繼的兩個指針）。set （集合）一包含了經(jīng)過排序了的數(shù)據(jù)，這些數(shù)據(jù)的值（value）必須是唯一的。map （映射）一 過排序了的二元組的集合，map中的每個元素都是由兩個值組成，其 中的key （鍵值，一個map中的鍵值必須是唯一的）是在排序或搜索時使用，它的值可以 在容器中重新獲??；而另一個值是該元素關(guān)聯(lián)的數(shù)值。比如，除了可以ar43 = overripe 這樣找到一個數(shù)據(jù)，map還可以通過arbanana = overripe，這樣的方法找到一個數(shù)據(jù)。 如果你想獲得

3、其中的元素信息，通過輸入元素的全名就可以輕松實現(xiàn)。multiset （多重集）一和集合（set）相似，然而其中的值不要求必須是唯一的（即可以 有重復(fù)）。multimap （多重映射）一和映射（map）相似，然而其中的鍵值不要求必須是唯一的（即 可以有重復(fù)）。STL map和set的使用雖不復(fù)雜，但也有一些不易理解的地方，如：#為何map和set的插入刪除效率比用其他序列容器高？#為何每次insert之后，以前保存的iterator不會失效？#為何map和set不能像vector 一樣有個reserve函數(shù)來預(yù)分配數(shù)據(jù)？#當(dāng)數(shù)據(jù)元素增多時（10000到20000個比較），map和set的插入和搜

4、索速度變化如何？或許有得人能回答出來大概原因，但要徹底明白，還需要了解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中標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部

5、采用的就是一種非常高效的平 衡檢索二叉樹：紅黑樹，也成為RB樹（Red-Black Tree）。RB樹的統(tǒng)計性能要好于一般的 平衡二叉樹（有些書籍根據(jù)作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹），所以 被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。本文并不會介紹詳細(xì)AVL樹和RB樹的實現(xiàn)以及 他們的優(yōu)劣，關(guān)于RB樹的詳細(xì)實現(xiàn)參看紅黑樹：理論與實現(xiàn)（理論篇）。本文針對開始提出 的幾個問題的回答，來向大家簡單介紹map和set的底層數(shù)據(jù)結(jié)構(gòu)。為何map和set的插入刪除效率比用其他序列容器高？大部分人說，很簡單，因為對于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動。說對了，確

6、實如此。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這里就相當(dāng)于指向 節(jié)點的指針，內(nèi)存沒有變，指向內(nèi)存的指針怎么會失效呢(當(dāng)然被刪除的那個元素本身已經(jīng) 失效了)。相

7、對于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函

8、數(shù)來預(yù)分配數(shù)據(jù)？我以前也這么問，究其原理來說時，引起它的原因在于在map和set內(nèi)部存儲的已經(jīng)不是 元素本身了，而是包含元素的節(jié)點。也就是說map內(nèi)部使用的Alloc并不是map聲明的時候從參數(shù)中傳入的Alloc。例如：mapint, int, less, Alloc intmap;這時候在intmap中使用的allocator并不是Alloc,而是通過了轉(zhuǎn)換的Alloc，具體轉(zhuǎn)換 的方法時在內(nèi)部通過Alloc:rebind重新定義了新的節(jié)點分配器，詳細(xì)的實現(xiàn)參看徹底 學(xué)習(xí)STL中的Allocator。其實你就記住一點，在map和set內(nèi)面的分配器已經(jīng)發(fā)生了變化， reserve方法你就不要奢

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

10、效率比較。在許多 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(voi

11、d *tree, int (*trav_uar)();void tree_mung(void *tree, void (*del_uar)();許多人認(rèn)為直接使用這些函數(shù)會比STL map速度快，因為STL map中使用了許多模板什 么的。其實不然，它們的區(qū)別并不在于算法，而在于內(nèi)存碎片。如果直接使用這些函數(shù)，你 需要自己去new 一些節(jié)點，當(dāng)節(jié)點特別多，而且進(jìn)行頻繁的刪除和插入的時候，內(nèi)存碎片 就會存在，而STL采用自己的Allocator分配內(nèi)存，以內(nèi)存池的方式來管理這些內(nèi)存，會大 大減少內(nèi)存碎片，從而會提升系統(tǒng)的整體性能。Winter在自己的系統(tǒng)中做過測試，把以前 所有直接用isc函數(shù)的

12、代碼替換成map，程序速度基本一致。當(dāng)時間運行很長時間后(例如 后臺服務(wù)程序)，map的優(yōu)勢就會體現(xiàn)出來。從另外一個方面講，使用map會大大降低你 的編碼難度，同時增加程序的可讀性。何樂而不為？學(xué)習(xí)STL map, STL set之?dāng)?shù)據(jù)結(jié)構(gòu)基 礎(chǔ)作者：winter摘要：本文列出幾個基本的STL map和STL set的問題，通過解答這些問題講解了 STL關(guān) 聯(lián)容器內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，最后提出了關(guān)于UNIX/LINUX自帶平衡二叉樹庫函數(shù)和map, set 選擇問題，并分析了 map, set的優(yōu)勢之處。對于希望深入學(xué)習(xí)STL和希望了解STL map 等關(guān)聯(lián)容器底層數(shù)據(jù)結(jié)構(gòu)的朋友來說，有一定的參考價

13、值。STL map和set的使用雖不復(fù)雜，但也有一些不易理解的地方，如：#為何map和set的插入刪除效率比用其他序列容器高？#為何每次insert之后，以前保存的iterator不會失效？#為何map和set不能像vector 一樣有個reserve函數(shù)來預(yù)分配數(shù)據(jù)？#當(dāng)數(shù)據(jù)元素增多時(10000到20000個比較)，map和set的插入和搜索速度變化如何？或許有得人能回答出來大概原因，但要徹底明白，還需要了解STL的底層數(shù)據(jù)結(jié)構(gòu)。C+ STL之所以得到廣泛的贊譽，也被很多人使用，不只是提供了像vector, string, list等 方便的容器，更重要的是STL封裝了許多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)算

14、法和大量常用數(shù)據(jù)結(jié)構(gòu)操作。 vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時 候，STL按照程序員的使用習(xí)慣，以成員函數(shù)方式提供的常用操作，如：插入、排序、刪 除、查找等。讓用戶在STL使用過程中，并不會感到陌生。C+ STL中標(biāo)準(zhǔn)關(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)

15、聯(lián)容器的內(nèi)部結(jié)構(gòu)。本文并不會介紹詳細(xì)AVL樹和RB樹的實現(xiàn)以及 他們的優(yōu)劣，關(guān)于RB樹的詳細(xì)實現(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é)點就可以了。刪除的時候類似， 稍做變換

16、后把指向刪除節(jié)點的指針指向其他節(jié)點就OK 了。這里的一切操作就是指針換來換 去，和內(nèi)存移動沒有關(guān)系。為何每次insert之后，以前保存的iterator不會失效？看見了上面答案的解釋，你應(yīng)該已經(jīng)可以很容易解釋這個問題。iterator這里就相當(dāng)于指向 節(jié)點的指針，內(nèi)存沒有變，指向內(nèi)存的指針怎么會失效呢（當(dāng)然被刪除的那個元素本身已經(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的

17、時候， 容器內(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聲明的時候從參數(shù)中傳入的Alloc。例如：mapint, int, less

18、, Alloc intmap;這時候在intmap中使用的allocator并不是Alloc,而是通過了轉(zhuǎn)換的Alloc，具體轉(zhuǎn)換 的方法時在內(nèi)部通過Alloc:rebind重新定義了新的節(jié)點分配器，詳細(xì)的實現(xiàn)參看徹底 學(xué)習(xí)STL中的Allocator。其實你就記住一點，在map和set內(nèi)面的分配器已經(jīng)發(fā)生了變化， reserve方法你就不要奢望了。當(dāng)數(shù)據(jù)元素增多時(10000和20000個比較)，map和set的插入和搜索速度變化如何？如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個答案。在map和set中查找是使用二分查找， 也就是說，如果有16個元素，最多需要比較4次就能找到結(jié)果，有32個元素，最多比較5 次。那么有10000個呢？最多比較的次數(shù)為log10000，最多為14次，如果是20000個元 素呢？最多不過15次?？匆娏税?，當(dāng)數(shù)據(jù)量增大一倍的時候，搜索次數(shù)只不過多了 1次， 多了 1/14的搜索時間而已。你明白這個道理后，就可以安心往里面放入元素了。最后，對于map和set Winter還要提的就是它們和一個c語言包裝庫的效率比較。在許多 unix和linux平臺下，都有一個庫叫isc，里面就提供類似于以下聲明的函數(shù)：void tree_init(void *