↓推薦關注↓

select_card mp_profile_iframe" data-pluginname="mpprofile" data-id="MzAxMDM0MzQ4Mg==" data-headimg="http://mmbiz.qpic.cn/mmbiz_png/DSU8cv1j3ibStMRcibJLd4TkNlt53KNZj0A2IicORH4REC4ics87icsx703M5giby2wuofz3dicMsHVcXDMXTM6t6VBQw/0?wx_fmt=png" data-nickname="開源前哨" data-alias="osfront" data-signature="點擊獲取10萬 star的開發(fā)資源庫。 日常分享熱門、有趣和實用的開源項目～" data-from="0">

std::set/std::map （以下用 std::map 代表） 是常用的關聯(lián)式容器，也是 ADT（抽象數(shù)據類型）。也就是說，其接口（不是 OO 意義下的 interface）不僅規(guī)定了操作的功能，還規(guī)定了操作的復雜度（代價/cost）。例如 set::insert(iterator first, iterator last) 在通常情況下是 O(N log N)，N 是區(qū)間的長度；但是如果 [first, last) 已經排好序（在 key_compare 意義下），那么復雜度將會是 O(N)。

盡管 C 標準沒有強求 std::map 底層的數(shù)據結構，但是根據其規(guī)定的時間復雜度，現(xiàn)在所有的 STL 實現(xiàn)都采用平衡二叉樹來實現(xiàn) std::map，而且用的都是紅黑樹?！端惴▽д摚ǖ?2 版）》第 12、13 章介紹了二叉搜索樹和紅黑樹的原理、性質、偽代碼，侯捷先生的《STL 源碼剖析》第 5 章詳細剖析了 SGI STL 的對應實現(xiàn)。本文對 STL 中紅黑樹（rb_tree）的實現(xiàn)問了幾個稍微深入一點的問題，并給出了我的理解。

本文剖析的是 G 4.7 自帶的這一份 STL 實現(xiàn)及其特定行為，與《STL 源碼剖析》的版本略有區(qū)別。為了便于閱讀，文中的變量名和 class 名都略有改寫（例如 _Rb_tree_node 改為 rb_tree_node）。本文不談紅黑樹的平衡算法，在我看來這屬于“旁枝末節(jié)”（見陳碩《談一談網絡編程學習經驗》對此的定義），因此也就不關心節(jié)點的具體顏色了。

數(shù)據結構回顧

先回顧一下數(shù)據結構教材上講的二叉搜索樹的結構，節(jié)點（Node）一般有三個數(shù)據成員（left、right、data），樹（Tree）有一到兩個成員（root 和 node_count）。

用 Python 表示：
class?Node:
????def?\_\_init\_\_\(self,?data\):
????????self.left?=?None
????????self.right?=?None
????????self.data?=?data

class?Tree:
????def?\_\_init\_\_\(self\):
????????self.root?=?None
????????self.node\_count?=?0
而實際上 STL rb_tree 的結構比這個要略微復雜一些，我整理的代碼見 https://gist.github.com/4574621#file-tree-structure-cc ?。

節(jié)點

Node 有 5 個成員，除了 left、right、data，還有 color 和 parent。

C 實現(xiàn)，位于bits/stl\_tree.h
/\*\*
?\*?Non-template?code
?\*\*/

enum?rb\_tree\_color?\{?kRed,?kBlack?\};

struct?rb\_tree\_node\_base
\{
??rb\_tree\_color???????color\_;
??rb\_tree\_node\_base\*??parent\_;
??rb\_tree\_node\_base\*??left\_;
??rb\_tree\_node\_base\*??right\_;
\};

/\*\*
?\*?template?code
?\*\*/

template\
struct?rb\_tree\_node?:?public?rb\_tree\_node\_base
\{
??Value?value\_field\_;
\};
見下圖。

color 的存在很好理解，紅黑樹每個節(jié)點非紅即黑，需要保存其顏色（顏色只需要 1-bit 數(shù)據，一種節(jié)省內存的優(yōu)化措施是把顏色嵌入到某個指針的最高位或最低位，Linux 內核里的 rbtree 是嵌入到 parent 的最低位）；parent 的存在使得非遞歸遍歷成為可能，后面還將再談到這一點。

樹

Tree 有更多的成員，它包含一個完整的 rb_tree_node_base（color/parent/left/right），還有 node_count 和 key_compare 這兩個額外的成員。

這里省略了一些默認模板參數(shù)，如 key_compare 和 allocator。

template\?//?key\_compare?and?allocator
class?rb\_tree
\{
?public:
??typedef?std::less\?key\_compare;
??typedef?rb\_tree\_iterator\?iterator;
?protected:

??struct?rb\_tree\_impl?//?:?public?node\_allocator
??\{
????key\_compare???????key\_compare\_;
????rb\_tree\_node\_base?header\_;
????size\_t????????????node\_count\_;
??\};
??rb\_tree\_impl?impl\_;
\};
template\?//?key\_compare?and?allocator
class?map
\{
?public:
??typedef?std::pair\?value\_type;
?private:
??typedef?rb\_tree\?rep\_type;
??rep\_type?tree\_;
\};
見下圖。這是一顆空樹，其中陰影部分是 padding bytes，因為 key_compare 通常是 empty class。（allocator 在哪里？）

rb_tree 中的 header 不是 rb_tree_node 類型，而是 rb_tree_node_base，因此 rb_tree 的 size 是 6 * sizeof(void*)，與模板類型參數(shù)無關。在 32-bit 上是 24 字節(jié)，在 64-bit 上是 48 字節(jié)，很容易用代碼驗證這一點。另外容易驗證 std::set 和 std::map 的 sizeof() 是一樣的。

注意 rb_tree 中的 header 不是 root 節(jié)點，其 left 和 right 成員也不是指向左右子節(jié)點，而是指向最左邊節(jié)點（left_most）和最右邊節(jié)點（right_most），后面將會介紹原因，是為了滿足時間復雜度。header.parent 指向 root 節(jié)點，root.parent 指向 header，header 固定是紅色，root 固定是黑色。在插入一個節(jié)點后，數(shù)據結構如下圖。

繼續(xù)插入兩個節(jié)點，假設分別位于 root 的左右兩側，那么得到的數(shù)據結構如下圖所示（parent 指針沒有全畫出來，因為其指向很明顯），注意 header.left 指向最左側節(jié)點，header.right 指向最右側節(jié)點。

迭代器

rb_tree 的 iterator 的數(shù)據結構很簡單，只包含一個 rb_tree_node_base 指針，但是其 /--操作卻不見得簡單（具體實現(xiàn)函數(shù)不在頭文件中，而在 libstdc 庫文件中）。

//?defined?in?library,?not?in?header
rb\_tree\_node\_base\*?rb\_tree\_increment\(rb\_tree\_node\_base\*?node\);
//?others:?decrement,?reblance,?etc.

template\
struct?rb\_tree\_node?:?public?rb\_tree\_node\_base
\{
??Value?value\_field\_;
\};

template\
struct?rb\_tree\_iterator
\{
??Value\