C++ STL 深度剖析：std::set/std::map 紅黑樹實現細節與效能特性

std::set/std::map 是常用關聯式容器，也是 ADT（抽象資料類型），介面規定操作功能與複雜度。雖標準未強制底層結構，但所有 STL 實作皆採用紅黑樹。本文針對 GCC 4.7 內建 STL 實作，探討 8 個深度問題。

資料結構回顧

節點結構

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<typename Value>
struct rb_tree_node : public rb_tree_node_base {
    Value value_field_;
};

color_ 標記紅黑，parent_ 使非遞迴遍歷成為可能。

樹結構與 header 節點

template<typename Key, typename Value>
class rb_tree {
    struct rb_tree_impl {
        key_compare key_compare_;
        rb_tree_node_base header_;  // 非 rb_tree_node，無 value_field
        size_t node_count_;
    };
    rb_tree_impl impl_;
};

空樹時 header_ 大小固定 (6 pointers)，32-bit 24B、64-bit 48B。header_ 成員特殊含義：

• parent_ → root 節點
• left_ → 最左節點 (leftmost)
• right_ → 最右節點 (rightmost)
• color_ 固定紅色

迭代器

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_，begin() 指向第一節點。空樹時兩者相同。

八個深度問題解答

1. 為什麼 rb_tree 沒有 allocator 成員？

採用 Empty Base Class Optimization (EBCO)：rb_tree_impl 繼承 allocator，若為 empty class 則不佔空間。同理 key_compare 亦可優化（作者建議）。

2. 為什麼迭代器可以 pass-by-value？

迭代器僅含單一指標成員、無自訂 copy-ctor。x86-64 下透暫存器傳遞，比 const reference 更快（少一次解參考）。同理 muduo Date/Timestamp 設計為 pass-by-value。

3. 為什麼 header 有 left 指向 leftmost？

讓 begin() 達到 O(1)。無 left_ 時需從 root 走 log N 步。

4. 為什麼 header 有 right 指向 rightmost？

支援 insert(end(), value) 達到 分攤 O(1)。若 hint 為 end() 且值大於 rightmost，直接在 rightmost 右子節點插入。標準註釋錯誤宣稱 set_union 配合 inserter 可達線性，實測 inserter 每次插入後 ++iter (rightmost→header) 為 O(log N)，拖慢至 O(N log N)。

5. 為什麼 header color 固定紅色？

迭代器遞減時判斷是否為 end()：(node_->color_ == kRed && node_->parent_->parent_ == node_)。利用 header 紅色、root 黑色、header.parent=root、root.parent=header 的不變式。

6. 為什麼分 rb_tree_node_base 與 rb_tree_node 兩層？

將迭代器遞增/遞減、樹重平衡等複雜函數從標頭檔移至庫檔，減少模板程式碼膨脹（set<int> 與 set<string> 共享基礎函數），加快編譯。基類非為 OOP，純屬實作技巧。

7. 為什麼迭代器遞增遞減是分攤常數時間？

歸納法證明： 滿二叉樹深度 n，節點數 2^n-1，遍歷步數 f(n)=2f(n-1)+n，解得 f(n)=2^(n+1)-n-2 < 2^(n+1)。平均每節點 <2 步。
更簡單證明： 每條邊最多來回各走一次，N 節點有 N-1 邊，最多 2(N-1)+1 步，平均 2 步。

8. 為什麼 muduo Poller 用 std::map 管理 fd？

• epoll_ctl 核心內部用紅黑樹 O(log N)，用戶態用陣列無法降低複雜度，反而可能增加記憶體
• channels_ 僅在 Channel 建構/解構時存取，其他場合僅在 assert() 中除錯用
• Channel 生命週期伴隨 socket 系統呼叫，map 操作佔比極小，優化屬無意義

空間複雜度

每節點 4 pointers + value_type。含配置器對齊：32-bit 8B、64-bit 16B 對齊。set<int> 節點 24B/48B，百萬元素佔 48MB (x86-64)。set<int64_t> 與 set<int32_t> 佔用相同空間，set<int> 與 map<int,int> 同理。說明用 set 排序整數在時空效率上皆不明智。