学过的模拟实现(不定期更新)

发布于:2024-06-09 ⋅ 阅读:(151) ⋅ 点赞:(0)

string模拟

list模拟

#pragma once

#include<assert.h>
namespace bear
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        //构造函数1
        vector()
            :_start(nullptr)
            ,_finish(nullptr)
            ,_end_of_storage(nullptr)
        {}

        vector(size_t n, const T& val = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
            {
                reserve(n);
                for (size_t i = 0; i < n; ++i)
                {
                    push_back(val);
                }
        }

        vector(int n, const T& val = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
      
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造传统写法
        vector(const vector<T>& v)
        {
            _start = new T[v.capacity()];
            for(size_t i = 0; i < v.size(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
        }

        //拷贝构造现代写法
        vector(const vector<T>& v)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        //析构函数
        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }

        //迭代器
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }

        //扩容函数
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start)
                {
                    for (size_t i = 0; i < sz; i++) 
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = tmp + sz;
                _end_of_storage = tmp + n;
            }
        }
        

        //尾插
        void push_back(const T& x)      
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        //检查容量
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }

        //检查有效大小
        size_t size() const
        {
            return _finish - _start;
        }

        //重构造[]
        T& operator[](size_t pos)
        {
            return _start[pos];
        }

        
        const T& operator[](size_t pos) const
        {
            return _start[pos];
        }

        //删除一个元素
        void pop_back()
        {
            assert(!empty());
            --_finish;
        }


        // v1 = v2
        vector<T>& operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

        void swap(vector<T>& v)
        {
            //交换容器当中的各个成员变量
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }
        //判空
        bool empty()
        {
            return _start == _finish;
        }

        //开空间+初始化
        void resize(size_t n,T val = T())
        {
            if (n < size())
            {
                _finish = _start+n;
            }
            else 
            {
                if (n > capacity())
                {
                    reserve(n);
                }
                while (_finish != _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

        
        void insert(iterator pos, const T& val)
        {
            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start;

                reserve(capacity() == 0 ? 4 : capacity() * 2);

                pos = _start + len;
            }
            iterator end = _finish -1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = val;
            ++_finish;
        }

        void erase(iterator pos)
        {
            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

}

vector模拟 

#pragma once

#include<assert.h>
namespace bear
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        //构造函数1
        vector()
            :_start(nullptr)
            ,_finish(nullptr)
            ,_end_of_storage(nullptr)
        {}

        //拷贝构造1
        vector(size_t n, const T& val = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
            {
                reserve(n);
                for (size_t i = 0; i < n; ++i)
                {
                    push_back(val);
                }
        }

        //拷贝构造2
        vector(int n, const T& val = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _end_of_storage(nullptr)
        {
            reserve(n);
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }
        }
      
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造传统写法
        vector(const vector<T>& v)
        {
            _start = new T[v.capacity()];
            for(size_t i = 0; i < v.size(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _end_of_storage = _start + v.capacity();
        }

        //拷贝构造现代写法
        vector(const vector<T>& v)
        {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        //析构函数
        ~vector()
        {
            delete[] _start;
            _start = _finish = _end_of_storage = nullptr;
        }

        //迭代器
        iterator begin()
        {
            return _start;
        }
        iterator end()
        {
            return _finish;
        }

        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }

        //扩容函数
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start)
                {
                    for (size_t i = 0; i < sz; i++) 
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = tmp + sz;
                _end_of_storage = tmp + n;
            }
        }
        

        //尾插
        void push_back(const T& x)      
        {
            if (_finish == _end_of_storage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        //检查容量
        size_t capacity() const
        {
            return _end_of_storage - _start;
        }

        //检查有效大小
        size_t size() const
        {
            return _finish - _start;
        }

        //重构造[]
        T& operator[](size_t pos)
        {
            return _start[pos];
        }

        
        const T& operator[](size_t pos) const
        {
            return _start[pos];
        }

        //删除一个元素
        void pop_back()
        {
            assert(!empty());
            --_finish;
        }


        // v1 = v2
        vector<T>& operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

        void swap(vector<T>& v)
        {
            //交换容器当中的各个成员变量
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }
        //判空
        bool empty()
        {
            return _start == _finish;
        }

        //开空间+初始化
        void resize(size_t n,T val = T())
        {
            if (n < size())
            {
                _finish = _start+n;
            }
            else 
            {
                if (n > capacity())
                {
                    reserve(n);
                }
                while (_finish != _start + n)
                {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

        
        void insert(iterator pos, const T& val)
        {
            if (_finish == _end_of_storage)
            {
                size_t len = pos - _start;

                reserve(capacity() == 0 ? 4 : capacity() * 2);

                pos = _start + len;
            }
            iterator end = _finish -1;
            while (end >= pos)
            {
                *(end + 1) = *end;
                --end;
            }
            *pos = val;
            ++_finish;
        }

        void erase(iterator pos)
        {
            iterator start = pos + 1;
            while (start != _finish)
            {
                *(start - 1) = *start;
                ++start;
            }
            --_finish;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}



AVLTree平衡二叉树

#pragma once
#include<assert.h>
template<class K,class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V>* _left; //左子树指针
    AVLTreeNode<K, V>* _right;//右子树指针
    AVLTreeNode<K, V>* _parent;//每个结点都包含了一个父结点地址
    pair<K, V> _kv;//键值对
    int _bf;//平衡因子

    AVLTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _bf(0)
    {}
};

template<class K,class T>
class AVLTree
{
    typedef AVLTreeNode<K, T> Node;
public:
    //中序遍历副函数
    void Inorder()
    {
        _Inorder(_root);
    }
    //中序遍历主函数
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << " ";
        _Inorder(root->_right);
    }

    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        
        parent->_right = subRL;
        subR->_left = parent;

        Node* pp = parent->_parent;
        
        parent->_parent = subR;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        if (_root = parent)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (pp->_left = parent)
            {
                pp->_left = subR;
            }
            else
            {
                pp->_right = subR;
            }
            subR->_parent = pp;
        }
        parent->_bf = subR->_bf = 0;
    }

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;

        parent->_left = subRR;
        subL->_right = parent;

        Node* pp = parent->_parent;
        parent->_parent = subL;

        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }

        if (_root == parent)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        subL->_bf = parent->_bf = 0;
    }

    void RotateRL(Node* parent)//右左双旋
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent->_left);

        if (bf == 0)
        {
            //subRL自己就是新增
            parent->_bf = subR->_bf = subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            //subRL的左子树新增
            parent->_bf = 0;
            subRL->_bf = 0;
            subR->_bf = 1;
        }
        else if (bf == 1)
        {
            //subRL的右子树新增
            parent->_bf = -1;
            subRL->_bf = 0;
            subR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void RotateLR(Node* parent)//左右双旋
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent->_right);

        if (bf == 0)
        {
            //subLR自己就是新增
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == -1)
        {
            //subLR的左子树新增
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if(bf == 1)
        {
            //subLR的右子树新增
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    //插入函数
    bool insert(const pair<K,T>& kv)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(kv);
            return true;
        }
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
        while (cur)//当不为空,说明存在值,那么继续搜索可插入的地方
        {
            if (cur->_kv.first < kv.first)//key大于结点值,往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)//key小于结点值,往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等,那么不插入,插入失败
            {
                return false;
            }
        }
            //找到地方插入,new一个新结点
            cur = new Node(kv);
            if (parent->_kv.first < kv.first)//key大于父结点值,插右边
            {
                parent->_right = cur;
                cur->_parent = parent;
            }
            else//小于那么插左边
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
            return true;//插入成功

        //平衡因子
        while (cur != _root)
        {
            //处理因子
            if (cur == parent->_left)//如果插入的结点在父节点的左边
            {
                parent->_bf--;//因子-1
            }
            else//如果插入的结点在父节点的右边
            {
                parent->_bf++;//因子+1
            }
            //处理完成,开始检查因子
            if (parent->_bf == 0)//等于0,说明平衡,不需要处理
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)//等于1或-1,说明高度变化了,那么要处理祖先结点因子
            {
                cur = parent;
                parent = parent->_parent;
            }

            else if (parent->_bf == 2 || parent->_bf == -2)// 如果等于2或-2,需要旋转解决
            {
                if (parent->_bf == 2 && cur->_bf == 1)//说明右边高,需左旋
                {
                    RotateL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)//说明左边高,需右旋
                {
                    RotateR(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)//左子树的右子树高
                {
                    RotateRL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)//右子树的左子树高
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                assert(false);
            }
           
        }
    }

    //判断是否为AVL树
    bool IsAVLTree()
    {
        int hight = 0; //输出型参数
        return _IsBalanced(_root, hight);
    }
    //检测二叉树是否平衡
    bool _IsBalanced(Node* root, int& hight)
    {
        if (root == nullptr) //空树是平衡二叉树
        {
            hight = 0; //空树的高度为0
            return true;
        }
        //先判断左子树
        int leftHight = 0;
        if (_IsBalanced(root->_left, leftHight) == false)
            return false;
        //再判断右子树
        int rightHight = 0;
        if (_IsBalanced(root->_right, rightHight) == false)
            return false;
        //检查该结点的平衡因子
        if (rightHight - leftHight != root->_bf)
        {
            cout << "平衡因子设置异常:" << root->_kv.first << endl;
        }
        //把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
        hight = max(leftHight, rightHight) + 1;
        return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
    }

private:
    Node* _root = nullptr;
};

 红黑树RBTree

#pragma once
#include<iostream>
using namespace std;
//枚举类型的颜色分类
enum Colour
{
    RED,
    BLACK
};

//定义一个结构体结点
template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
        :_left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};

//红黑树类
template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    //中序遍历副函数
    void Inorder()
    {
        _Inorder(_root);
    }
    //中序遍历主函数
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << " ";
        _Inorder(root->_right);
    }


    //插入函数
    bool insert(const pair<K, V>& kv)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(kv);
            _root->_col = BLACK;//根结点一定为黑
            return true;
        }
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
        while (cur)//当不为空,说明存在值,那么继续搜索可插入的地方
        {
            if (cur->_kv.first < kv.first)//key大于结点值,往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)//key小于结点值,往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等,那么不插入,插入失败
            {
                return false;
            }
        }
        cur = new Node(kv);//新增结点
        cur->_col = RED;//默认红色
        //插入
        if (parent->_kv.first > kv.first)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //开始判断颜色
        while (parent != nullptr && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            //如果父亲为红,那么违反红红规则,开始判断情况
            if (parent != nullptr && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    //变色
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //将cur和parent往上移继续判断
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//叔叔不存在或者存在且为黑色,情况二和情况三结合
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateLR(grandfather); //左右双旋
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;//根结点为黑,不需要往上了
                }
            }
            else//parent在grandfather的右边
            {
                Node* uncle = grandfather->_left;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //向上调整
                    cur = grandfather;
                    parent = grandfather->_parent;
                }
                else//叔叔不存在或者存在且为黑色,情况二和情况三结合
                {
                    if (cur == parent->_left)//如果插入在parent的左边
                    {
                        RotateRL(grandfather);//右左双旋
                        cur->_col = BLACK;
                        grandfather->_col = RED;

                    }
                    else//如果插入在parent的右边
                    {
                        RotateL(grandfather);//左旋
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    break;//根结点为黑,不需要往上了
                }
            }
        }
        _root->_col = BLACK;//往上移动后无论cur是否为根结点,统一为改黑

        return true;//插入成功

    }

    //左单旋
    void RotateL(Node* parent)
    {
        //定义新指针,方便操作
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* pp = parent->_parent;//方便更改_root的操作

        parent->_right = subRL;//让parent结点链接subRL
        subR->_left = parent;//让subR的左子树链接parent
        parent->_parent = subR;//由于parent的_parent由nullptr变成了subR,所以也需要重新链接
        if (subRL)
            //判断subRL是否为空,如果为空的话就不需要对subRL进行操作了,不然会出现对空指针进行解引用的问题
        {
            subRL->_parent = parent;//不为空,那么让subRL链接parent
        }
        if (pp == nullptr)//如果parent是整棵树的根结点
        {
            _root = subR;//subR变为根结点
            subR->_parent = nullptr;//subR的_parent为空
        }
        else//如果parent不是整棵树的根结点,那么将新的parent重新链接上一个结点
        {
            if (pp->_left = parent)//如果parent是上一个结点的左子树,那么新的parent也是
            {
                pp->_left = subR;
            }
            else//如果parent是上一个结点的右子树,那么新的parent也是
            {
                pp->_right = subR;
            }
            subR->_parent = pp;//更新subR的父结点
        }
        //parent->_bf = subR->_bf = 0;//由于旋转后,整棵树的高度变回插入前的,那么此时parent和subR(cur)的因子都变回0
    }

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;
        Node* pp = parent->_parent;

        //建立subL和parent之间的关系
        parent->_left = subRR;
        subL->_right = parent;

        //建立parent和subRR之间的关系
        parent->_parent = subL;
        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }

        //建立PP和subL之间的关系
        if (pp == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        //更新平衡因子
        //subL->_bf = parent->_bf = 0;
    }

    //左右双旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        //int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        //if (bf == 0)
        //{
        //    //subLR自己就是新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subLR的左子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subLR的右子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = -1;
        //    parent->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    //右左双旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        //int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        //if (bf == 0)
        //{
        //    //subRL自己就是新增
        //    parent->_bf = subR->_bf = subRL->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subRL的左子树新增
        //    parent->_bf = 0;
        //    subRL->_bf = 0;
        //    subR->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subRL的右子树新增
        //    parent->_bf = -1;
        //    subRL->_bf = 0;
        //    subR->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    // blacknum是根结点到当前结点的黑色结点数量
    bool check(Node* root,int blacknum,int count)
    {
        if (root == nullptr)
        {
            if(count != blacknum)
            {
                cout << "黑色结点数量不等" << endl;
                return false;
            }
            
            return true;
        }

        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "有连续的红色结点" << endl;
            return false;
        }


        if (root->_col == BLACK)
        {
            ++blacknum;
        }

        return check(root->_left,blacknum,count) && check(root->_right,blacknum,count);
    }

    bool isbalance()
    {
        if (_root == nullptr)
        {
            return true;
        }
        if (_root->_col == RED)
        {
            return false;
        }
        //找最左路径作为黑色结点数目的参考值
        Node* cur = _root;
        int count = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++count;
            cur = cur->_left;
        }

        int blacknum = 0;
        return check(_root,blacknum,count); 
    }
private:
    Node* _root = nullptr;
};

红黑树封装map、set

红黑树代码

#pragma once
#include<iostream>
using namespace std;
//枚举类型的颜色分类
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 T, class Ref,class Ptr>
struct _TreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef _TreeIterator<T, Ref, Ptr> Self;
    Node* _node;

    _TreeIterator(Node* node)
        :_node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &_node->_data;
    }

    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 = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

    Self operator--()
    {
        if (_node->_left) //结点的左子树不为空
        {
            //寻找该结点左子树当中的最右结点
            Node* right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }
            _node = right; //--后变为该结点
        }
        else //结点的左子树为空
        {
            //寻找孩子不在父亲左的祖先
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent; //--后变为该结点
        }
        return *this;
    }

    bool operator!=(const Self& s) const
    {
        return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个
    }
};


//红黑树类
template<class K, class T, class KeyofT>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    //中序遍历副函数
    void Inorder()
    {
        _Inorder(_root);
    }
    //中序遍历主函数
    void _Inorder(Node* root)
    {
        if (root == nullptr)
            return;
        _Inorder(root->_left);
        cout << root->_kv.first << " ";
        _Inorder(root->_right);
    }

    //迭代器函数
    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 iterator(cur);
    }
    const_iterator end() const
    {
        return iterator(nullptr);
    }


    //插入函数
    pair<iterator,bool> insert(const T& data)
    {
        //按照二叉树搜索树插入
        if (_root == nullptr)//根结点为空时new一个最初的根结点
        {
            _root = new Node(data);
            _root->_col = BLACK;//根结点一定为黑
            return make_pair(iterator(_root),true);
        }
        Node* parent = nullptr;//这个为当前指针cur的父结点指针
        Node* cur = _root;//当前指针指向根
        KeyofT kot;

        while (cur)//当不为空,说明存在值,那么继续搜索可插入的地方
        {
            if (kot(cur->_data) < kot(data))//key大于结点值,往右走
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kot(cur->_data) > kot(data))//key小于结点值,往左走
            {
                parent = cur;
                cur = cur->_left;
            }
            else//相等,那么不插入,插入失败
            {
                return make_pair(iterator(cur), false);
            }
         }
        cur = new Node(data);//新增结点
        Node* newnode = cur;
        cur->_col = RED;//默认红色
        //插入
        if (kot(parent->_data) > kot(data))
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //开始判断颜色
        while (parent != nullptr && parent->_col == RED)
        {
            Node* grandfather = parent->_parent;
            //如果父亲为红,那么违反红红规则,开始判断情况
            if (parent != nullptr && parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    //变色
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //将cur和parent往上移继续判断
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//叔叔不存在或者存在且为黑色,情况二和情况三结合
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);//右旋
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateLR(grandfather); //左右双旋
                        grandfather->_col = RED;
                        cur->_col = BLACK;
                    }
                    break;//根结点为黑,不需要往上了
                }
            }
            else//parent在grandfather的右边
            {
                Node* uncle = grandfather->_left;//记录叔叔结点
                if (uncle != nullptr && uncle->_col == RED)//如果叔叔存在或者为红色,情况一
                {
                    parent->_col = uncle->_col = BLACK;//父亲和叔叔都变黑
                    grandfather->_col = RED;//爷爷变红

                    //向上调整
                    cur = grandfather;
                    parent = grandfather->_parent;
                }
                else//叔叔不存在或者存在且为黑色,情况二和情况三结合
                {
                    if (cur == parent->_left)//如果插入在parent的左边
                    {
                        RotateRL(grandfather);//右左双旋
                        cur->_col = BLACK;
                        grandfather->_col = RED;

                    }
                    else//如果插入在parent的右边
                    {
                        RotateL(grandfather);//左旋
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }
                    break;//根结点为黑,不需要往上了
                }
            }
        }
        _root->_col = BLACK;//往上移动后无论cur是否为根结点,统一为改黑

        return make_pair(iterator(newnode), true);//插入成功

    }

    //左单旋
    void RotateL(Node* parent)
    {
        //定义新指针,方便操作
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        Node* pp = parent->_parent;//方便更改_root的操作

        parent->_right = subRL;//让parent结点链接subRL
        subR->_left = parent;//让subR的左子树链接parent
        parent->_parent = subR;//由于parent的_parent由nullptr变成了subR,所以也需要重新链接
        if (subRL)
            //判断subRL是否为空,如果为空的话就不需要对subRL进行操作了,不然会出现对空指针进行解引用的问题
        {
            subRL->_parent = parent;//不为空,那么让subRL链接parent
        }
        if (pp == nullptr)//如果parent是整棵树的根结点
        {
            _root = subR;//subR变为根结点
            subR->_parent = nullptr;//subR的_parent为空
        }
        else//如果parent不是整棵树的根结点,那么将新的parent重新链接上一个结点
        {
            if (pp->_left = parent)//如果parent是上一个结点的左子树,那么新的parent也是
            {
                pp->_left = subR;
            }
            else//如果parent是上一个结点的右子树,那么新的parent也是
            {
                pp->_right = subR;
            }
            subR->_parent = pp;//更新subR的父结点
        }
        //parent->_bf = subR->_bf = 0;//由于旋转后,整棵树的高度变回插入前的,那么此时parent和subR(cur)的因子都变回0
    }




    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subRR = subL->_right;
        Node* pp = parent->_parent;

        //建立subL和parent之间的关系
        parent->_left = subRR;
        subL->_right = parent;

        //建立parent和subRR之间的关系
        parent->_parent = subL;
        if (subRR != nullptr)
        {
            subRR->_parent = parent;
        }

        //建立PP和subL之间的关系
        if (pp == nullptr)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (pp->_left == parent)
            {
                pp->_left = subL;
            }
            else
            {
                pp->_right = parent;
            }
            subL->_parent = pp;
        }
        //更新平衡因子
        //subL->_bf = parent->_bf = 0;
    }



    //左右双旋
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        //int bf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        //if (bf == 0)
        //{
        //    //subLR自己就是新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subLR的左子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = 0;
        //    parent->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subLR的右子树新增
        //    subLR->_bf = 0;
        //    subL->_bf = -1;
        //    parent->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    //右左双旋
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        //int bf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        //if (bf == 0)
        //{
        //    //subRL自己就是新增
        //    parent->_bf = subR->_bf = subRL->_bf = 0;
        //}
        //else if (bf == -1)
        //{
        //    //subRL的左子树新增
        //    parent->_bf = 0;
        //    subRL->_bf = 0;
        //    subR->_bf = 1;
        //}
        //else if (bf == 1)
        //{
        //    //subRL的右子树新增
        //    parent->_bf = -1;
        //    subRL->_bf = 0;
        //    subR->_bf = 0;
        //}
        //else
        //{
        //    assert(false);
        //}
    }

    // blacknum是根结点到当前结点的黑色结点数量
    bool check(Node* root, int blacknum, int count)
    {
        if (root == nullptr)
        {
            if (count != blacknum)
            {
                cout << "黑色结点数量不等" << endl;
                return false;
            }

            return true;
        }

        if (root->_col == RED && root->_parent->_col == RED)
        {
            cout << "有连续的红色结点" << endl;
            return false;
        }


        if (root->_col == BLACK)
        {
            ++blacknum;
        }

        return check(root->_left, blacknum, count) && check(root->_right, blacknum, count);
    }

    bool isbalance()
    {
        if (_root == nullptr)
        {
            return true;
        }
        if (_root->_col == RED)
        {
            return false;
        }
        //找最左路径作为黑色结点数目的参考值
        Node* cur = _root;
        int count = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                ++count;
            cur = cur->_left;
        }

        int blacknum = 0;
        return check(_root, blacknum, count);
    }
private:
    Node* _root = nullptr;
};

map代码

#pragma once
#include"RBTree.h"

namespace bear
{
    template<class K,class V>
    class map
    {
    public:
        struct MapKeyofT
        {
            const K& operator()(const pair<K,V>& kv)
            {
                return kv.first;
            }
        };

        typedef typename RBTree<K, pair<K, V>, MapKeyofT>::iterator iterator;

        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }

        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            return ret.first->second;
        }

        pair<iterator, bool> Insert(const pair<K, V>& kv)
        {
            return _t.insert(kv);
        }
    private:
        RBTree<K, pair<K, V>, MapKeyofT> _t;
    };
}

set代码

#pragma once
#include"RBTree.h"

namespace bear
{
    template<class K>
    class set
    {
    public:
        struct SetKeyofT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        typedef typename RBTree<K, K, SetKeyofT>::const_iterator iterator;
        typedef typename RBTree<K, K, SetKeyofT>::const_iterator const_iterator;

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

        pair<iterator, bool> Insert(const K& key)
        {
            return _t.insert(key);
        }

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

哈希

哈希表

//哈希表
namespace hashtable
{
    //状态
    enum Status
    {
        EMPTY,//空
        EXIST,//存在
        DELETE//删除
    };

    template<class K,class V>
    struct HashData
    {
        pair<K, V> _kv;//键值对
        Status _s = EMPTY;//状态
    };


    template<class K, class V>
    class HashTable
    {
    public:
        //构造函数
        HashTable()
        {
            _tables.resize(10);
        }

        //插入函数
        bool Insert(const pair<K, V>& kv)
        {
            //用find判断是否已经有了
            if (Find(kv.first))
            {
                return false;
            }
            //负载因子
            if (_n * 10 / _tables.size() >= 7)//如果负载因子>0.7,那么需要扩容
            {
                //开新表
                size_t newsize = _tables.size() * 2;
                HashTable<K, V> newht;
                newht._tables.resize(newsize);

                //遍历旧表
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    if (_tables[i]._s == EXIST)
                    {
                        newht.Insert(_tables[i]._kv);
                    }
                }
                //交换新旧表
                _tables.swap(newht._tables);
            }

            size_t hash = kv.first % _tables.size();//计算哈希值
            //开始寻找可插入位置
            while (_tables[hash]._s == EXIST)//如果该位置已经有值,那么线性向前探测
            {
                hash++;//线性探测,每次往前一位探测
                hash %= _tables.size();//防止探测越界
            }
            //开始插入
            _tables[hash]._kv = kv;
            _tables[hash]._s = EXIST;
            ++_n;
            return true;
        }

        //查找函数
        HashData<K, V>* Find(const K& key)
        {
            size_t hash = key % _tables.size();//计算哈希值
            while (_tables[hash]._s != EMPTY)//找到位置为空的就停止寻找
            {
                if (_tables[hash]._kv.first == key && _tables[hash]._s == EMPTY)//找到了
                {
                    return &_tables[hash];//返回地址
                }
                //如果没找到,线性往前探测
                hash++;
                hash %= _tables.size();//防止探测越界
            }
            //出了循环
            return NULL;//返回空
        }

        //删除函数
        bool Erase(const K& key)
        {
            HashData<K, V>* ret = Find(key);//先获取key的地址
            if (ret != NULL)//如果地址不为空,说明存在
            {
                ret->_s = DELETE;//状态改为删除
                --_n;//空间-1
                return true;
            }
            else//如果地址为空
            {
                return false;//删除失败
            }
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;//存储关键字的格个数
    };
}

哈希桶

//哈希桶
namespace hashbucket
{
    template<class K,class V>
    struct HashNode
    {
        HashNode* _next;
        pair<K, V> _kv;

        HashNode(const pair<K, V>& kv)

            :_kv(kv)
            ,_next(nullptr)
            {}
    };


    template<class K,class V>
    class HashTables
    {
        typedef HashNode<K, V> Node;
    public:

        //构造函数
        HashTables()
        {
            _tables.resize(10);
        }

        //析构函数
        ~HashTables()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }

        //插入函数
        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))
            {
                return false;
            }

            //负载因子
            if (_n == _tables.size())//因子到1开始扩容
            {
                //开新表
                vector<Node*> newtables;
                newtables.resize(_tables.size() * 2, nullptr);
                //遍历旧表
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;//记录下一个的地址
                        size_t hash = cur->_kv.first % newtables.size();//计算哈希值
                        //头插
                        cur->_next = newtables[i];
                        newtables[i] = cur;
                        //更新下一个位置
                        cur = next;
                    }
                    //将表置空
                    _tables[i] = nullptr;
                }
                //交换新旧表
                _tables.swap(newtables);
            }
            size_t hash = kv.first % _tables.size();//计算哈希值
            Node* newnode = new Node(kv);//创建结点
            //头插
            newnode->_next = _tables[hash];
            _tables[hash] = newnode;
            ++_n;
            return true;
        }

        //查找函数
        Node* Find(const K& key)
        {
            size_t hash = key % _tables.size();//计算哈希值
            Node* cur = _tables[hash];//寻找位置

            while (cur)//cur不为空则继续寻找
            {
                if (cur->_kv.first == key)//相同则找到
                {
                    return cur;//返回找到的地址
                }
                //不相同则判断下一个
                cur = cur->_next;
            }
            //出循环还没找到则返回空
            return NULL;
        }

        //删除函数
        bool Erase(const K& key)
        {
            size_t hash = key % _tables.size();//计算哈希值
            Node* prev = nullptr;//记录前地址
            Node* cur = _tables[hash];//记录当前地址
            while (cur)//不为空则继续寻找
            {
                if (cur->_kv.first == key)//相同则找到
                {
                    if (prev == nullptr)//如果为头删
                    {
                        _tables[hash] = cur->_next;//将下一个结点地址放到指针数组上
                    }
                    else
                    {
                        prev->_next = cur->_next;//将前一个结点连接后一个地址
                    }
                    delete cur;//删除找到的结点
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            //出循环还没找到则删除失败
            return false;
        }

    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };
}

哈希桶封装unordered_map、unordered_set

哈希桶代码

//哈希桶
namespace hashbucket
{
    //结点
    template<class T>
    struct HashNode
    {
        HashNode* _next;
        T _data;

        HashNode(const T& data)

            :_data(data)
            , _next(nullptr)
        {}
    };

    //解决冲突的前置声明
    template<class K, class T, class KeyofT>
    class HashTables;

    //迭代器
    template<class K,class T,class Ref, class Ptr, class KeyofT>
    struct HTiterator
    {
        typedef HashNode<T> Node;
        typedef HTiterator<K, T, Ref, Ptr, KeyofT> Self;
        Node* _node;

        const HashTables<K, T, KeyofT>* _pht;//迭代器要哈希表,哈希表要迭代器,冲突
        //vector<Node*>* _ptb;//直接使用私有类,就不会冲突了

        size_t _hash;

        HTiterator(Node* node,HashTables<K,T,KeyofT>* pht,size_t hash)
            :_node(node)
            ,_pht(pht)
            ,_hash(hash)
        {}

        HTiterator(Node* node, const HashTables<K, T, KeyofT>* pht, size_t hash)
            :_node(node)
            , _pht(pht)
            , _hash(hash)
        {}

        Self& operator++()
        {
            if (_node->_next)
            {
                _node = _node->_next;
            }
            else
            {
                ++_hash;
                while (_hash < _pht->_tables.size())
                {
                    if (_pht->_tables[_hash])
                    {
                        _node = _pht->_tables[_hash];
                        break;
                    }
                    ++_hash;
                }
                if (_hash == _pht->_tables.size())
                {
                    _node = nullptr;
                }
            }
            return *this;
        }

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }
    };


    //哈希表
    template<class K, class T,class KeyofT>
    class HashTables
    {
        typedef HashNode<T> Node;

        //友元函数,让外部类能访问私有成员
        template<class K, class T, class Ref, class Ptr, class KeyofT>
        friend struct HTiterator;

    public:
        
        typedef HTiterator<K, T, T&, T*, KeyofT> iterator;
        typedef HTiterator<K, T, const T&, const T*, KeyofT> const_iterator;

        iterator begin()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    return iterator(_tables[i], this, i);
                }
            }
            return end();
        }

        iterator end()
        {
            return iterator(nullptr, this, -1);
        }

        const_iterator begin() const
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    return const_iterator(_tables[i], this, i);
                }
            }
            return end();
        }

        const_iterator end() const
        {
            return const_iterator(nullptr, this, -1);
        }

        //构造函数
        HashTables()
        {
            _tables.resize(10);
        }

        //析构函数
        ~HashTables()
        {
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }

        //插入函数
        pair<iterator,bool> Insert(const T& data)
        {
            KeyofT kot;
            iterator it = Find(kot(data));

            if (it != end())
            {
                return make_pair(it,false);
            }

            //负载因子
            if (_n == _tables.size())//因子到1开始扩容
            {
                //开新表
                vector<Node*> newtables;
                newtables.resize(_tables.size() * 2, nullptr);
                //遍历旧表
                for (size_t i = 0; i < _tables.size(); ++i)
                {
                    Node* cur = _tables[i];
                    while (cur)
                    {
                        Node* next = cur->_next;//记录下一个的地址
                        size_t hash = kot(cur->_data) % newtables.size();//计算哈希值
                        //头插
                        cur->_next = newtables[i];
                        newtables[i] = cur;
                        //更新下一个位置
                        cur = next;
                    }
                    //将表置空
                    _tables[i] = nullptr;
                }
                //交换新旧表
                _tables.swap(newtables);
            }
            size_t hash = kot(data) % _tables.size();//计算哈希值
            Node* newnode = new Node(data);//创建结点
            //头插
            newnode->_next = _tables[hash];
            _tables[hash] = newnode;
            ++_n;
            return make_pair(iterator(newnode,this,hash), true);
        }

        //查找函数
        iterator Find(const K& key)
        {
            KeyofT kot;
            size_t hash = key % _tables.size();//计算哈希值
            Node* cur = _tables[hash];//寻找位置

            while (cur)//cur不为空则继续寻找
            {
                if (kot(cur->_data) == key)//相同则找到
                {
                    return iterator(cur,this,hash);//返回找到的地址
                }
                //不相同则判断下一个
                cur = cur->_next;
            }
            //出循环还没找到则返回空
            return end();
        }

        //删除函数
        bool Erase(const K& key)
        {
            KeyofT kot;
            size_t hash = key % _tables.size();//计算哈希值
            Node* prev = nullptr;//记录前地址
            Node* cur = _tables[hash];//记录当前地址
            while (cur)//不为空则继续寻找
            {
                if (kot(cur->_data) == key)//相同则找到
                {
                    if (prev == nullptr)//如果为头删
                    {
                        _tables[hash] = cur->_next;//将下一个结点地址放到指针数组上
                    }
                    else
                    {
                        prev->_next = cur->_next;//将前一个结点连接后一个地址
                    }
                    delete cur;//删除找到的结点
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            //出循环还没找到则删除失败
            return false;
        }

    private:
        vector<Node*> _tables;
        size_t _n = 0;
    };

}

unordered_set

#pragma once
#include"hashtable.h"

namespace bear
{
    template<class K>
    class unordered_set
    {
        struct SetKeyofT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    public:
        typedef typename hashbucket::HashTables<K, K, SetKeyofT>::const_iterator iterator;
        typedef typename hashbucket::HashTables<K, K, SetKeyofT>::const_iterator const_iterator;

        //iterator begin()
        //{
        //    return _ht.begin();
        //}

        //iterator end()
        //{
        //    return _ht.end();
        //}

        const_iterator begin() const
        {
            return _ht.begin();
        }

        const_iterator end() const
        {
            return _ht.end();
        }

        pair<const_iterator,bool> Insert(const K& key)
        {
            auto ret = _ht.Insert(key);
            return pair<const_iterator, bool>(const_iterator(ret.first._node,ret.first._pht,ret.first._hash),ret.second);
        }

        iterator Find(const K& key)
        {
            return _ht.Find(key);
        }
        bool Erase(const K& key)
        {
            return _ht.Erase(key);
        }

    private:
        hashbucket::HashTables<K, K, SetKeyofT> _ht;
    };
}

unordered_map

#pragma once
#include"hashtable.h"

namespace bear
{
    template<class K,class V>
    class unordered_map
    {
        struct MapKeyofT
        {
            const K& operator()(const pair<K,V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename hashbucket::HashTables<K, pair<const K, V>, MapKeyofT>::iterator iterator;
        typedef typename hashbucket::HashTables<K, pair<const K, V>, MapKeyofT>::const_iterator const_iterator;

        iterator begin()
        {
            return _ht.begin();
        }

        iterator end()
        {
            return _ht.end();
        }

        const_iterator begin() const
        {
            return _ht.begin();
        }

        const_iterator end() const
        {
            return _ht.end();
        }

        pair<iterator, bool> Insert(const pair<K,V>& kv)
        {
            return _ht.Insert(kv);
        }

        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }

        V& operator[](const K& key) const
        {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }

        iterator Find(const K& key)
        {
            return _ht.Find(key);
        }
        bool Erase(const K& key)
        {
            return _ht.Erase(key);
        }

    private:
        hashbucket::HashTables<K, pair<const K, V>, MapKeyofT> _ht;
    };
}