STL 底层解析：map 与 set 基于红黑树的封装及迭代器实现

map的 []可以插入和修改和访问–string的 []不能用来插入

namespace mylib {
template <class K>
class set {
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
    typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

    const_iterator begin() const {
        return _t.begin();
    }
    const_iterator end() const {
        return _t.end();
    }

    pair<iterator, bool> insert(const K& key) {
        pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
        return pair<iterator, bool>(ret.first, ret.second);
    }

private:
    RBTree<K, K, SetKeyOfT> _t;
};
}

底层红黑树的模拟实现

enum Colour { RED, BLACK };

template <class T>
struct RBTreeNode {
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    T _data;
    Colour _col;

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

template <class K, class T, class KeyOfT>
struct RBTree {
    typedef RBTreeNode<T> Node;

public:
    typedef __TreeIterator<T, T*, T&> iterator;
    typedef __TreeIterator<T, const T*, const T&> const_iterator;

    iterator begin() {
        Node* leftMin = _root;
        while (leftMin && leftMin->_left) {
            leftMin = leftMin->_left;
        }
        return iterator(leftMin);
    }

    iterator end() {
        return iterator(nullptr);
    }

    const_iterator begin() const {
        Node* leftMin = _root;
        while (leftMin && leftMin->_left) {
            leftMin = leftMin->_left;
        }
        return const_iterator(leftMin);
    }

    const_iterator end() const {
        return const_iterator(nullptr);
    }

    Node* Find(const K& key) {
        Node* cur = _root;
        KeyOfT kot;
        while (cur) {
            if (kot(cur->_data) < key) {
                cur = cur->_right;
            } else if (kot(cur->_data) > key) {
                cur = cur->_left;
            } else {
                return cur;
            }
        }
        return nullptr;
    }

    pair<iterator, bool> Insert(const T& data) {
        if (_root == nullptr) {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), true);
        }

        Node* parent = nullptr;
        Node* cur = _root;
        KeyOfT kot;
        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);
        cur->_col = RED;
        if (kot(parent->_data) < kot(data)) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        cur->_parent = parent;

        while (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left) {
                Node* uncle = grandfather->_right;
                // u 存在且为红
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (cur == parent->_left) {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        RotateL(parent);
                        RotateR(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            } else {
                Node* uncle = grandfather->_left;
                // u 存在且为红
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    cur = grandfather;
                    parent = cur->_parent;
                } else {
                    if (cur == parent->_right) {
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    } else {
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return make_pair(iterator(cur), true);
    }

private:
    Node* _root = nullptr;
};

库里面的红黑树和这里的模拟实现的区别:

库里面其实还有个头节点，头节点的父亲是红黑树的根节点，头节点的 left 是红黑树里面最小的数，头节点的 right 是红黑树里面最大的数，然后根节点的父亲也是头节点

注意：区分头节点和根节点!

迭代器的模拟实现

这里的迭代器的 begin和 end的位置要注意:

begin是最左边的那个节点

end是根节点的父亲–nullptr–这个 begin和 end是在底层红黑树那里定义的

这里的迭代器的 ++:

1.当前节点的右子树不为空，则访问右树的最左节点

2.当前节点的右子树为空，如果当前节点的父亲是其父亲的左孩子，就访问当前节点的父亲，不然就把当前节点的父亲变成当前节点，直到遇到那种情况或者当前节点成根节点的父亲了

这里迭代器的 --:

1.当前节点的左子树不为空，则访问左树的最右节点

2.当前节点的右子树为空，如果当前节点的父亲是其父亲的右孩子，就访问当前节点的父亲，不然就把当前节点的父亲变成当前节点，直到遇到那种情况或者当前节点变成根节点的父亲了

引申：普通迭代器可以隐式转换为 const 迭代器

template <class T, class Ptr, class Ref>
struct __TreeIterator {
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator<T, Ptr, Ref> Self;
    typedef __TreeIterator<T, T*, T&> Iterator;

    __TreeIterator(const Iterator& it) : _node(it._node) {}
    Node* _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->_left) {
            Node* subNode = _node->_left;
            while (subNode->_right) {
                subNode = subNode->_right;
            }
            _node = subNode;
        } else {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left) {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self& operator++() {
        if (_node->_right) {
            Node* subNode = _node->_right;
            while (subNode->_left) {
                subNode = subNode->_left;
            }
            _node = subNode;
        } else {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right) {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
};