# STL容器内核：基于红黑树的set与map实现剖析

在C++标准库的底层，set和map容器巧妙地共享同一颗红黑树骨架。这种设计展现了泛型编程的强大威力——用同一套数据结构支撑起两种截然不同的抽象接口。

## 红黑树基础：自平衡的二叉搜索树

红黑树是一种自平衡的二叉搜索树，它通过五个约束条件确保树的高度保持在对数级别：

```cpp

// 红黑树节点基本结构

enum Color { RED, BLACK };

template<typename T>

struct RBTreeNode {

    T data;

    Color color;

    RBTreeNode* parent;

    RBTreeNode* left;

    RBTreeNode* right;

    

    RBTreeNode(const T& val, Color c = RED)

        : data(val), color(c), parent(nullptr), 

          left(nullptr), right(nullptr) {}

};

```

红黑树的五个核心规则：

1. 每个节点要么红色，要么黑色

2. 根节点是黑色

3. 所有叶子节点（NIL节点）是黑色

4. 红色节点的两个子节点都是黑色

5. 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

## STL中的红黑树实现框架

STL实际使用更复杂的节点结构和模板设计：

```cpp

// 简化版STL红黑树节点结构

template<typename Value>

struct RBTreeNodeImpl {

    typedef RBTreeNodeImpl<Value>* LinkType;

    

    Value value_field;

    Color color;

    LinkType parent;

    LinkType left;

    LinkType right;

};

// 红黑树基类框架

template<typename Key, typename Value, typename KeyOfValue,

         typename Compare, typename Alloc = allocator<Value>>

class RBTree {

protected:

    typedef RBTreeNodeImpl<Value> RBTreeNode;

    

public:

    typedef Key key_type;

    typedef Value value_type;

    typedef Compare key_compare;

    

protected:

    RBTreeNode* header;      // 特殊头节点

    size_t node_count;       // 节点数量

    key_compare comp;        // 比较函数

    

    // 关键操作：左旋、右旋、插入修复、删除修复

    void rotate_left(RBTreeNode* x);

    void rotate_right(RBTreeNode* x);

    void insert_fixup(RBTreeNode* z);

    void erase_fixup(RBTreeNode* x);

    

public:

    // 迭代器支持

    iterator begin() { return leftmost(); }

    iterator end() { return header; }

    

    // 核心操作接口

    pair<iterator, bool> insert_unique(const value_type& x);

    iterator find(const key_type& k);

    size_type erase(const key_type& k);

    

private:

    // 内部辅助函数

    RBTreeNode* create_node(const value_type& x);

    void destroy_node(RBTreeNode* p);

    void insert(RBTreeNode* z);

    RBTreeNode* copy_tree(RBTreeNode* x, RBTreeNode* p);

};

```

## set的实现：基于红黑树的简单包装

set本质上是一个键值相同的红黑树容器：

```cpp

// set容器实现简析

template<typename Key, typename Compare = less<Key>,

         typename Alloc = allocator<Key>>

class set {

public:

    typedef Key key_type;

    typedef Key value_type;

    typedef Compare key_compare;

    typedef Compare value_compare;

    

private:

    // 关键：定义从值提取键的仿函数

    struct Identity {

        const key_type& operator()(const value_type& x) const {

            return x;  // set中键和值相同

        }

    };

    

    // 内部使用红黑树

    typedef RBTree<key_type, value_type, Identity,

                   key_compare, Alloc> RepType;

    RepType t;  // 实际的树容器

    

public:

    // 迭代器类型（底层树迭代器的包装）

    typedef typename RepType::const_iterator iterator;

    typedef typename RepType::const_iterator const_iterator;

    

    // 构造函数

    set() : t(Compare()) {}

    explicit set(const Compare& comp) : t(comp) {}

    

    template<typename InputIterator>

    set(InputIterator first, InputIterator last)

        : t(Compare()) {

        t.insert_range_unique(first, last);

    }

    

    // 容量操作

    bool empty() const { return t.empty(); }

    size_type size() const { return t.size(); }

    

    // 修改操作

    pair<iterator, bool> insert(const value_type& x) {

        return t.insert_unique(x);

    }

    

    template<typename InputIterator>

    void insert(InputIterator first, InputIterator last) {

        t.insert_range_unique(first, last);

    }

    

    // 查找操作

    iterator find(const key_type& x) const {

        return t.find(x);

    }

    

    size_type count(const key_type& x) const {

        return t.find(x) == t.end() ? 0 : 1;

    }

    

    // 删除操作

    size_type erase(const key_type& x) {

        return t.erase(x);

    }

    

    void erase(iterator position) {

        t.erase(position);

    }

    

    // 范围操作

    iterator lower_bound(const key_type& x) const {

        return t.lower_bound(x);

    }

    

    iterator upper_bound(const key_type& x) const {

        return t.upper_bound(x);

    }<"m4.s6k3.org.cn"><"a6.s6k3.org.cn"><"d3.s6k3.org.cn">

    

    // 交换

    void swap(set& other) {

        t.swap(other.t);

    }

    

    // 比较操作

    key_compare key_comp() const { return t.key_comp(); }

    value_compare value_comp() const { return t.key_comp(); }

};

```

## map的实现：键值分离的红黑树

map需要在红黑树节点中存储键值对：

```cpp

// map容器实现核心

template<typename Key, typename T, typename Compare = less<Key>,

         typename Alloc = allocator<pair<const Key, T>>>

class map {

public:

    typedef Key key_type;

    typedef T mapped_type;

    typedef pair<const key_type, mapped_type> value_type;

    typedef Compare key_compare;

    

private:

    // 从pair中提取键的仿函数

    struct SelectKey {

        const key_type& operator()(const value_type& x) const {

            return x.first;

        }

    };

    

    // 内部红黑树类型

    typedef RBTree<key_type, value_type, SelectKey,

                   key_compare, Alloc> RepType;

    RepType t;

    

public:

    // 迭代器类型

    typedef typename RepType::iterator iterator;

    typedef typename RepType::const_iterator const_iterator;

    

    // 构造函数

    map() : t(Compare()) {}

    explicit map(const Compare& comp) : t(comp) {}

    

    template<typename InputIterator>

    map(InputIterator first, InputIterator last)

        : t(Compare()) {

        t.insert_range_unique(first, last);

    }

    

    // 元素访问

    mapped_type& operator[](const key_type& k) {

        // 使用lower_bound和insert实现

        iterator i = lower_bound(k);

        if (i == end() || key_comp()(k, (*i).first)) {

            i = insert(i, value_type(k, mapped_type()));

        }

        return (*i).second;

    }

    

    mapped_type& at(const key_type& k) {

        iterator i = find(k);

        if (i == end()) {

            throw out_of_range("map::at");

        }

        return (*i).second;

    }

    

    const mapped_type& at(const key_type& k) const {

        const_iterator i = find(k);

        if (i == end()) {

            throw out_of_range("map::at");

        }

        return (*i).second;

    }

    

    // 插入操作

    pair<iterator, bool> insert(const value_type& x) {

        return t.insert_unique(x);

    }

    

    template<typename InputIterator>

    void insert(InputIterator first, InputIterator last) {

        t.insert_range_unique(first, last);

    }

    

    // 删除操作

    size_type erase(const key_type& x) {

        return t.erase(x);

    }

    

    void erase(iterator position) {

        t.erase(position);

    }

    

    void erase(iterator first, iterator last) {

        t.erase(first, last);

    }

    

    // 查找操作

    iterator find(const key_type& x) {

        return t.find(x);

    }

    

    const_iterator find(const key_type& x) const {

        return t.find(x);

    }

    

    // 容量操作

    bool empty() const { return t.empty(); }

    size_type size() const { return t.size(); }

    

    // 交换

    void swap(map& other) {

        t.swap(other.t);

    }

    

    // 比较操作

    key_compare key_comp() const { return t.key_comp(); }

    

    // 值比较器

    class value_compare {

        friend class map;

    protected:

        Compare comp;

        value_compare(Compare c) : comp(c) {}

    public:

        bool operator()(const value_type& x, const value_type& y) const {

            return comp(x.first, y.first);

        }

    };

    

    value_compare value_comp() const { return value_compare(key_comp()); }

};

```

## 迭代器设计：遍历红黑树的关键

红黑树迭代器需要支持中序遍历：

```cpp

// 红黑树迭代器实现框架

template<typename T, typename Ref, typename Ptr>

struct RBTreeIterator {

    typedef RBTreeIterator<T, T&, T*> iterator;

    typedef RBTreeIterator<T, const T&, const T*> const_iterator;

    typedef RBTreeIterator<T, Ref, Ptr> self;

    

    typedef bidirectional_iterator_tag iterator_category;

    typedef T value_type;

    typedef Ref reference;

    typedef Ptr pointer;

    typedef ptrdiff_t difference_type;

    

    typedef RBTreeNodeImpl<T>* LinkType;

    LinkType node;

    

    // 构造函数

    RBTreeIterator() : node(nullptr) {}

    explicit RBTreeIterator(LinkType x) : node(x) {}

    

    // 解引用操作符

    reference operator*() const { return node->value_field; }

    pointer operator->() const { return &(operator*()); }

    

    // 前向迭代

    self& operator++() {

        increment();

        return *this;

    }

    

    self operator++(int) {

        self tmp = *this;

        increment();

        return tmp;

    }

    

    // 后向迭代

    self& operator--() {

        decrement();

        return *this;

    }

    

    self operator--(int) {

        self tmp = *this;

        decrement();

        return tmp;

    }

    <"h7.s6k3.org.cn"><"v9.s6k3.org.cn"><"s2.s6k3.org.cn">

    // 比较操作

    bool operator==(const self& x) const { return node == x.node; }

    bool operator!=(const self& x) const { return node != x.node; }

    

private:

    // 关键：寻找中序遍历的下一个节点

    void increment() {

        if (node->right != nullptr) {

            // 如果有右子树，找右子树的最左节点

            node = node->right;

            while (node->left != nullptr) {

                node = node->left;

            }

        } else {

            // 否则找第一个左子树包含当前节点的祖先

            LinkType y = node->parent;

            while (node == y->right) {

                node = y;

                y = y->parent;

            }

            if (node->right != y) {

                node = y;

            }

        }

    }

    

    // 寻找中序遍历的前一个节点

    void decrement() {

        if (node->color == RED && node->parent->parent == node) {

            // 特殊情况：header节点

            node = node->right;

        } else if (node->left != nullptr) {

            // 如果有左子树，找左子树的最右节点

            node = node->left;

            while (node->right != nullptr) {

                node = node->right;

            }

        } else {

            // 否则找第一个右子树包含当前节点的祖先

            LinkType y = node->parent;

            while (node == y->left) {

                node = y;

                y = y->parent;

            }

            node = y;

        }

    }

};

```

## 性能特性与使用指导

基于红黑树的set和map具有以下性能特点：

- 插入、删除、查找：O(log n)时间复杂度

- 有序遍历：支持基于比较的有序遍历

- 内存使用：每个节点需要额外存储颜色和指针信息

```cpp

// 使用示例：统计单词频率

void countWordFrequency(const vector<string>& words) {

    map<string, int> wordCount;

    

    for (const auto& word : words) {

        // 自动处理重复键

        wordCount[word]++;

    }

    

    // 有序输出

    for (const auto& pair : wordCount) {

        cout << pair.first << ": " << pair.second << endl;

    }

}

// 使用示例：集合运算

void setOperations() {

    set<int> s1 = {1, 3, 5, 7, 9};

    set<int> s2 = {2, 3, 5, 7, 11};

    

    // 交集

    set<int> intersection;

    set_intersection(s1.begin(), s1.end(),

                     s2.begin(), s2.end(),

                     inserter(intersection, intersection.begin()));

    

    // 并集

    set<int> unionSet;

    set_union(s1.begin(), s1.end(),

              s2.begin(), s2.end(),

              inserter(unionSet, unionSet.begin()));

}

```

set和map的设计展现了C++模板和泛型编程的精髓：通过精心的抽象和复用，用同一套红黑树实现支撑起多个容器接口。这种设计不仅保证了代码的高效执行，还确保了不同容器间行为的一致性。理解这一底层实现，有助于开发人员更好地利用这些容器，并能在需要时实现自定义的关联容器。