C++ 基于红黑树实现 set 和 map 容器

前言

本章将基于红黑树模拟实现 STL 库中的 set 和 map 这两类容器，主要目的是加深对其使用原理及红黑树机制的理解。

1. 分析源码

map 和 set 在 STL 库中是由红黑树来实现的。SGI-STL 源代码中，map 和 set 的实现结构核心部分如下：

// stl_set.h
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; // red-black tree representing set
};

// stl_map.h
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; // red-black tree representing map
};

通过对源码的分析，发现 rb_tree 使用了泛型思想。它通过第二个模板参数 Value 决定 __rb_tree_node 中存储的数据类型。set 实例化时第二个模板参数给的是 key，map 实例化时给的是 。这样一棵红黑树既可以实现 key 搜索场景的 set，也可以实现 key/value 搜索场景的 map。