一、c++ multimap是紅黑樹(shù)還是什么

C++標(biāo)準(zhǔn)并未硬性規(guī)定multimap必須使用哪種數(shù)據(jù)結(jié)構(gòu)，只是對(duì)其特性有所要求，比如容器內(nèi)元素必須有序，查找刪除時(shí)間復(fù)雜度得是對(duì)數(shù)級(jí)等等。 而紅黑樹(shù)確實(shí)非常適合用于這種場(chǎng)景，所以主流的STL版本都采用紅黑樹(shù)來(lái)實(shí)現(xiàn)multimap。 事實(shí)上如果你喜歡也可以自己用AVL樹(shù)或者甚至都不需要平衡二叉樹(shù)，比如skiplist就是個(gè)不錯(cuò)的選擇，來(lái)實(shí)現(xiàn)multimap。這些都是符合C++標(biāo)準(zhǔn)規(guī)定的。

紅黑樹(shù)（RB-Tree）—map，set，multimap,multiset底層使用紅黑樹(shù)

Red-Black tree(紅黑樹(shù))是平衡二分搜索樹(shù)（balanced binary search tree）中常被使用的一種。平衡二分搜索樹(shù)的特性：排列規(guī)則有利search和insert，并保持適度平衡—無(wú)任何結(jié)點(diǎn)過(guò)深。

RB-Tree提供遍歷操作及iterators。

按正常規(guī)則（++ite）遍歷，便能獲得排序狀態(tài)（sorted）。

我們不應(yīng)該使用RB-Tree的iterators改變?cè)刂担ㄒ驗(yàn)樵赜衅鋰?yán)謹(jǐn)?shù)呐帕幸?guī)則）。變成層面并未阻止此事。如此設(shè)計(jì)是正確的，因?yàn)镽B-Tree即將為set何map服務(wù)（作為其底層支持），而map允許元素的data被改變，只有元素的key才是不可被改變的。

RB-Tree提供兩種insertion操作：insert_unique()和insert_equal()。前者表示節(jié)點(diǎn)的key一定在整個(gè)tree中獨(dú)一無(wú)二，否則安插失敗；后者表示節(jié)點(diǎn)的key可重復(fù)。

容器set和multiset，底層容器使用的是紅黑樹(shù)（rb_tree）

set/multiset以rb_tree為底層結(jié)構(gòu)，因此有元素自動(dòng)排序特性。排序的依據(jù)是key，而set/multiset元素的value和key合一：value就是key。

set/multiset提供遍歷操作及iterators。按正常規(guī)則（++ite）遍歷，便能獲得排序狀態(tài)（sorted）。

我們無(wú)法使用set\multiset的iterators改變?cè)刂担ㄒ驗(yàn)閗ey有其嚴(yán)謹(jǐn)?shù)呐帕幸?guī)則）。set\multiset的iterator是其底部的rb_tree的const iterator，就是為了禁止用戶對(duì)元素賦值。

set元素的key必須獨(dú)一無(wú)二，因此其insert()用的是rb_tree的insert_unique()。

multiset元素的key可以重復(fù)，因此其insert()用的是rb_tree的insert_qeual()。

延伸閱讀：

二、紅黑樹(shù)概念

與AVL樹(shù)一樣，紅黑樹(shù)也是map、set等關(guān)聯(lián)式容器的底層結(jié)構(gòu)。但紅黑樹(shù)是現(xiàn)代主流的底層結(jié)構(gòu)，STL使用的便是紅黑樹(shù)。其原因在于：AVL樹(shù)保持平衡的方法太過(guò)于絕對(duì)(必須保證每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差不超過(guò)1)，而紅黑樹(shù)的性質(zhì)保證了其具有一定的”柔韌性”以及可觀的效率。

紅黑樹(shù)的本質(zhì)也是一顆二叉搜索樹(shù)，但在原有的基礎(chǔ)上做了平衡處理。紅黑樹(shù)的每個(gè)節(jié)點(diǎn)都會(huì)增加一個(gè)存儲(chǔ)位，用來(lái)表示節(jié)點(diǎn)的顏色，可以是紅色也可以是黑色。