使用红黑树封装map和set

[bosthhe1]

set.h

#define _CRT_SECURE_NO_WARNINGS 1
#include"11.h"
namespace hxh
{
    template<class K>
    class set
    {
    public:

        struct SetCmp
        {
            const K& operator()(const K& a)
            {
                return a;
            }
        };
        typedef typename RBTree<K, K, SetCmp>::iterator iterator;
        typedef RBTree<K, K, SetCmp> setNode;
        iterator begin()
        {
            return node.begin();
        }
        iterator end()
        {
            return node.end();
        }
        bool insert(const K& key)
        {
            return node.insert(key);
        }
    private:
        setNode node;
    };
}

[bosthhe1]

map.h

#define _CRT_SECURE_NO_WARNINGS 1
#include"11.h";
namespace hxh{
    template<class K,class V>
    class Map
    {
        struct MapRb
        {
            K& operator()(pair<K,V>& v)
            {
                return v.first;
            }
        };
    public:
        typedef typename RBTree<K, pair<K, V>, MapRb >::iterator Mapiterator;
        bool insert(const pair<K,V>& v)
        {
            return k.insert(v);
        }

    private:
        RBTree<K, pair<K,V>, MapRb> k;
    };
}

[bosthhe1]

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
using namespace std;
#include<time.h>
#include<assert.h>
namespace hxh
{
    enum color
    {
        RED,
        BLACK
    };

    template<class T>
    struct RBTreeNode
    {
        RBTreeNode<T>* left;
        RBTreeNode<T>* right;
        RBTreeNode<T>* parent;
        T _data;
        color col;
        RBTreeNode(const T& data)
            :left(nullptr)
            , right(nullptr)
            , parent(nullptr)
            , _data(data)
            , col(RED)
        {}
    }; 
    template<class T,class Ref,class Ptr>
    struct Bidrectionaliterator
    {
        typedef RBTreeNode<T> Node;
        typedef Bidrectionaliterator<T, Ref, Ptr> Self;
        Bidrectionaliterator(Node* _node)
            :node(_node)
        {}
        Node* node;
        Ref operator*()
        {
            return node->_data;
        }
        Ptr operator->()
        {
            return &operator*();
        }
        Self operator--()
        {
            Node* cur = node;
            if (cur->left)
            {
                cur = cur->left;
                while (cur->right)
                {
                    cur = cur->right;
                }
                node = cur;
                return Self(cur);
            }
            else
            {
                Node* parent = cur->parent;
                while (parent&&parent->left == cur)
                {
                    cur = parent;
                    parent = cur->parent;
                }
                node = parent;
                return Self(parent);
            }
        }
        Self operator++()
        {
            Node* cur = node;
            if (cur->right)
            {
                cur = cur->right;
                while (cur->left)
                {
                    cur = cur->left;
                }
                node = cur;
                return Self(cur);
            }
            else
            {
                Node* parent = cur->parent;
                while(parent&&parent->right == cur)
                {
                    cur = parent;
                    parent = cur->parent;
                }
                node = parent;
                return Self(parent);
            }
        }
        bool operator!=(const Self& b)
        {
            return node != b.node;
        }
        bool operator==(const Self& b)
        {
            return !this->operator!=(b);
        }
    };
    template<class K, class T, class KEeyOfVaule>
    class RBTree
    {
        typedef RBTreeNode<T> Node;
    public:
        RBTree()
            :_root(nullptr)
        {}
        ~RBTree()
        {
            Delete(_root);
        }
        RBTree(const RBTree& root)
        {
            _root = RBTree1(root._root);
        }
        RBTree& operator=(RBTree key)
        {
            swap(_root,key._root);
            return *this;
        }
        typedef Bidrectionaliterator<T, T&, T*> iterator;
        iterator& begin()
        {
            Node* cur = _root;
            while (cur&&cur->left)
            {
                cur = cur->left;
            }
            return iterator(cur);
        }
        iterator& end()
        {
            return iterator(nullptr);
        }
        pair<iterator,bool>& insert(const T& tmp)
        {
            Node * newNode = new Node(tmp);
            Node * newNodecopy = newNode;
            Node* cur = _root;
            Node* _parent = _root;
            KEeyOfVaule cmp;
            if (_root == nullptr)
            {
                _root = newNode;
                _root->col = BLACK;
                auto it = iterator(_root);
                return make_pair(it, true);
            }
            else
            {
                while (cur)
                {
                    _parent = cur;
                    if (cmp(cur->_data)> cmp(newNode->_data))
                        cur = cur->left;
                    else if (cmp(cur->_data)< cmp(newNode->_data))
                        cur = cur->right;
                    else
                    {
                        auto it = iterator(cur);
                        return make_pair(it, false);
                    }
                }
                if (cmp(_parent->_data)>cmp(newNode->_data))
                {
                    _parent->left = newNode;
                    newNode->parent = _parent;
                }
                else
                {
                    _parent->right = newNode;
                    newNode->parent = _parent;
                }
                while (_parent != nullptr&&_parent->col == RED)
                {
                    Node* GrandParent = _parent->parent;
                    if (_parent->left == newNode&&GrandParent->left == _parent)
                    {
                        Node* uncle = _parent->parent->right;
                        if (uncle == nullptr)
                        {
                            RRotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            RRotate(GrandParent);
                            _parent->col = BLACK;
                            GrandParent->col = RED;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->right == newNode&&GrandParent->right == _parent)
                    {
                        Node* uncle = _parent->parent->left;
                        if (uncle == nullptr)
                        {
                            LRotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            LRotate(GrandParent);
                            _parent->col = BLACK;
                            GrandParent->col = RED;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->left == newNode&&GrandParent->right == _parent)
                    {
                        Node* uncle = _parent->parent->left;
                        if (uncle == nullptr)
                        {
                            LRPotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            LRPotate(GrandParent);
                            _parent->col = RED;
                            GrandParent->col = RED;
                            newNode->col = BLACK;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                    else if (_parent->right == newNode&&GrandParent->left == _parent)
                    {
                        Node* uncle = _parent->parent->right;
                        if (uncle == nullptr)
                        {
                            RLPotate(GrandParent);
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            break;
                        }
                        else if (uncle->col == RED)
                        {
                            GrandParent->col = RED;
                            _parent->col = BLACK;
                            uncle->col = BLACK;
                            newNode = GrandParent;
                            _parent = newNode->parent;
                        }
                        else if (uncle->col == BLACK)
                        {
                            RLPotate(GrandParent);
                            _parent->col = RED;
                            GrandParent->col = RED;
                            newNode->col = BLACK;
                            break;
                        }
                        else
                        {
                            assert(false);
                        }
                    }
                }
            }
            _root->col = BLACK;
            auto it = iterator(newNodecopy);
            return make_pair(it, true);
        }
        void RRotate(Node* parent1)
        {
            Node* parent = parent1;
            Node* Grandparent = parent1->parent;
            Node* Sub = parent->left;
            Node* Subr = Sub->right;
            parent->left = Subr;
            if (Subr)
                Subr->parent = parent;
            Sub->right = parent;
            parent->parent = Sub;
            Sub->parent = Grandparent;
            if (Grandparent)
            {
                if (Grandparent->left == parent)
                    Grandparent->left = Sub;
                else
                    Grandparent->right = Sub;
            }
            else
            {
                Sub->parent = nullptr;
                _root = Sub;
            }
        }
        void LRotate(Node* parent1)
        {
            Node* parent = parent1;
            Node* Grandparent = parent1->parent;
            Node* Sub = parent->right;
            Node* Subl = Sub->left;
            parent->right = Subl;
            if (Subl)
                Subl->parent = parent;
            Sub->left = parent;
            parent->parent = Sub;
            Sub->parent = Grandparent;
            if (Grandparent)
            {
                if (Grandparent->left == parent)
                    Grandparent->left = Sub;
                else
                    Grandparent->right = Sub;
            }
            else
            {
                Sub->parent = nullptr;
                _root = Sub;
            }
        }
        void RLPotate(Node* cur)
        {
            RRotate(cur->right);
            LRotate(cur);
        }
        void LRPotate(Node* cur)
        {
            LRotate(cur->left);
            RRotate(cur);
        }
        bool testCorrect()
        {
            int k = 0;
            Node* cur = _root;
            while (cur)
            {
                if (cur->col == BLACK)
                    k++;
                cur = cur->left;
            }
            int t = 0;
            return _testCorrect(_root, k, t);
        }
        void Delete(Node* root)
        {
            if (root == nullptr)
                return;
            Delete(root->left);
            Delete(root->right);
            delete root;
        }
        Node* RBTree1(Node* root)
        {
            if (root == nullptr)
                return nullptr;
            Node* newroot = new Node(root->_data);
            newroot->col = root->col;
            newroot->left = RBTree1(root->left);
            newroot->right = RBTree1(root->right);
            if (newroot->left)
            newroot->left->parent = newroot;
            if (newroot->right)
            newroot->right->parent = newroot;
            return newroot;
        }
private:
        bool _testCorrect(Node* root, int k, int t)
        {
            if (root == nullptr)
            {
                if (k == t)
                    return true;
                return false;
            }
            if (root->col == BLACK)
                t++;
            return _testCorrect(root->left, k, t) &&
                _testCorrect(root->right, k, t);
        }
    private:
        Node* _root;
    };

}