C++ 使用红黑树封装 map 与 set

源码分析

对于 map 与 set，它们一个是 KV 模型，一个是 K 模型，那我们要写两个红黑树吗？

我们可以发现，红黑树在底层不知道你传给它的是什么，为了兼容 map 与 set 它搞了两个参数。

但是搞了两个参数后，第一个模板参数 Key 是不是有点多余呢？

对于 set 而言，两个 K 确实是有点多余；对于 map 来说，pair 里面也有 K，好像也有点多余。如果只留第二个模板参数，_rb_tree_node，为 set 时 Value 为 K；为 map 时 Value 为 pair<K,V>，好像也没问题。对于插入操作，set 是 k，map 是 pair 还挺好；但是对于查找操作时，set 使用 Value 没问题；map 查找时也要使用 Value，但 map 的 Value 是一个 pair(有 K，V)，那我既然知道了 K 和 V，我还查找什么呢？所以第一个模板参数不多于，反而是必须。

但还有一个问题，在插入操作时，涉及数据比较大小。但是 map 的 Value 是一个 pair，还得取里面的 key；set 的 Value 就是 key，此时就比较麻烦。pair 默认的比较规则是 first 比完 second 比，不符合我们的预期。因此我们还要给红黑树传递一个仿函数，以便获取 key。

调整红黑树的结构搭建 map、set

那我们之前实现的红黑树的结构就得做一下调整了。

除了上面呈现出来的模板参数以外，还可以传递自定义的比较规则模板 Compare。

下面是 map 与 set 的基本框架。

原来红黑树中涉及数据比较大小的地方，都得回调传递过来的 KeyOfT 获取 Key 后再比较。

红黑树的迭代器

普通迭代器

红黑树的迭代器无非也就是包含一个节点的指针，然后重载指针的各种操作即可。

一般迭代器的实现都是按照中序遍历，遍历完是有序的。所以红黑树迭代器的 begin()，应该是树最左侧的节点；对于迭代器的 end()，我们就按照 NULL 来处理。

那红黑树迭代器的++与--操作是如何实现的呢？

对于++操作：

对于--操作：为了方便_node == nullptr 时找树最右侧的节点，我们再给迭代器加一个指针 root 记录树的根。

template <class Value>
class RBTreeIterator {
    typedef TreeNode<Value> Node;
    typedef RBTreeIterator<Value> Self;
private:
    Node* _node;
    Node* _root;
public:
    RBTreeIterator(Node* data, Node* root) : _node(data), _root(root) {}
    Self& operator++() {
        // 右树存在，找右树的最左侧节点
        if (_node->_right) {
            Node* leftMost = _node->_right;
            while (leftMost && leftMost->_left) {
                leftMost = leftMost->_left;
            }
            _node = leftMost;
            // 直接跳转至
        } else
            // 右树不存在，继续向上
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && parent->_right == cur) {
                cur = parent;
                parent = cur->_parent;
            }
            
            _node = parent;
        }
         *;
    }
    Self& --() {
        
         (_node == ) {
            Node* rightMost = _root;
             (rightMost && rightMost->_right) {
                rightMost = rightMost->_right;
            }
            _node = rightMost;
        }
        
          (_node->_left) {
            Node* rightMost = _node->_left;
             (rightMost && rightMost->_right) {
                rightMost = rightMost->_right;
            }
            _node = rightMost;
        }  {
            
            Node* cur = _node;
            Node* parent = cur->_parent;
             (parent && parent->_left == cur) {
                cur = parent;
                parent = cur->_parent;
            }
            
            _node = parent;
        }
         *;
    }
    Value& *() {  _node->_data; }
    Value* ->() {  &_node->_data; }
     ==( Self& it) {  _node == it._node; }
     !=( Self& it) {  _node != it._node; }
};