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

我们知道，STL 中的 set 和 map 底层均基于红黑树实现。这一节我们来深入剖析它们是如何在红黑树基础上进行封装的。

STL 容器底层结构

通过查阅资料可以看到，set 通常只传递一个类型参数（Key），而 map 传递两个（Key-Value）。但实际上，库中实现的 set 和 map 底层都是 Key-Value 类型的红黑树。

具体来说：

set<Key> 实际是通过红黑树 rb_tree<Key, Key> 封装实现的；
map<Key, Value> 则是通过红黑树 rb_tree<Key, pair<Key, Value>> 封装实现的。

文章配图

这意味着两者使用的是同一种树结构，区别仅在于传递给红黑树的第二个模板参数不同：set 是 <Key, Key>，而 map 是 <Key, pair<Key, Value>>。

红黑树的泛型改造

由于 set 存储的是 Key，而 map 存储的是 pair<Key, Value>，我们需要将红黑树节点的模板设计为泛型存储。

节点定义

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) {}
};

此时红黑树类的模板参数虽然定义为两个，但为了适配后续需求，我们还需要增加第三个参数。

插入操作与 KeyOfT

在树的插入操作中，比较的关键是 Key 值。对于 set，第二个模板参数本身就是 Key；对于 map，第二个参数是 pair，需要取出 first 作为 Key。解决这个问题，可以在 set 和 map 层传递第三个模板参数给红黑树，这是一个仿函数类，重载了 () 运算符。

在 set 中实现内部类获取 Key：



 MyCreate {
< >   {
      {
        {  key; }
    };
:
    RBTree<K, K, SetKeyOfT> ;
};
}

#pragma once 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<T, Ref, Ptr> Self; typedef __TreeIterator<T, T&, T*> Iterator; __TreeIterator(const Iterator& it) :_node(it._node) {} __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->_left) cur = cur->_left; return iterator(cur); } iterator end() { return iterator(nullptr); } const_iterator begin() const { Node* cur = _root; while (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 == nullptr) { _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; while (parent && parent->_col == RED) { Node* grandparent = parent->_parent; if (parent == grandparent->_left) { Node* uncle = grandparent->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else { if (cur == parent->_left) { RotateR(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else { RotateL(parent); RotateR(grandparent); grandparent->_col = RED; cur->_col = BLACK; } break; } } else { Node* uncle = grandparent->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandparent->_col = RED; cur = grandparent; parent = grandparent->_parent; } else { if (cur == parent->_right) { RotateL(grandparent); parent->_col = BLACK; grandparent->_col = RED; } else { RotateR(parent); RotateL(grandparent); grandparent->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; return make_pair(iterator(cur), true); } void RotateL(Node* parent) { Node* cur = parent->_right; Node* curleft = cur->_left; Node* ppnode = parent->_parent; parent->_right = curleft; if (curleft != nullptr) curleft->_parent = parent; cur->_left = parent; parent->_parent = cur; if (ppnode == nullptr) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) ppnode->_left = cur; else ppnode->_right = cur; cur->_parent = ppnode; } } void RotateR(Node* parent) { Node* cur = parent->_left; Node* curright = cur->_right; Node* ppnode = parent->_parent; parent->_left = curright; if (curright != nullptr) curright->_parent = parent; cur->_right = parent; parent->_parent = cur; if (ppnode == nullptr) { _root = cur; cur->_parent = nullptr; } else { if (ppnode->_left == parent) ppnode->_left = cur; else ppnode->_right = cur; cur->_parent = ppnode; } } private: Node* _root = nullptr; };

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