C++ STL set 与 map 底层封装原理详解

在深入理解 C++ STL 容器之前，我们通常知道 set 和 map 的底层实现都依赖于红黑树。但具体是如何通过模板机制将同一棵红黑树适配到这两种不同语义的容器上的？本章我们将拆解其封装细节。

一、认识 STL 中的 set 和 map

从接口上看，set 只接受一个类型参数（Key），而 map 接受两个（Key-Value）。但在库的实现层面，它们本质上都是基于 Key-Value 类型的红黑树构建的。

set：虽然对外表现为 set<Key>，内部实际是通过 rb_tree<Key, Key> 封装实现的。
map：对外表现为 map<Key, Value>，内部实际是通过 rb_tree<Key, pair<Key, Value>> 封装实现的。

这意味着我们需要设计一种通用的红黑树结构，能够根据传入的第二个模板参数灵活存储数据，同时保证查找逻辑始终基于 Key 进行。

二、修改红黑树以适应泛型存储

为了支持 set 和 map 的不同需求，红黑树的节点定义需要更加通用。

1. 节点定义

节点模板中引入泛型 T，使其既能存储 Key（用于 set），也能存储 pair<Key, Value>（用于 map）。

template<class T> struct RBTreeNode {
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    enum Colour { RED, BLACK };
    Colour _col;
    T _data;

    RBTreeNode(const T& data) :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) {}
};

2. 插入操作与 Key 提取策略

由于 set 和 map 比较的对象不同（一个是 Key，一个是 Pair 的 first），我们需要引入第三个模板参数 KeyOfT，这是一个仿函数，负责从存储的数据中提取出用于比较的 Key。

Set 场景：KeyOfT 直接返回 Key 本身。
Map 场景：KeyOfT 返回 pair.first。

这样，红黑树的插入逻辑就可以统一为：利用 KeyOfT 获取当前节点的 Key 值进行比较。

template<class K,  ,  >   {
     RBTreeNode<T> Node;
:
    {
         (_root == ) {
            _root =  (data);
            _root->_col = BLACK;
             ;
        }

        KeyOfT kot;
        Node* cur = _root;
        Node* parent = ;
         (cur) {
             ((cur->_data) < (data)) {
                parent = cur;
                cur = cur->_right;
            }   ((cur->_data) > (data)) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ; 
            }
        }

        cur =  (data);
         ((parent->_data) < (data)) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
        cur->_parent = parent;

        
         (parent && parent->_col == RED) {
            Node* grandparent = parent->_parent;
             (parent == grandparent->_left) {
                Node* uncle = grandparent->_right;
                 (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandparent->_col = RED;
                    cur = grandparent;
                    parent = cur->_parent;
                }  {
                     (cur == parent->_right) {
                        (parent);
                        std::(parent, cur);
                    }
                    (grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                    ;
                }
            }  {
                Node* uncle = grandparent->_left;
                 (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandparent->_col = RED;
                    cur = grandparent;
                    parent = cur->_parent;
                }  {
                     (cur == parent->_left) {
                        (parent);
                        std::(parent, cur);
                    }
                    (grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                    ;
                }
            }
        }
        _root->_col = BLACK;
         ;
    }
:
    Node* _root = ;
    ; 
    ; 
};

#pragma once #include <utility> enum Colour { RED, BLACK }; template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data; RBTreeNode(const T& data) :_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) {} }; template<class T, class Ref, class Ptr> struct __TreeIterator { typedef RBTreeNode<T> Node; Node* _node; typedef __TreeIterator Self; __TreeIterator(Node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return _node != s._node; } bool operator==(const Self& s) const { return _node == s._node; } Self& operator++() { if (_node->_right) { Node* cur = _node->_right; while (cur->_left) cur = cur->_left; _node = cur; } 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->_left) { Node* cur = _node->_left; while (cur->_right) cur = cur->_right; _node = cur; } else { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } }; template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef __TreeIterator<T, T&, T*> iterator; typedef __TreeIterator<T, const T&, const T*> const_iterator; iterator begin() { Node* cur = _root; while (cur && cur->_left) cur = cur->_left; return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* cur = _root; while (cur && cur->_left) cur = cur->_left; return const_iterator(cur); } const_iterator end() const { return const_iterator(nullptr); } pair<iterator, bool> Insert(const T& data) { if (!_root) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } KeyOfT kot; Node* cur = _root; Node* parent = nullptr; while (cur) { if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); if (kot(parent->_data) < kot(data)) parent->_right = cur; else parent->_left = cur; cur->_parent = parent; // 调整逻辑同上，此处省略以节省篇幅 _root->_col = BLACK; return make_pair(iterator(cur), true); } private: Node* _root = nullptr; void RotateL(Node* parent) {} // 简化示意 void RotateR(Node* parent) {} // 简化示意 };

C++ STL set 与 map 底层封装原理详解