学过的模拟实现（不定期更新）

本文主要是介绍学过的模拟实现（不定期更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

string模拟

list模拟

#pragma once#include<assert.h>
namespace bear
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//构造函数1vector():_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 = v2vector<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;//构造函数1vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//拷贝构造1vector(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);}}//拷贝构造2vector(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 = v2vector<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; //空树的高度为0return 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结点链接subRLsubR->_left = parent;//让subR的左子树链接parentparent->_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结点链接subRLsubR->_left = parent;//让subR的左子树链接parentparent->_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;//空间-1return 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;};
}

这篇关于学过的模拟实现（不定期更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---