↓推薦關(guān)注↓

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="點(diǎn)擊獲取10萬 star的開發(fā)資源庫。 日常分享熱門、有趣和實(shí)用的開源項(xiàng)目～" data-from="0">

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

盡管 C 標(biāo)準(zhǔn)沒有強(qiáng)求 std::map 底層的數(shù)據(jù)結(jié)構(gòu)，但是根據(jù)其規(guī)定的時(shí)間復(fù)雜度，現(xiàn)在所有的 STL 實(shí)現(xiàn)都采用平衡二叉樹來實(shí)現(xiàn) std::map，而且用的都是紅黑樹。《算法導(dǎo)論（第 2 版）》第 12、13 章介紹了二叉搜索樹和紅黑樹的原理、性質(zhì)、偽代碼，侯捷先生的《STL 源碼剖析》第 5 章詳細(xì)剖析了 SGI STL 的對應(yīng)實(shí)現(xiàn)。本文對 STL 中紅黑樹（rb_tree）的實(shí)現(xiàn)問了幾個(gè)稍微深入一點(diǎn)的問題，并給出了我的理解。

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

數(shù)據(jù)結(jié)構(gòu)回顧

先回顧一下數(shù)據(jù)結(jié)構(gòu)教材上講的二叉搜索樹的結(jié)構(gòu)，節(jié)點(diǎn)（Node）一般有三個(gè)數(shù)據(jù)成員（left、right、data），樹（Tree）有一到兩個(gè)成員（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
而實(shí)際上 STL rb_tree 的結(jié)構(gòu)比這個(gè)要略微復(fù)雜一些，我整理的代碼見 https://gist.github.com/4574621#file-tree-structure-cc ?。

節(jié)點(diǎn)

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

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

樹

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

這里省略了一些默認(rèn)模板參數(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，因?yàn)?key_compare 通常是 empty class。（allocator 在哪里？）

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

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

繼續(xù)插入兩個(gè)節(jié)點(diǎn)，假設(shè)分別位于 root 的左右兩側(cè)，那么得到的數(shù)據(jù)結(jié)構(gòu)如下圖所示（parent 指針沒有全畫出來，因?yàn)槠渲赶蚝苊黠@），注意 header.left 指向最左側(cè)節(jié)點(diǎn)，header.right 指向最右側(cè)節(jié)點(diǎn)。

迭代器

rb_tree 的 iterator 的數(shù)據(jù)結(jié)構(gòu)很簡單，只包含一個(gè) rb_tree_node_base 指針，但是其 /--操作卻不見得簡單（具體實(shí)現(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\