↓推荐关注↓

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的开发资源库。 日常分享热门、有趣和实用的开源项目～" data-from="0">

std::set/std::map （以下用 std::map 代表） 是常用的关联式容器，也是 ADT（抽象数据类型）。也就是说，其接口（不是 OO 意义下的 interface）不仅规定了操作的功能，还规定了操作的复杂度（代价/cost）。例如 set::insert(iterator first, iterator last) 在通常情况下是 O(N log N)，N 是区间的长度；但是如果 [first, last) 已经排好序（在 key_compare 意义下），那么复杂度将会是 O(N)。

尽管 C 标准没有强求 std::map 底层的数据结构，但是根据其规定的时间复杂度，现在所有的 STL 实现都采用平衡二叉树来实现 std::map，而且用的都是红黑树。《算法导论（第 2 版）》第 12、13 章介绍了二叉搜索树和红黑树的原理、性质、伪代码，侯捷先生的《STL 源码剖析》第 5 章详细剖析了 SGI STL 的对应实现。本文对 STL 中红黑树（rb_tree）的实现问了几个稍微深入一点的问题，并给出了我的理解。

本文剖析的是 G 4.7 自带的这一份 STL 实现及其特定行为，与《STL 源码剖析》的版本略有区别。为了便于阅读，文中的变量名和 class 名都略有改写（例如 _Rb_tree_node 改为 rb_tree_node）。本文不谈红黑树的平衡算法，在我看来这属于“旁枝末节”（见陈硕《谈一谈网络编程学习经验》对此的定义），因此也就不关心节点的具体颜色了。

数据结构回顾

先回顾一下数据结构教材上讲的二叉搜索树的结构，节点（Node）一般有三个数据成员（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  。

节点

Node 有 5 个成员，除了 left、right、data，还有 color 和 parent。

C 实现，位于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 的存在很好理解，红黑树每个节点非红即黑，需要保存其颜色（颜色只需要 1-bit 数据，一种节省内存的优化措施是把颜色嵌入到某个指针的最高位或最低位，Linux 内核里的 rbtree 是嵌入到 parent 的最低位）；parent 的存在使得非递归遍历成为可能，后面还将再谈到这一点。

树

Tree 有更多的成员，它包含一个完整的 rb_tree_node_base（color/parent/left/right），还有 node_count 和 key_compare 这两个额外的成员。

这里省略了一些默认模板参数，如 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*)，与模板类型参数无关。在 32-bit 上是 24 字节，在 64-bit 上是 48 字节，很容易用代码验证这一点。另外容易验证 std::set 和 std::map 的 sizeof() 是一样的。

注意 rb_tree 中的 header 不是 root 节点，其 left 和 right 成员也不是指向左右子节点，而是指向最左边节点（left_most）和最右边节点（right_most），后面将会介绍原因，是为了满足时间复杂度。header.parent 指向 root 节点，root.parent 指向 header，header 固定是红色，root 固定是黑色。在插入一个节点后，数据结构如下图。

继续插入两个节点，假设分别位于 root 的左右两侧，那么得到的数据结构如下图所示（parent 指针没有全画出来，因为其指向很明显），注意 header.left 指向最左侧节点，header.right 指向最右侧节点。

迭代器

rb_tree 的 iterator 的数据结构很简单，只包含一个 rb_tree_node_base 指针，但是其 /--操作却不见得简单（具体实现函数不在头文件中，而在 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\