一、c++ multimap是紅黑樹還是什么
C++標準并未硬性規定multimap必須使用哪種數據結構，只是對其特性有所要求，比如容器內元素必須有序，查找刪除時間復雜度得是對數級等等。 而紅黑樹確實非常適合用于這種場景，所以主流的STL版本都采用紅黑樹來實現multimap。 事實上如果你喜歡也可以自己用AVL樹或者甚至都不需要平衡二叉樹，比如skiplist就是個不錯的選擇，來實現multimap。這些都是符合C++標準規定的。
紅黑樹（RB-Tree）—map，set，multimap,multiset底層使用紅黑樹
Red-Black tree(紅黑樹)是平衡二分搜索樹（balanced binary search tree）中常被使用的一種。平衡二分搜索樹的特性：排列規則有利search和insert，并保持適度平衡—無任何結點過深。
RB-Tree提供遍歷操作及iterators。
按正常規則（++ite）遍歷，便能獲得排序狀態（sorted）。
我們不應該使用RB-Tree的iterators改變元素值（因為元素有其嚴謹的排列規則）。變成層面并未阻止此事。如此設計是正確的，因為RB-Tree即將為set何map服務（作為其底層支持），而map允許元素的data被改變，只有元素的key才是不可被改變的。
RB-Tree提供兩種insertion操作：insert_unique()和insert_equal()。前者表示節點的key一定在整個tree中獨一無二，否則安插失敗；后者表示節點的key可重復。
容器set和multiset，底層容器使用的是紅黑樹（rb_tree）
set/multiset以rb_tree為底層結構，因此有元素自動排序特性。排序的依據是key，而set/multiset元素的value和key合一：value就是key。
set/multiset提供遍歷操作及iterators。按正常規則（++ite）遍歷，便能獲得排序狀態（sorted）。
我們無法使用set\multiset的iterators改變元素值（因為key有其嚴謹的排列規則）。set\multiset的iterator是其底部的rb_tree的const iterator，就是為了禁止用戶對元素賦值。
set元素的key必須獨一無二，因此其insert()用的是rb_tree的insert_unique()。
multiset元素的key可以重復，因此其insert()用的是rb_tree的insert_qeual()。
延伸閱讀：
二、紅黑樹概念
與AVL樹一樣，紅黑樹也是map、set等關聯式容器的底層結構。但紅黑樹是現代主流的底層結構，STL使用的便是紅黑樹。其原因在于：AVL樹保持平衡的方法太過于絕對(必須保證每個節點的左右子樹的高度差不超過1)，而紅黑樹的性質保證了其具有一定的”柔韌性”以及可觀的效率。
紅黑樹的本質也是一顆二叉搜索樹，但在原有的基礎上做了平衡處理。紅黑樹的每個節點都會增加一個存儲位，用來表示節點的顏色，可以是紅色也可以是黑色。
京公網安備 11010802030320號