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;
};
}