网硕互联帮助中心
目录
前言
Part1. map、set与红黑树
Part2. 红黑树的改造
Part2.1. map和set在传给红黑树模板参数的区别
Part2.2. 传给红黑树模板中第一个K的意义
Part2.3. 访问红黑树内数值与函数传参之间的矛盾
Part3. 迭代器的实现
Part3.1. ++的重载
Part3.2. –的重载
Part4. 代码实现
Part4.1. set
Part4.1. map
Part4.2. 红黑树
Part5. 结语
前言
了解STL容器最好的方法就是亲自去实现它，接下来跟随小编的视角来看看在实现map和set容器中会遇到的问题与困难吧。
let's go!!!!!!!!!
Part1. map、set与红黑树
map和set的底层都是红黑树，都用红黑树来管理数据。因此了解红黑树的实现是必要的，至于怎么实现红黑树，可以看这两篇博客：
【知识讲解】 红黑树的基本接口讲解（插入、判断等等）-CSDN博客
【知识讲解】 红黑树的删除讲解-CSDN博客
Part2. 红黑树的改造
我们知道，set只存一个数据就是单单的key，而map存两个，即key和value，两个构成映射关系。关键这两个底层都是红黑树，要想实现不是得实现两种红黑树？实则不用，这里用的的方法就是C++中的模板，我们来看。
同iterator和const_iterator的实现相似，都是利用模板不定参数，依靠编译器自己实现来简化代码。
逻辑：
<1> map、set模板：template<class k,class v,···>
<2> 给红黑树的模板：
rb_tree<k,k,····>//set
rb_tree<k,pair<k,v>,····>//map
<3> 节点：rb_tree_node<class v>
<4> rb_tree_node<v>//set
rb_tree_node<pair<k,v>>//map
Part2.1. map和set在传给红黑树模板参数的区别
在红黑树模板中，我们给出的第一个参数是键值，第二个给出的是数据，由于在set中数据和键值都是一起的所以两个写相同的，但是在map中就是给value了。
在给红黑树的模板中，为什么map的第二个参数是pair这个呢？因为这里模板第二个参数指代的意思是指红黑树每个结点的类型，在map的红黑树每个节点类型自然是pair了，因为有两个参数。
Part2.2. 传给红黑树模板中第一个K的意义
那为什么还要多一个参数，就是第一个k？这个参数代表的是键值，为什么要把这个独立出来呢？因为在红黑树的接口中，删除等需要这个类型，所以必须把这个独立出来。而没有单独的需要value类型的接口，只会需要键值和value结合的整体类型。故不用把value独立出来。
Part2.3. 访问红黑树内数值与函数传参之间的矛盾
由于map传给红黑树类型为pair，他访问的方式是.first/.second，与set的不同，它传的就可以直接用。他们的访问方式有区别，我们怎么解决呢？我们可以利用一个萃取器，就是仿函数，我们用这个函数取出来需要的数据，在map和set里面分别按照需求实现，这样就解决了。
Part3. 迭代器的实现
迭代器的大体实现主要还是和list一样，关键的难点在于++的重载，我们来看：
Part3.1. ++的重载
为什么++实现比较难，因为按照我们的逻辑，红黑树的遍历是中序遍历，也就是说在当前迭代器++后应该到它在中序遍历中的下一个节点对应的迭代器，关键我们怎么搞呢？我们来看图：
我们要求A处迭代器++后的结果，也就是要到下一个中序遍历的迭代器。中序遍历的顺序是左->根->右。A为这个局部树的根，我们现在能到这个位置说明左边（b）已经遍历完了，现在该到A的右子树了，到A的右子树（d），按照左->根->右，应该遍历他的左，如此循环，直到结点的左边为nullptr为止，这个节点就是下一个中序遍历的节点。结束。
我们现在能到这个位置说明左右已经遍历完了，说明其中序遍历结束了，该回到上一个根节点了，到B。由于A为B右子，说明B右也遍历完了，说明B的中序遍历也结束了，回到C，直到D，由于C为D的左边，象征这左边遍历完，该到根，也就是D本身。这个节点就是下一个中序遍历的节点。结束。
总结就是
<1> 当当前节点的右边为不为空，找其右子树的最左节点。
<2> 若为空，则向上索引，直到找到节点x的父亲节点的左边为x，返回父亲节点，当然要是父亲节点为空，说明此时x为根节点，说明此时整个树遍历完了，返回nullptr，结束。
Part3.2. –的重载
我们上面++重载的实现其实埋下了一个隐祸，就是当end()–时候，我们按照上面的逻辑，end()为nullptr，对这个–肯定会有问题，因此我们就要判断，当当前节点为nullptr时，我们返回_root的最右节点（中序遍历的最后一个），关键是我们的迭代器没有_root，因此我们要加一个_root成员来解决。
p.s. STL库解决这个问题是用一个哨兵位，它的_left指向整个树的最左，_right指向最右，它的_parent指向_root，_root的_parent指向它，这样确实会比较方便但是我们还要注意erase，insert对于这个的维护。
Part4. 代码实现
Part4.1. set
#include"头.h"
namespace all
{
template<class k>
class set
{
struct SetKeyOrT//萃取器
{
const k& operator()(const k& key)
{
return key;
}
};
public:
typedef typename RBTree<k,const k, SetKeyOrT>::iterator iterator;
typedef typename RBTree<k, const k, SetKeyOrT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
bool insert(const k& key)
{
return _t.insert(key);
}
private:
RBTree<k, const k, SetKeyOrT> _t;
};
}
Part4.1. map
#include"头.h"
namespace all
{
template<class k,class v>
class map
{
struct MapKeyOrT
{
const k& operator()(const pair<k, v>& p)
{
return p.first;
}
};
public:
typedef typename RBTree<const k, pair<const k, v>, MapKeyOrT>::iterator iterator;
typedef typename RBTree<const k, pair<const k, v>, MapKeyOrT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
bool insert(const pair<k,v>& value)
{
return _t.insert(value);
}
private:
RBTree<const k, pair<const k, v>, MapKeyOrT> _t;
};
}
Part4.2. 红黑树
#pragma once
#include<iostream>
#include<vector>
#include<map>
using namespace std;
enum colour
{
RED
, BLACK
};
template<class T>//红黑树节点
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{
}
};
template<class T,class Ref,class Ptr>
class RBTreeIterator;
template<class k , class T ,class KeyOrT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur!=nullptr&&cur->_left != nullptr)
{
cur = cur->_left;
}
return iterator(cur,_root);
}
iterator end()
{
return iterator(nullptr,_root);
}
const_iterator begin()const
{
Node* cur = _root;
while (cur != nullptr && cur->_left != nullptr)
{
cur = cur->_left;
}
return iterator(cur,_root);
}
const_iterator end()const
{
return iterator(nullptr,_root);
}
bool insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur != nullptr)
{
if (KeyOrT()(cur->_data) > KeyOrT()(data))
{
parent = cur;
cur = cur->_left;
}
else if (KeyOrT()(cur->_data) < KeyOrT()(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(data);
cur->_parent = parent;
if (KeyOrT()(parent->_data) > KeyOrT()(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_col = RED;
while (parent != nullptr && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
grandfather->_col = RED;
cur->_col = RED;
parent->_col = BLACK;
}
else
{
RotateLR(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
parent->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
grandfather->_col = RED;
cur->_col = RED;
parent->_col = BLACK;
}
else
{
RotateRL(grandfather);
grandfather->_col = RED;
cur->_col = BLACK;
parent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
bool erase(const k& key)
{
Node* z = find(key);
Node* x = nullptr;
if (z == nullptr)
{
return false;
}
colour col = z->_col;
Node* parent = z->_parent;
int lor = 0;
if (z->_left == nullptr&&z->_right!=nullptr)
{
if (z->_parent == nullptr)
{
_root = z->_right;
z->_right->_parent = nullptr;
z->_right->_col = BLACK;
delete z;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = z->_right;
lor = -1;
}
else
{
z->_parent->_right = z->_right;
lor = 1;
}
x = z->_right;
z->_right->_parent = z->_parent;
delete z;
}
else if (z->_left != nullptr && z->_right == nullptr)
{
if (z->_parent == nullptr)
{
_root = z->_left;
z->_left->_parent = nullptr;
z->_left->_col = BLACK;
delete z;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = z->_left;
lor = -1;
}
else
{
z->_parent->_right = z->_left;
lor =1;
}
x = z->_left;
z->_left->_parent = z->_parent;
delete z;
}
else if (z->_left == nullptr && z->_right == nullptr)
{
if (z->_parent == nullptr)
{
delete z;
_root = nullptr;
return true;
}
if (z->_parent->_left == z)
{
z->_parent->_left = nullptr;
lor = -1;
}
else
{
z->_parent->_right = nullptr;
lor = 1;
}
x = nullptr;
delete z;
}
else
{
Node* y = z->_right;
while (y->_left != nullptr)
{
y = y->_left;
}
z->_kv = y->_kv;
col = y->_col;
parent = y->_parent;
if (y->_parent->_left == y)
{
y->_parent->_left = y->_right;
lor = -1;
}
else
{
y->_parent->_right = y->_right;
lor = 1;
}
x = y->_right;
if (y->_right != nullptr)
{
y->_right->_parent = y->_parent;
}
delete y;
}
if (col == RED)
{
return true;
}
Node* w = nullptr;
if (lor == 1)
{
w = parent->_left;
}
else
{
w = parent->_right;
}
while (x != _root && (x==nullptr||x->_col==BLACK))
{
if (lor == -1)
{
if (w->_col == RED)
{
w->_col = BLACK;
parent->_col = RED;
Node* tem = w->_left;
RotateL(parent);
w = tem;
}
else if (w->_col == BLACK&&(w->_left==nullptr||w->_left->_col==BLACK)&&(w->_right==nullptr||w->_right->_col==BLACK))
{
w->_col = RED;
x = parent;
if (x == _root)
{
break;
}
else
{
if (x->_parent->_left == x)
{
w = x->_parent->_right;
lor = -1;
}
else
{
w = x->_parent->_left;
lor = 1;
}
parent = x->_parent;
}
}
else if (w->_col == BLACK && w->_left != nullptr && w->_left->_col == RED && (w->_right == nullptr || w->_right->_col == BLACK))
{
w->_left->_col = BLACK;
w->_col = RED;
Node* tem = w->_left;
RotateR(w);
w = tem;
}
else if (w->_col == BLACK && w->_right != nullptr && w->_right->_col == RED)
{
w->_col = parent->_col;
parent->_col = BLACK;
w->_right->_col = BLACK;
RotateL(parent);
x = _root;
}
}
else
{
if (w->_col == RED)
{
w->_col = BLACK;
parent->_col = RED;
Node* tem = w->_right;
RotateR(parent);
w = tem;
}
else if (w->_col == BLACK && (w->_left == nullptr || w->_left->_col == BLACK) && (w->_right == nullptr || w->_right->_col == BLACK))
{
w->_col = RED;
x = parent;
if (x == _root)
{
break;
}
else
{
if (x->_parent->_left == x)
{
w = x->_parent->_right;
lor = -1;
}
else
{
w = x->_parent->_left;
lor = 1;
}
parent = x->_parent;
}
}
else if (w->_col == BLACK && w->_right != nullptr && w->_right->_col == RED && (w->_left == nullptr || w->_left->_col == BLACK))
{
w->_right->_col = BLACK;
w->_col = RED;
Node* tem = w->_right;
RotateL(w);
w = tem;
}
else if (w->_col == BLACK && w->_left != nullptr && w->_left->_col == RED)
{
w->_col = parent->_col;
parent->_col = BLACK;
w->_left->_col = BLACK;
RotateR(parent);
x = _root;
}
}
}
if (x != nullptr) {
x->_col = BLACK;
}
_root->_col = BLACK;
return true;
}
void InOrder()const
{
_InOrder(_root);
}
void Is_RBTree()
{
if (_Is_RBTree(_root) != -1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
Node* find(const k& key)
{
Node* cur = _root;
while (cur != nullptr)
{
if (KeyOrT()(cur->_data) > KeyOrT()(data))
{
cur = cur->_left;
}
else if (KeyOrT()(cur->_data) < KeyOrT()(data))
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
if (parent->_parent != nullptr)
{
if (parent->_parent->_left == parent)
{
parent->_parent->_left = subL;
}
else
{
parent->_parent->_right = subL;
}
}
else
{
_root = subL;
}
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_parent = parent->_parent;
parent->_parent = subL;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
if (parent->_parent != nullptr)
{
if (parent->_parent->_left == parent)
{
parent->_parent->_left = subR;
}
else
{
parent->_parent->_right = subR;
}
}
else
{
_root = subR;
}
if (subRL != nullptr)
{
subRL->_parent = parent;
}
subR->_parent = parent->_parent;
parent->_parent = subR;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
RotateL(subL);
RotateR(parent);
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
RotateR(subR);
RotateL(parent);
}
void _InOrder(Node* root)const
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.second << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Is_RBTree(Node* root)
{
if (root == nullptr)
return 0;
int left = _Is_RBTree(root->_left);
int right = _Is_RBTree(root->_right);
if (left == -1 || right == -1)
{
return -1;
}
if (left != right)
{
return -1;
}
if (root->_col == RED)
{
if (root->_left != nullptr)
{
if (root->_left->_col != BLACK)
{
return -1;
}
}
if (root->_right != nullptr)
{
if (root->_right->_col != BLACK)
{
return -1;
}
}
return left + 0;
}
else
{
return left + 1;
}
}
Node* _root = nullptr;
};
template<class T, class Ref, class Ptr>
class RBTreeIterator
{
typedef RBTreeIterator<T, Ref, Ptr> self;
typedef RBTreeNode<T> Node;
public:
RBTreeIterator(Node* node,Node* root)
:_node(node)
,_root(root)
{
}
self operator++()
{
if (_node->_right != nullptr)
{
Node* cur = _node->_right;
while(cur->_left != nullptr)
{
cur = cur->_left;
}
_node = cur;
}
else
{
Node* parent = _node->_parent;
while (parent!=nullptr && _node != parent->_left)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
self operator–()
{
if (_node == nullptr)
{
Node* cur = _root;
while (cur->_right != nullptr)
{
cur = cur->_right;
}
_node = cur;
return *this;
}
else
{
if (_node->_left != nullptr)
{
Node* cur = _node->_left;
while (cur->_right != nullptr)
{
cur = cur->_right;
}
_node = cur;
}
else
{
Node* parent = _node->_parent;
while (parent != nullptr && _node != parent->_right)
{
_node = parent;
parent = parent->_parent;
}
_node = parent;
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const self& s)const
{
return s._node != _node;
}
private:
Node* _node;
Node* _root;//多一个_root
};
Part5. 结语
这篇文章我们认识到了map和set的实现，接下来，小编会带来哈希表的相关知识，敬请期待~
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~
评论前必须登录！
注册