SGI-STL30 的 stl_set.h 和 stl_map.h 都很薄,真正的实现全在 stl_tree.h 的 rb_tree 里。把源码的关键几行抽出来看,两个容器几乎是同一份代码套了两件外套:

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set
{
public:
    typedef Key key_type;
    typedef Key value_type;
 
private:
    typedef rb_tree<key_type, value_type,
                    identity<value_type>, key_compare, Alloc> rep_type;
    rep_type t;
};
 
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map
{
public:
    typedef Key key_type;
    typedef T mapped_type;
    typedef pair<const Key, T> value_type;
 
private:
    typedef rb_tree<key_type, value_type,
                    select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;
};

rb_tree 的第二个模板参数 Value 决定结点里存什么:set 传 Key,map 传 pair<const Key, T>。第三个参数 KeyOfValue 决定怎么从这个 Value 里取出键:set 用恒等函数 identity,map 用取 first 的 select1st。一棵红黑树因此既能做 key 场景,也能做 key/value 场景。

源码框架图:set 的 value_type 是 Key,map 的 value_type 是键值对,两者都作为第二个模板参数传进 rb_tree,结点真正存的就是 value_type

课件顺带吐槽了源码命名不统一:set 用 Key,map 用 Key 和 T,rb_tree 又用 Key 和 Value。这确实是历史包袱,读源码时记不住哪个名字对应哪一层,最好的办法是盯住"结点里存的那个类型"。

结点泛型化之后,树不知道自己该比谁

按源码的形状把结点改成只认一个类型参数:

#include <iostream>
#include <string>
#include <utility>
 
using std::pair;
 
enum Colour
{
    RED,
    BLACK
};
 
template<class T>
struct RBTreeNode
{
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
 
    RBTreeNode(const T& data)
        : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)
    {}
};

T 是 set 的 K,也是 map 的 pair<const K, V>。树不再硬编码"结点里存的是什么",但立刻带来一个问题:插入时怎么比较两个 T?

set 实例化时 T 是 const K,结点里那个 _data 本身就是 const K 成员,构造完成之后任何路径都改不了它。

map 的 T 是 pair,而 std::pair 的 operator< 是字典序:先比 first,相等再比 second。如果直接拿 T 比大小,{"apple", 1} 和 {"apple", 2} 会被判成两个不同的元素:

bit::map<std::string, int> dict;
dict.insert({"apple", 1});
dict.insert({"apple", 2});   // key 相同,但 pair 的 second 不同

遍历时会打印两个 apple,size 也是 2。set 不会犯这个错,因为它的 T 就是 key 本身。所以泛型化的关键不是结点,而是把"比哪个字段"从结点里拿出去:给红黑树再传一个仿函数 KeyOfT,专门从 T 里把键取出来。

struct MapKeyOfT
{
    const K& operator()(const pair<const K, V>& kv) const
    {
        return kv.first;
    }
};
 
struct SetKeyOfT
{
    const K& operator()(const K& key) const
    {
        return key;
    }
};

课件这一版把 MapKeyOfT 的形参写成了 const pair<K, V>&,而树里存的是 pair<const K, V>。这样也能编译,靠的是 pair 的转换构造函数临时造一个 pair<K, V>;键是 string 时,每次比较都要拷一份字符串。改成 const pair<const K, V>& 就只传引用。

仿函数本身没有成员,kot(x) 一般会被内联成一次成员访问,运行时开销可以忽略;代价是 set 和 map 各自要定义一份,模板参数也因此多了一个。

模板参数最终是三个:template<class K, class T, class KeyOfT>。T 已经决定结点存什么了,K 为什么还要单独传?因为两个接口收的东西不一样:insert 收完整的 T(map 是一对键值,set 是一个键),find 和 erase 只收 K。find 的签名要是只有 T,map 就没法只用一个键来查。set 里这两个参数恰好相同,map 里完全不同。

树里的所有比较都改成通过仿函数取键,写成 kot(cur->_data) < kot(data) 和 kot(data) < kot(cur->_data)。只写 <、不写 >,是因为 a > b 可以写成 b < a,这样自定义类型只需要一个严格弱序;相等也不靠 ==,而是"既不小于、也不大于"。

迭代器:++ 只看当前结点和祖先

树的结点之间没有物理上的"下一个",++ 只能靠结构推算。规则两句:

  • 右子树不为空,下一个是右子树的最左结点;
  • 右子树为空,沿着祖先往上爬,直到"当前结点是父亲的左孩子"为止,那个父亲就是下一个。

如果一路爬上去都没遇到"孩子是父亲的左",说明当前结点是整棵树的最右结点,parent 最终变成空,正好用空指针表示 end()。

迭代器类别是双向:++ 和 -- 都能走,但没有 it + n,想跳 n 步只能循环。begin()/end() 各有 const 重载,const set 拿到的是 ConstIterator,所以 Print 的参数写成 const set& 也能遍历。

中序迭代器的走位:begin 是最左的 10,然后 15、18、25、30、35、40、50,走到 50 之后 ++ 得到 end;每一步都符合"右子树最左"或"孩子是父亲左"

-- 是 ++ 的镜像:左子树不为空就取左子树最右结点;否则往上找"孩子是父亲的右"。--end() 是个特殊情形:_node 是空,推不出前驱,所以迭代器里多存一个 _root,从根一路往右走到底。

SGI 源码不付这个代价,它给红黑树加了一个哨兵头结点 header:header 与根互为父亲,header.left 指向最左结点,header.right 指向最右结点。

SGI 的哨兵头结点:header 挂在根 18 上方,左指针指向最小结点 10,右指针指向最大结点 50;begin 是 header.left,end 是 header 自己,--end 是 header.right

有了它,begin()、end()、--end() 都不用特判,空树也能统一处理。源码里 decrement() 那句"红结点且父亲的父亲是自己"看着莫名其妙,其实就是在认"当前结点是不是 header"。教学版用多存一个指针换掉了这份特判,代价是每个迭代器多 8 字节。

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T, Ref, Ptr> Self;
 
    Node* _node;
    Node* _root;
 
    RBTreeIterator(Node* node, Node* root)
        : _node(node), _root(root)
    {}
 
    Ref operator*() const
    {
        return _node->_data;
    }
 
    Ptr operator->() const
    {
        return &_node->_data;
    }
 
    Self& operator++()
    {
        if (_node->_right)
        {
            Node* leftMost = _node->_right;
            while (leftMost->_left)
            {
                leftMost = leftMost->_left;
            }
            _node = leftMost;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
 
    Self& operator--()
    {
        if (_node == nullptr)
        {
            Node* rightMost = _root;
            while (rightMost && rightMost->_right)
            {
                rightMost = rightMost->_right;
            }
            _node = rightMost;
        }
        else if (_node->_left)
        {
            Node* rightMost = _node->_left;
            while (rightMost->_right)
            {
                rightMost = rightMost->_right;
            }
            _node = rightMost;
        }
        else
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = cur->_parent;
            }
            _node = parent;
        }
        return *this;
    }
 
    bool operator==(const Self& s) const
    {
        return _node == s._node;
    }
 
    bool operator!=(const Self& s) const
    {
        return _node != s._node;
    }
};

一棵完整的泛型红黑树

Insert 除了比较换成 KeyOfT,其余与普通红黑树一致:新结点涂红,父亲是红才修,叔叔红只变色,叔叔黑按形状单旋或双旋,最后无条件把根刷黑。返回类型是 pair<Iterator, bool>,两个结果都指向这个 key 最终所在的结点——失败时 insert 顺便当了一次查找,operator[] 要的就是这一点。

template<class K, class T, class KeyOfT>
class RBTree
{
    typedef RBTreeNode<T> Node;
 
public:
    typedef RBTreeIterator<T, T&, T*> Iterator;
    typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
 
    RBTree() = default;
 
    RBTree(const RBTree&) = delete;
    RBTree& operator=(const RBTree&) = delete;
 
    ~RBTree()
    {
        Destroy(_root);
        _root = nullptr;
    }
 
    Iterator Begin()
    {
        Node* leftMost = _root;
        while (leftMost && leftMost->_left)
        {
            leftMost = leftMost->_left;
        }
        return Iterator(leftMost, _root);
    }
 
    Iterator End()
    {
        return Iterator(nullptr, _root);
    }
 
    ConstIterator Begin() const
    {
        Node* leftMost = _root;
        while (leftMost && leftMost->_left)
        {
            leftMost = leftMost->_left;
        }
        return ConstIterator(leftMost, _root);
    }
 
    ConstIterator End() const
    {
        return ConstIterator(nullptr, _root);
    }
 
    pair<Iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return pair<Iterator, bool>(Iterator(_root, _root), true);
        }
 
        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kot(data) < kot(cur->_data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return pair<Iterator, bool>(Iterator(cur, _root), false);
            }
        }
 
        cur = new Node(data);
        Node* newnode = cur;
        cur->_col = RED;
        if (kot(parent->_data) < kot(data))
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
 
        while (parent && parent->_col == RED)
        {
            Node* grand = parent->_parent;
 
            if (parent == grand->_left)
            {
                Node* uncle = grand->_right;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grand->_col = RED;
                    cur = grand;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grand);
                        parent->_col = BLACK;
                        grand->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);
                        RotateR(grand);
                        cur->_col = BLACK;
                        grand->_col = RED;
                    }
                    break;
                }
            }
            else
            {
                Node* uncle = grand->_left;
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grand->_col = RED;
                    cur = grand;
                    parent = cur->_parent;
                }
                else
                {
                    if (cur == parent->_right)
                    {
                        RotateL(grand);
                        parent->_col = BLACK;
                        grand->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grand);
                        cur->_col = BLACK;
                        grand->_col = RED;
                    }
                    break;
                }
            }
        }
 
        _root->_col = BLACK;
        return pair<Iterator, bool>(Iterator(newnode, _root), true);
    }
 
    Iterator Find(const K& key)
    {
        KeyOfT kot;
        Node* cur = _root;
        while (cur)
        {
            if (kot(cur->_data) < key)
            {
                cur = cur->_right;
            }
            else if (key < kot(cur->_data))
            {
                cur = cur->_left;
            }
            else
            {
                return Iterator(cur, _root);
            }
        }
        return End();
    }
 
private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
 
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
 
        Node* parentParent = parent->_parent;
 
        subR->_left = parent;
        parent->_parent = subR;
 
        if (parentParent == nullptr)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->_left)
            {
                parentParent->_left = subR;
            }
            else
            {
                parentParent->_right = subR;
            }
            subR->_parent = parentParent;
        }
    }
 
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
 
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
 
        Node* parentParent = parent->_parent;
 
        subL->_right = parent;
        parent->_parent = subL;
 
        if (parentParent == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (parent == parentParent->_left)
            {
                parentParent->_left = subL;
            }
            else
            {
                parentParent->_right = subL;
            }
            subL->_parent = parentParent;
        }
    }
 
    void Destroy(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }
 
    Node* _root = nullptr;
};

课件最后一版 Find 的函数体里还写着 cur->_kv.first,而泛型结点里根本没有 _kv 这个成员,照抄会直接编译失败。泛型化之后,取键必须走 kot(cur->_data)。

while 每一轮开头都要重新取 grand = parent->_parent,不能缓存。上一轮走了变色分支后,cur 变成了原来的 grand,parent 也跟着换了,缓存下来的 grand 已经过期。旋转里 parentParent 必须在 parent->_parent = subL; 之前取,subLR、subRL 可能为空。这三处都是断链的来源。

Insert 成功和失败两个分支都构造 Iterator(结点, _root),因为迭代器要存根指针才能处理 --end();只传结点的话,-- 到端点就没法回头。每个迭代器因此多存一个指针,代价是两个指针而不是一个;和遍历时少写一份特判相比,这个换法在教学代码里划算。

Find 走空时返回 End(),也就是空指针包装出来的迭代器,调用方统一用 != end() 判断,不需要另一套约定。

const 写在 T 里,不是写在迭代器外面

容器按键排好序,键一旦被用户改掉,整棵树就废了,而且不会立刻报错,只会在下次 find 时莫名其妙落空。所以"键不可改"必须做成类型层面的保证,不能只靠文档提醒。

做法是把它塞进 T 本身:

RBTree<K, const K, SetKeyOfT> _t;              // set:元素整体只读
RBTree<K, pair<const K, V>, MapKeyOfT> _t;     // map:first 只读,second 可写

set 的 T 是 const K,迭代器解引用得到 const K&,*it += 2 编译期就被拒。map 的 const 只加在 pair 的第一个成员上,it->first = "x" 同样编不过,it->second 却可以照改。标准库的 value_type 就是 std::pair<const Key, T>,cppreference 的 std::map 页面写得很明确。

Iterator 和 ConstIterator 是同一个模板用不同的 Ref、Ptr 实例化出来的两个类型,不能互相赋值;const 成员函数返回的是 ConstIterator,非 const 对象调用 begin() 返回 Iterator。这也是 begin/end 要写两份的原因。

为什么不把 set 的 iterator 直接 typedef 成 ConstIterator 就完事?那只是接口层面的承诺,结点里的数据本身仍然可写,任何拿到内部指针的路径都能改,比如 Insert 里的 newnode。把 const 放进 T,则指向这个结点的任何指针、引用、迭代器天生只能读。

这一层还会带出一个模板语法坑:导出依赖类型时 typename 不能省。

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

RBTree<K, const K, SetKeyOfT>::Iterator 依赖模板参数,编译器不知道它是类型还是静态成员,漏掉 typename 就是一行编译错误。

operator[] 的魔法,前提是 insert 返回两个值

dict["没见过的 key"] = 值 能凭空造出词条,靠的不是 [] 本身,而是 Insert 的返回值。[] 同时要知道两件事:key 以前在不在,对应的结点在哪。只返回 bool 的话,[] 拿到结果还得再 Find 一次,白多走一趟 O(logN)。

    V& operator[](const K& key)
    {
        pair<iterator, bool> ret = insert(pair<const K, V>(key, V()));
        return ret.first->second;
    }

key 不存在就插一个值初始化的 V 再返回引用,存在就直接拿到旧结点的引用。于是同一个 [] 具备插入、查找、修改三种语义:dict["left"] = "左边" 是插入加赋值,dict["left"] = "左边、剩余" 是纯修改,dict["string"]; 这种看起来只读的写法也会真的插一条空 value 进去。

这里还有一次容易被忽略的转换:外部传进来的是 pair<const K, V>,构造时 key、value 各拷一次。标准库因此另外提供了收 value_type 的重载,让调用方自己决定在哪一步转换;教学版图省事,把这次拷贝留在函数里。

V() 要求 V 能默认构造。自定义类型不写默认构造函数时,[] 直接编译失败;只读的接口标准库提供的是 at(),找不到抛 std::out_of_range,也不会往表里插东西。标准库也没有给 map 提供 const 版的 operator[]:一个只读接口却可能修改容器,语义上说不通。

组装成 mymap 与 myset

set 只有一层转发:插入收 K,查出 Iterator,内部树实例化成 RBTree<K, const K, SetKeyOfT>。

namespace bit
{
template<class K>
class set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key) const
        {
            return key;
        }
    };
 
public:
    typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
 
    iterator begin() { return _t.Begin(); }
    iterator end() { return _t.End(); }
    const_iterator begin() const { return _t.Begin(); }
    const_iterator end() const { return _t.End(); }
 
    pair<iterator, bool> insert(const K& key) { return _t.Insert(key); }
    iterator find(const K& key) { return _t.Find(key); }
 
private:
    RBTree<K, const K, SetKeyOfT> _t;
};
}

map 多一个 operator[],insert 收的是整个键值对。insert 的形参写成 const pair<const K, V>&,dict.insert({"sort", "排序"}) 的花括号会直接构造一个临时 pair 绑定到 const 引用,不用显式写 make_pair 或 pair<std::string, std::string>("sort", "排序")。

namespace bit
{
template<class K, class V>
class map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<const K, V>& kv) const
        {
            return kv.first;
        }
    };
 
public:
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
 
    iterator begin() { return _t.Begin(); }
    iterator end() { return _t.End(); }
    const_iterator begin() const { return _t.Begin(); }
    const_iterator end() const { return _t.End(); }
 
    pair<iterator, bool> insert(const pair<const K, V>& kv)
    {
        return _t.Insert(kv);
    }
 
    iterator find(const K& key) { return _t.Find(key); }
 
    V& operator[](const K& key)
    {
        pair<iterator, bool> ret = insert(pair<const K, V>(key, V()));
        return ret.first->second;
    }
 
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

两棵树都持有裸指针,析构函数会 delete 每个结点,所以拷贝必须管住。默认生成的拷贝构造和赋值是浅拷贝,两棵树指向同一批结点,析构时二次释放。上面 RBTree 里用 = delete 关掉了拷贝;要支持拷贝就得自己实现深拷贝:先序复制结点,递归接上左右和父指针,销毁则后序释放。三件套写全之后,树才能安全地按值传递或返回。课件给的类里只写了析构,没写拷贝控制,直接使用会踩到这个问题。

跑一遍:

void Print(const bit::set<int>& s)
{
    bit::set<int>::const_iterator it = s.end();
    while (it != s.begin())
    {
        --it;
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}
 
int main()
{
    bit::set<int> s;
    int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
    for (int e : a)
    {
        s.insert(e);
    }
    for (auto e : s)
    {
        std::cout << e << ' ';
    }
    std::cout << '\n';        // 1 2 3 4 5 6 7 14 15 16
    Print(s);                 // 16 15 14 7 6 5 4 3 2 1
 
    bit::map<std::string, std::string> dict;
    dict.insert({"sort", "排序"});
    dict.insert({"left", "左边"});
    dict["insert"] = "插入";
    dict["string"];           // 插入 {"string", ""}
 
    for (const auto& e : dict)
    {
        std::cout << e.first << ':' << e.second << '\n';
    }
    return 0;
}

Print 从 end() 开始往回走,正好检验 -- 的实现;输出方向与 begin 相反,说明 -- 和 ++ 用的不是同一个分支,--end() 里那句从根往右走到底也确实生效了。dict["string"]; 一行同时检验 [] 的插入语义和空串的默认构造。到这里,set 和 map 不再是两个容器,而是同一棵树的两件外套:T 决定结点存什么,KeyOfT 决定从里面抠哪个字段,const 的位置决定谁能改,Insert 的返回值决定上层能不能实现 []。