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

《stl中map、set的數(shù)據(jù)結(jié)構(gòu)及底層實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

2、e）——在功能上和vector相似，但是可以在前后兩端向其中添加數(shù)據(jù)。?list（列表）——游標(biāo)一次只可以移動(dòng)一步。如果你對(duì)鏈表已經(jīng)很熟悉，那么STL中的list則是一個(gè)雙向鏈表（每個(gè)節(jié)點(diǎn)有指向前驅(qū)和指向后繼的兩個(gè)指針）。set（集合）——包含了經(jīng)過排序了的數(shù)據(jù)，這些數(shù)據(jù)的值(value)必須是唯一的。map（映射）——經(jīng)過排序了的二元組的集合，map中的每個(gè)元素都是由兩個(gè)值組成，其中的key（鍵值，一個(gè)map中的鍵值必須是唯一的）是在排序或搜索時(shí)使用，它的值可以在容器中重新獲取；而另一個(gè)值是該元素

3、關(guān)聯(lián)的數(shù)值。比如，除了可以ar[43]="overripe"這樣找到一個(gè)數(shù)據(jù)，map還可以通過ar["banana"]="overripe"這樣的方法找到一個(gè)數(shù)據(jù)。如果你想獲得其中的元素信息，通過輸入元素的全名就可以輕松實(shí)現(xiàn)。multiset（多重集）——和集合（set）相似，然而其中的值不要求必須是唯一的（即可以有重復(fù)）。multimap（多重映射）——和映射（map）相似，然而其中的鍵值不要求必須是唯一的（即可以有重復(fù)）。STLmap和set的使用雖不復(fù)雜，但也有一些不易理解的地方，如：#為何m

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

5、據(jù)結(jié)構(gòu)算法和大量常用數(shù)據(jù)結(jié)構(gòu)操作。vector封裝數(shù)組，list封裝了鏈表，map和set封裝了二叉樹等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時(shí)候，STL按照程序員的使用習(xí)慣，以成員函數(shù)方式提供的常用操作，如：插入、排序、刪除、查找等。讓用戶在STL使用過程中，并不會(huì)感到陌生。C++STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set,multiset,map,multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也成為RB樹(Red-BlackTree)。RB樹的統(tǒng)計(jì)性能要好于一般的平衡二叉樹(有些書籍根據(jù)作者姓名，Adel

6、son-Velskii和Landis，將其稱為AVL-樹)，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。本文并不會(huì)介紹詳細(xì)AVL樹和RB樹的實(shí)現(xiàn)以及他們的優(yōu)劣，關(guān)于RB樹的詳細(xì)實(shí)現(xiàn)參看紅黑樹:理論與實(shí)現(xiàn)(理論篇)。本文針對(duì)開始提出的幾個(gè)問題的回答，來向大家簡(jiǎn)單介紹map和set的底層數(shù)據(jù)結(jié)構(gòu)。為何map和set的插入刪除效率比用其他序列容器高？大部分人說，很簡(jiǎn)單，因?yàn)閷?duì)于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng)。說對(duì)了，確實(shí)如此。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲(chǔ)，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不

7、多，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)。結(jié)構(gòu)圖可能如下：????????A??????//??????B???C??????////????DEFG因此插入的時(shí)候只需要稍做變換，把節(jié)點(diǎn)的指針指向新的節(jié)點(diǎn)就可以了。刪除的時(shí)候類似，稍做變換后把指向刪除節(jié)點(diǎn)的指針指向其他節(jié)點(diǎn)就OK了。這里的一切操作就是指針換來換去，和內(nèi)存移動(dòng)沒有關(guān)系。為何每次insert之后，以前保存的iterator不會(huì)失效？看見了上面答案的解釋，你應(yīng)該已經(jīng)可以很容易解釋這個(gè)問題。iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針，內(nèi)存沒有變，指向內(nèi)存的指針

8、怎么會(huì)失效呢(當(dāng)然被刪除的那個(gè)元素本身已經(jīng)失效了)。相對(duì)于vector來說，每一次刪除和插入，指針都有可能失效，調(diào)用push_back在尾部插入也是如此。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了。即使時(shí)push_back的時(shí)候，容器內(nèi)部空間可能不夠，需要一塊新的更大的內(nèi)存，只有把以前的內(nèi)存釋放，申請(qǐng)新的更大的內(nèi)存，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后，那么以前的內(nèi)存