陳碩 (chenshuo.com)
2013-01-20
std::set/std::map （以下用 std::map 代表） 是常用的關(guān)聯(lián)式容器，也是 ADT（抽象數(shù)據(jù)類(lèi)型）。也就是說(shuō)，其接口（不是 OO 意義下的 interface）不僅規(guī)定了操作的功能，還規(guī)定了操作的復(fù)雜度（代價(jià)/cost）。例如 set::insert(iterator first, iterator last) 在通常情況下是 O(N log N)，N 是區(qū)間的長(zhǎng)度；但是如果 [first, last) 已經(jīng)排好序（在 key_compare 意義下），那么復(fù)雜度將會(huì)是 O(N)。
盡管 C++ 標(biāo)準(zhǔn)沒(méi)有強(qiáng)求 std::map 底層的數(shù)據(jù)結(jié)構(gòu)，但是根據(jù)其規(guī)定的時(shí)間復(fù)雜度，現(xiàn)在所有的 STL 實(shí)現(xiàn)都采用平衡二叉樹(shù)來(lái)實(shí)現(xiàn) std::map，而且用的都是紅黑樹(shù)。《算法導(dǎo)論（第 2 版）》第 12、13 章介紹了二叉搜索樹(shù)和紅黑樹(shù)的原理、性質(zhì)、偽代碼，侯捷先生的《STL 源碼剖析》第 5 章詳細(xì)剖析了 SGI STL 的對(duì)應(yīng)實(shí)現(xiàn)。本文對(duì) STL 中紅黑樹(shù)（rb_tree）的實(shí)現(xiàn)問(wèn)了幾個(gè)稍微深入一點(diǎn)的問(wèn)題，并給出了我的理解。本文剖析的是 G++ 4.7 自帶的這一份 STL 實(shí)現(xiàn)及其特定行為，與《STL 源碼剖析》的版本略有區(qū)別。為了便于閱讀，文中的變量名和 class 名都略有改寫(xiě)（例如 _Rb_tree_node 改為 rb_tree_node）。本文不談紅黑樹(shù)的平衡算法，在我看來(lái)這屬于“旁枝末節(jié)”（見(jiàn)陳碩《談一談網(wǎng)絡(luò)編程學(xué)習(xí)經(jīng)驗(yàn)》對(duì)此的定義），因此也就不關(guān)心節(jié)點(diǎn)的具體顏色了。
數(shù)據(jù)結(jié)構(gòu)回顧
先回顧一下數(shù)據(jù)結(jié)構(gòu)教材上講的二叉搜索樹(shù)的結(jié)構(gòu)，節(jié)點(diǎn)（Node）一般有三個(gè)數(shù)據(jù)成員（left、right、data），樹(shù)（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ù)雜一些，我整理的代碼見(jiàn) 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<typename Value>
struct rb_tree_node : public rb_tree_node_base
{
Value value_field_;
};
見(jiàn)下圖。
color 的存在很好理解，紅黑樹(shù)每個(gè)節(jié)點(diǎn)非紅即黑，需要保存其顏色（顏色只需要 1-bit 數(shù)據(jù)，一種節(jié)省內(nèi)存的優(yōu)化措施是把顏色嵌入到某個(gè)指針的最高位或最低位，Linux 內(nèi)核里的 rbtree 是嵌入到 parent 的最低位）；parent 的存在使得非遞歸遍歷成為可能，后面還將再談到這一點(diǎn)。
樹(shù)
Tree 有更多的成員，它包含一個(gè)完整的 rb_tree_node_base（color/parent/left/right），還有 node_count 和 key_compare 這兩個(gè)額外的成員。
這里省略了一些默認(rèn)模板參數(shù)，如 key_compare 和 allocator。
template<typename Key, typename Value> // key_compare and allocator
class rb_tree
{
public:
typedef std::less<Key> key_compare;
typedef rb_tree_iterator<Value> 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<typename Key, typename T> // key_compare and allocator
class map
{
public:
typedef std::pair<const Key, T> value_type;
private:
typedef rb_tree<Key, value_type> rep_type;
rep_type tree_;
};
見(jiàn)下圖。這是一顆空樹(shù)，其中陰影部分是 padding bytes，因?yàn)?key_compare 通常是 empty class。（allocator 在哪里？）
rb_tree 中的 header 不是 rb_tree_node 類(lèi)型，而是 rb_tree_node_base，因此 rb_tree 的 size 是 6 * sizeof(void*)，與模板類(lèi)型參數(shù)無(wú)關(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 指針沒(méi)有全畫(huà)出來(lái)，因?yàn)槠渲赶蚝苊黠@），注意 header.left 指向最左側(cè)節(jié)點(diǎn)，header.right 指向最右側(cè)節(jié)點(diǎn)。
迭代器
rb_tree 的 iterator 的數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單，只包含一個(gè) rb_tree_node_base 指針，但是其++/--操作卻不見(jiàn)得簡(jiǎn)單（具體實(shí)現(xiàn)函數(shù)不在頭文件中，而在 libstdc++ 庫(kù)文件中）。
// defined in library, not in header
rb_tree_node_base* rb_tree_increment(rb_tree_node_base* node);
// others: decrement, reblance, etc.
template<typename Value>
struct rb_tree_node : public rb_tree_node_base
{
Value value_field_;
};
template<typename Value>
struct rb_tree_iterator
{
Value& operator*() const
{
return static_cast<rb_tree_node<Value>*>(node_)->value_field_;
}
rb_tree_iterator& operator++()
{
node_ = rb_tree_increment(node_);
return *this;
}
rb_tree_node_base* node_;
};
end() 始終指向 header 節(jié)點(diǎn)，begin() 指向第一個(gè)節(jié)點(diǎn)（如果有的話）。因此對(duì)于空樹(shù)，begin() 和 end() 都指向 header 節(jié)點(diǎn)。對(duì)于 1 個(gè)元素的樹(shù)，迭代器的指向如下。
對(duì)于前面 3 個(gè)元素的樹(shù)，迭代器的指向如下。
思考，對(duì) std::set<int>::end() 做 dereference 會(huì)得到什么？（按標(biāo)準(zhǔn)，這屬于undefined behaviour，不過(guò)但試無(wú)妨。）
rb_tree 的 iterator 的遞增遞減操作并不簡(jiǎn)單?？紤]下面這棵樹(shù)，假設(shè)迭代器 iter 指向綠色節(jié)點(diǎn)3，那么 ++iter 之后它應(yīng)該指向灰色節(jié)點(diǎn) 4，再 ++iter 之后，它應(yīng)該指向黃色節(jié)點(diǎn) 5，這兩步遞增都各走過(guò)了 2 個(gè)指針。
對(duì)于一顆更大的樹(shù)（下圖），假設(shè)迭代器 iter 指向綠色節(jié)點(diǎn)7，那么 ++iter 之后它應(yīng)該指向灰色節(jié)點(diǎn) 8，再 ++iter 之后，它應(yīng)該指向黃色節(jié)點(diǎn) 9，這兩步遞增都各走過(guò)了 3 個(gè)指針。
由此可見(jiàn)，rb_tree 的迭代器的每次遞增或遞減不能保證是常數(shù)時(shí)間，最壞情況下可能是對(duì)數(shù)時(shí)間（即與樹(shù)的深度成正比）。那么用 begin()/end() 迭代遍歷一棵樹(shù)還是不是 O(N)？換言之，迭代器的遞增或遞減是否是分?jǐn)偤蟮模╝mortized）常數(shù)時(shí)間？
另外注意到，當(dāng) iter 指向最右邊節(jié)點(diǎn)的時(shí)候（7 或 15），++iter 應(yīng)該指向 header 節(jié)點(diǎn)，即 end()，這一步是 O(log N)。同理，對(duì) end() 做--，復(fù)雜度也是 O(log N)，后面會(huì)用到這一事實(shí)。
rb_tree 迭代器的遞增遞減操作的實(shí)現(xiàn)也不是那么一目了然。要想從頭到尾遍歷一顆二叉樹(shù)（前序、中序、后序），教材上給出的辦法是用遞歸（或者用 stack 模擬遞歸，性質(zhì)一樣），比如：（https://gist.github.com/4574621#file-tree-traversal-py ）
Python:
def printTree(node):
if node:
printTree(node.left)
print node.data
printTree(node.right)
如果考慮通用性，可以把函數(shù)作為參數(shù)進(jìn)去，然后通過(guò)回調(diào)的方式來(lái)訪問(wèn)每個(gè)節(jié)點(diǎn)，代碼如下。Java XML 的 SAX 解析方式也是這樣。
Python:
def visit(node, func):
if node:
printTree(node.left)
func(node.data)
printTree(node.right)
要想使用更方便，在調(diào)用方用 for 循環(huán)就能從頭到尾遍歷 tree，那似乎就不那么容易了。在 Python 這種支持 coroutine 的語(yǔ)言中，可以用 yield 關(guān)鍵字配合遞歸來(lái)實(shí)現(xiàn)，代碼如下，與前面的實(shí)現(xiàn)沒(méi)有多大區(qū)別。
在 Python 3.3 中還可以用 yield from，這里用 Python 2.x 的寫(xiě)法。
def travel(root):
if root.left:
for x in travel(root.left):
yield x
yield root.data
if root.right:
for y in travel(root.right):
yield y
調(diào)用方：
for y in travel(root):
print y
但是在 C++ 中，要想做到最后這種 StAX 的遍歷方式，那么迭代器的實(shí)現(xiàn)就麻煩多了，見(jiàn)《STL 源碼剖析》第 5.2.4 節(jié)的詳細(xì)分析。這也是 node 中 parent 指針存在的原因，因?yàn)檫f增操作時(shí)，如果當(dāng)前節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)，就需要先回到父節(jié)點(diǎn)，再接著找。
空間復(fù)雜度
每個(gè) rb_tree_node 直接包含了 value_type，其大小是 4 * sizeof(void*) + sizeof(value_type)。在實(shí)際分配內(nèi)存的時(shí)候還要 round up 到 allocator/malloc 的對(duì)齊字節(jié)數(shù)，通常 32-bit 是 8 字節(jié)，64-bit 是 16 字節(jié)。因此 set<int>每個(gè)節(jié)點(diǎn)是 24 字節(jié)或 48 字節(jié)，100 萬(wàn)個(gè)元素的 set<int> 在 x86-64 上將占用 48M 內(nèi)存。說(shuō)明用 set<int> 來(lái)排序整數(shù)是很不明智的行為，無(wú)論從時(shí)間上還是空間上。
考慮 malloc 對(duì)齊的影響，set<int64_t> 和 set<int32_t> 占用相同的空間，set<int> 和 map<int, int> 占用相同的空間，無(wú)論 32-bit 還是 64-bit 均如此。
幾個(gè)為什么
對(duì)于 rb_tree 的數(shù)據(jù)結(jié)構(gòu)，我們有幾個(gè)問(wèn)題：
1. 為什么 rb_tree 沒(méi)有包含 allocator 成員？
2. 為什么 iterator 可以 pass-by-value？
3. 為什么 header 要有 left 成員，并指向 left most 節(jié)點(diǎn)？
4. 為什么 header 要有 right 成員，并指向 right most 節(jié)點(diǎn)？
5. 為什么 header 要有 color 成員，并且固定是紅色？
6. 為什么要分為 rb_tree_node 和 rb_tree_node_base 兩層結(jié)構(gòu)，引入 node 基類(lèi)的目的是什么？
7. 為什么 iterator 的遞增遞減是分?jǐn)偅╝mortized）常數(shù)時(shí)間？
8. 為什么 muduo 網(wǎng)絡(luò)庫(kù)的 Poller 要用 std::map<int, Channel*> 來(lái)管理文件描述符？
我認(rèn)為，在面試的時(shí)候能把上面前 7 個(gè)問(wèn)題答得頭頭是道，足以說(shuō)明對(duì) STL 的 map/set 掌握得很好。下面一一解答。
為什么 rb_tree 沒(méi)有包含 allocator 成員？
因?yàn)槟J(rèn)的 allocator 是 empty class （沒(méi)有數(shù)據(jù)成員，也沒(méi)有虛表指針vptr），為了節(jié)約 rb_tree 對(duì)象的大小，STL 在實(shí)現(xiàn)中用了 empty base class optimization。具體做法是 std::map 以 rb_tree 為成員，rb_tree 以 rb_tree_impl 為成員，而 rb_tree_impl 繼承自 allocator，這樣如果 allocator 是 empty class，那么 rb_tree_impl 的大小就跟沒(méi)有基類(lèi)時(shí)一樣。其他 STL 容器也使用了相同的優(yōu)化措施，因此 std::vector 對(duì)象是 3 個(gè) words，std::list 對(duì)象是 2 個(gè) words。boost 的 compressed_pair 也使用了相同的優(yōu)化。
我認(rèn)為，對(duì)于默認(rèn)的 key_compare，應(yīng)該也可以實(shí)施同樣的優(yōu)化，這樣每個(gè) rb_tree 只需要 5 個(gè) words，而不是 6 個(gè)。
為什么 iterator 可以 pass-by-value？
讀過(guò)《Effective C++》的想必記得其中有個(gè)條款是 Prefer pass-by-reference-to-const to pass-by-value，即對(duì)象盡量以 const reference 方式傳參。這個(gè)條款同時(shí)指出，對(duì)于內(nèi)置類(lèi)型、STL 迭代器和 STL 仿函數(shù)，pass-by-value 也是可以的，一般沒(méi)有性能損失。
在 x86-64 上，對(duì)于 rb_tree iterator 這種只有一個(gè) pointer member 且沒(méi)有自定義 copy-ctor 的 class，pass-by-value 是可以通過(guò)寄存器進(jìn)行的（例如函數(shù)的頭 4 個(gè)參數(shù)，by-value 返回對(duì)象算一個(gè)參數(shù)），就像傳遞普通 int 和指針那樣。因此實(shí)際上可能比 pass-by-const-reference 略快，因?yàn)閏allee 減少了一次 deference。
同樣的道理，muduo 中的 Date class 和 Timestamp class 也是明確設(shè)計(jì)來(lái) pass-by-value 的，它們都只有一個(gè) int/long 成員，按值拷貝不比 pass reference 慢。如果不分青紅皂白一律對(duì) object 使用 pass-by-const-reference，固然算不上什么錯(cuò)誤，不免稍微顯得知其然不知其所以然罷了。
為什么 header 要有 left 成員，并指向 left most 節(jié)點(diǎn)？
原因很簡(jiǎn)單，讓 begin() 函數(shù)是 O(1)。假如 header 中只有 parent 沒(méi)有 left，begin() 將會(huì)是 O(log N)，因?yàn)橐獜?root 出發(fā)，走 log N 步，才能到達(dá) left most。現(xiàn)在 begin() 只需要用 header.left 構(gòu)造 iterator 并返回即可。
為什么 header 要有 right 成員，并指向 right most 節(jié)點(diǎn)？
這個(gè)問(wèn)題不是那么顯而易見(jiàn)。end() 是 O(1)，因?yàn)橹苯佑?header 的地址構(gòu)造 iterator 即可，不必使用 right most 節(jié)點(diǎn)。在源碼中有這么一段注釋：
bits/stl_tree.h
// Red-black tree class, designed for use in implementing STL
// associative containers (set, multiset, map, and multimap). The
// insertion and deletion algorithms are based on those in Cormen,
// Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
// 1990), except that
//
// (1) the header cell is maintained with links not only to the root
// but also to the leftmost node of the tree, to enable constant
// time begin(), and to the rightmost node of the tree, to enable
// linear time performance when used with the generic set algorithms
// (set_union, etc.)
//
// (2) when a node being deleted has two children its successor node
// is relinked into its place, rather than copied, so that the only
// iterators invalidated are those referring to the deleted node.
這句話的意思是說(shuō)，如果按大小順序插入元素，那么將會(huì)是線性時(shí)間，而非 O(N log N)。即下面這段代碼的運(yùn)行時(shí)間與 N 成正比：
// 在 end() 按大小順序插入元素
std::set<int> s;
const int N = 1000 * 1000
for (int i = 0; i < N; ++i)
s.insert(s.end(), i);
在 rb_tree 的實(shí)現(xiàn)中，insert(value) 一個(gè)元素通常的復(fù)雜度是 O(log N)。不過(guò)，insert(hint, value) 除了可以直接傳 value_type，還可以再傳一個(gè) iterator 作為 hint，如果實(shí)際的插入點(diǎn)恰好位于 hint 左右，那么分?jǐn)偤蟮膹?fù)雜度是 O(1)。對(duì)于這里的情況，既然每次都在 end() 插入，而且插入的元素又都比 *(end()-1) 大，那么 insert() 是 O(1)。在具體實(shí)現(xiàn)中，如果 hint 等于 end()，而且 value 比 right most 元素大，那么直接在 right most 的右子節(jié)點(diǎn)插入新元素即可。這里 header.right 的意義在于讓我們能在常數(shù)時(shí)間取到 right most 節(jié)點(diǎn)的元素，從而保證 insert() 的復(fù)雜度（而不需要從 root 出發(fā)走 log N 步到達(dá) right most）。具體的運(yùn)行時(shí)間測(cè)試見(jiàn) https://gist.github.com/4574621#file-tree-bench-cc ，測(cè)試結(jié)果如下，縱坐標(biāo)是每個(gè)元素的耗時(shí)（微秒），其中最上面的紅線是普通 insert(value)，下面的藍(lán)線和黑線是 insert(end(), value)，確實(shí)可以大致看出 O(log N) 和 O(1) 關(guān)系。具體的證明見(jiàn)《算法導(dǎo)論（第 2 版》第 17 章中的思考題 17-4。
但是，根據(jù)測(cè)試結(jié)果，前面引用的那段注釋其實(shí)是錯(cuò)的，std::inserter() 與 set_union() 配合并不能實(shí)現(xiàn) O(N) 復(fù)雜度。原因是 std::inserter_iterator 會(huì)在每次插入之后做一次 ++iter，而這時(shí) iter 正好指向 right most 節(jié)點(diǎn)，其++操作是 O(log N) 復(fù)雜度（前面提到過(guò) end() 的遞減是 O(log N)，這里反過(guò)來(lái)也是一樣）。于是把整個(gè)算法拖慢到了 O(N log N)。要想 set_union() 是線性復(fù)雜度，我們需要自己寫(xiě) inserter，見(jiàn)上面代碼中的 end_inserter 和 at_inserter，此處不再贅言。
為什么 header 要有 color 成員，并且固定是紅色？
這是一個(gè)實(shí)現(xiàn)技巧，對(duì) iterator 做遞減時(shí)，如果此刻 iterator 指向 end()，那么應(yīng)該走到 right most 節(jié)點(diǎn)。既然 iterator 只有一個(gè)數(shù)據(jù)成員，要想判斷當(dāng)前是否指向 end()，就只好判斷 (node_->color_ == kRed && node_->parent_->parent_ == node_) 了。
為什么要分為 rb_tree_node 和 rb_tree_node_base 兩層結(jié)構(gòu)，引入 node 基類(lèi)的目的是什么？
這是為了把迭代器的遞增遞減、樹(shù)的重新平衡等復(fù)雜函數(shù)從頭文件移到庫(kù)文件中，減少模板引起的代碼膨脹（set<int> 和 set<string> 可以共享這些的 rb_tree 基礎(chǔ)函數(shù)），也稍微加快編譯速度。引入 rb_tree_node_base 基類(lèi)之后，這些操作就可以以基類(lèi)指針（與模板參數(shù)類(lèi)型無(wú)關(guān)）為參數(shù)，因此函數(shù)定義不必放在在頭文件中。這也是我們?cè)陬^文件里看不到 iterator 的 ++/-- 的具體實(shí)現(xiàn)的原因，它們位于 libstdc++ 的庫(kù)文件源碼中。注意這里的基類(lèi)不是為了 OOP，而純粹是一種實(shí)現(xiàn)技巧。
為什么 iterator 的遞增遞減是分?jǐn)偅╝mortized）常數(shù)時(shí)間？
嚴(yán)格的證明需要用到分?jǐn)偡治觯╝mortized analysis），一來(lái)我不會(huì)，二來(lái)寫(xiě)出來(lái)也沒(méi)多少人看，這里我用一點(diǎn)歸納的辦法來(lái)說(shuō)明這一點(diǎn)?？紤]一種特殊情況，對(duì)前面圖中的滿二叉樹(shù)（perfect binary tree）從頭到尾遍歷，計(jì)算迭代器一共走過(guò)多少步（即 follow 多少次指針），然后除以節(jié)點(diǎn)數(shù) N，就能得到平均每次遞增需要走多少步。既然紅黑樹(shù)是平衡的，那么這個(gè)數(shù)字跟實(shí)際的步數(shù)也相差不遠(yuǎn)。
對(duì)于深度為 1 的滿二叉樹(shù)，有 1 個(gè)元素，從 begin() 到 end() 需要走 1 步，即從 root 到 header。
對(duì)于深度為 2 的滿二叉樹(shù)，有 3 個(gè)元素，從 begin() 到 end() 需要走 4 步，即 1->2->3->header，其中從 3 到 header 是兩步
對(duì)于深度為 3 的滿二叉樹(shù)，有 7 個(gè)元素，從 begin() 到 end() 需要走 11 步，即先遍歷左子樹(shù)（4 步）、走 2 步到達(dá)右子樹(shù)的最左節(jié)點(diǎn)，遍歷右子樹(shù)（4 步），最后走 1 步到達(dá) end()，4 + 2 + 4 + 1 = 11。
對(duì)于深度為 4 的滿二叉樹(shù)，有 15 個(gè)元素，從 begin() 到 end() 需要走 26 步。即先遍歷左子樹(shù)（11 步）、走 3 步到達(dá)右子樹(shù)的最左節(jié)點(diǎn)，遍歷右子樹(shù)（11 步），最后走 1 步到達(dá) end()，11 + 3 + 11 + 1 = 26。
后面的幾個(gè)數(shù)字依次是 57、120、247
對(duì)于深度為 n 的滿二叉樹(shù)，有 2^n - 1 個(gè)元素，從 begin() 到 end() 需要走 f(n) 步。那么 f(n) = 2*f(n-1) + n。
然后，用遞推關(guān)系求出 f(n) = sum(i * 2 ^ (n-i)) = 2^(n+1) - n - 2（這個(gè)等式可以用歸納法證明）。即對(duì)于深度為 n 的滿二叉樹(shù)，從頭到尾遍歷的步數(shù)小于 2^(n+1) - 2，而元素個(gè)數(shù)是 2^n - 1，二者一除，得到平均每個(gè)元素需要 2 步。因此可以說(shuō) rb_tree 的迭代器的遞增遞減是分?jǐn)偤蟮某?shù)時(shí)間。
似乎還有更簡(jiǎn)單的證明方法，在從頭到尾遍歷的過(guò)程中，每條邊（edge）最多來(lái)回各走一遍，一棵樹(shù)有 N 個(gè)節(jié)點(diǎn)，那么有 N-1 條邊，最多走 2*(N-1)+1 步，也就是說(shuō)平均每個(gè)節(jié)點(diǎn)需要 2 步，跟上面的結(jié)果相同。
說(shuō)一點(diǎn)題外話。
為什么 muduo 網(wǎng)絡(luò)庫(kù)的 Poller 要用 std::map<int, Channel*> 來(lái)管理文件描述符？
muduo 在正常使用的時(shí)候會(huì)用 EPollPoller，是對(duì) epoll(4) 的簡(jiǎn)單封裝，其中用 std::map<int, Channel*> channels_ 來(lái)保存 fd 到 Channel 對(duì)象的映射。我這里沒(méi)有用數(shù)組，而是用 std::map，原因有幾點(diǎn)：
- epoll_ctl() 是 O(lg N)，因?yàn)閮?nèi)核中用紅黑樹(shù)來(lái)管理 fd。因此用戶態(tài)用數(shù)組管理 fd 并不能降低時(shí)間復(fù)雜度，反而有可能增加內(nèi)存使用（用 hash 倒是不錯(cuò)）。不過(guò)考慮系統(tǒng)調(diào)用開(kāi)銷(xiāo)，map vs. vector 的實(shí)際速度差別不明顯。（題外話：總是遇到有人說(shuō) epoll 是 O(1) 云云，其實(shí) epoll_wait() 是 O(N)，N 是活動(dòng)fd的數(shù)目。poll 和 select 也都是 O(N)，不過(guò) N 的意義不同。仔細(xì)算下來(lái)，恐怕只有 epoll_create() 是 O(1) 的。也有人想把 epoll 改為數(shù)組，但是被否決了，因?yàn)檫@是開(kāi)歷史倒車(chē) https://lkml.org/lkml/2008/1/8/205 。）
- channels_ 只在 Channel 創(chuàng)建和銷(xiāo)毀的時(shí)候才會(huì)被訪問(wèn)，其他時(shí)候（修改關(guān)注的讀寫(xiě)事件）都是位于 assert() 中，用于 Debug 模式斷言。而 Channel 的創(chuàng)建和銷(xiāo)毀本身就伴隨著 socket 的創(chuàng)建和銷(xiāo)毀，涉及系統(tǒng)調(diào)用，channels_ 操作所占的比重極小。因此優(yōu)化 channels_ 屬于優(yōu)化 nop，是無(wú)意義的。
(.完.)