今天我们用红黑树来模拟实现map和set，我们可以参考STL源码，不用自己造轮子。
一下是STL源码中的片段，它定义节点的颜色是用const的全局变量，同样需要三个指针left,right,parent.还用了一个继承，我也不知道大佬当时是怎么想的，其实不用继承也是一样可以搞，那么我们模拟实现就不搞继承了。大佬当时可能是出于某种原因吧。?
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
static base_ptr minimum(base_ptr x)
{
while (x->left != 0) x = x->left;
return x;
}
static base_ptr maximum(base_ptr x)
{
while (x->right != 0) x = x->right;
return x;
}
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};我们定义接定义节点的代码如下：
enum Colour
{
RED=0,
BALCK=1
};
//定义节点
template<class T>
class RBTreeNode
{
public:
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_data(data)
{
}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
};
template<class T,class Ref,class Ptr> //迭代器
class RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
RBTreeIterator(Node* node)
:_node(node)
{
}
}；
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator< T, const T&, const T*> const_iterator;
RBTree()
:_root(nullptr)
{
}
}；这些没啥好说的的，但是map和set在STL源码库中用的是一颗红黑树，但是set是k模型，map是K,V模型，那么我们先看一下大佬是怎么设置的。
?可以看出set和map一个传递的是key一个传递的pair，那红黑树怎么识别的，红黑树第三个模板参数可以将传递过来的参数取出来，在STL中仿函数的作用就体现出来了。要不然怎么说仿函数是STL六大组件之一呢。
所以在set中我们就可以定义仿函数的使用方法：代码如下：
#include"stl_tree.h"
namespace bit
{
template<class K>
class set
{
public:
class SetofT
{
public:
const K& operator()(const K& key)
{
return key;
}
};
typedef typename RBTree<K, K, SetofT>::iterator iterator;
std::pair<iterator, bool> insert(const K& key)
{
return _rb.insert(key);
}
iterator begin()
{
return _rb.begin();
}
iterator end()
{
return _rb.end();
}
private:
RBTree<K, K, SetofT> _rb;
};
void set_test()
{
set<int> s;
s.insert(1);
s.insert(4);
s.insert(2);
s.insert(24);
s.insert(2);
s.insert(12);
s.insert(6);
set<int>::iterator it = s.begin();
while (it != s.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for (auto e : s)
{
std::cout << e << " ";
}
std::cout << std::endl;
set<int> copy(s);
for (auto e : copy)
{
std::cout << e << " ";
}
std::cout << std::endl;
set<int> ss;
ss.insert(111);
ss.insert(422);
copy = ss;
for (auto e : copy)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
}在map中仿函数的定义如下：
#include"stl_tree.h"
namespace bit
{
template<class K, class V>
class map
{
public:
class MapOfT
{
public:
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
typedef typename RBTree<K, std::pair<K, V>, MapOfT>::iterator iterator;
iterator begin()
{
return _rb.begin();
}
iterator end()
{
return _rb.end();
}
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _rb.insert(kv);
}
V& operator[](const K& key)
{
auto ret = _rb.insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, std::pair<K, V>, MapOfT> _rb;
};
void test_map()
{
map<std::string, std::string> dict;
dict.insert(std::make_pair("sort", "排序"));
dict.insert(std::make_pair("string", "字符串"));
dict.insert(std::make_pair("map", "地图"));
dict["left"];
dict["left"] = "剩余";
dict["map"] = "地图/容器";
auto it = dict.begin();
while (it != dict.end())
{
std::cout << it->first << ":" << it->second << std::endl;
++it;
}
std::cout << std::endl;
}
}typedef typename RBTree<K, std::pair<K, V>, MapOfT>::iterator iterator;这句代码很重要，如果不加typename会编译报错，没有办法实例化，加了可以告诉编译器先去推导，等实例化之后在去执行。
下面我们来看看红黑树的迭代器的实现代码如下：
//红黑树迭代器
template<class T,class Ref,class Ptr>
class RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
RBTreeIterator(Node* node)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min != nullptr && min->_left != nullptr)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right != nullptr)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator !=(const Self& s) const
{
return _node != s._node;
}
bool operator ==(const Self& s) const
{
return _node == s._node;
}
private:
Node* _node;
};迭起器的++和--：
?
?对红黑树的改造，只需要把比较的时候用set,map各自的仿函数，进行比较即可。
std::pair<iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BALCK;
return std::make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot; //定义仿函数对象
while (cur != nullptr)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return std::make_pair(iterator(cur), false);
}
}
//申请节点
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(data) > kot(parent->_data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
}红黑树全部代码如下：
stl_tree.h
#pragma once
#include<iostream>
namespace bit
{
enum Colour
{
RED=0,
BALCK=1
};
//定义节点
template<class T>
class RBTreeNode
{
public:
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_data(data)
{
}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
};
//红黑树迭代器
template<class T,class Ref,class Ptr>
class RBTreeIterator
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
RBTreeIterator(Node* node)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min != nullptr && min->_left != nullptr)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right != nullptr)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent != nullptr && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator !=(const Self& s) const
{
return _node != s._node;
}
bool operator ==(const Self& s) const
{
return _node == s._node;
}
private:
Node* _node;
};
//红黑树
template<class K,class T,class KeyOfT> //第三个模板参数为仿函数
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator< T, const T&, const T*> const_iterator;
RBTree()
:_root(nullptr)
{
}
RBTree(const RBTree<K, T, KeyOfT>& s)
{
_root = Copy(s._root);
}
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> s)
{
std::swap(_root, s._root);
return *this;
}
~RBTree()
{
Destroy(_root);
}
iterator begin()
{
Node* min = _root;
while (min != nullptr && min->_left != nullptr)
{
min = min->_left;
}
return iterator(min);
}
iterator end()
{
return iterator(nullptr);
}
iterator find(const K& key)
{
Node* cur = _root;
if (key > kot(cur->_data))
{
cur = cur->_right;
}
else if (key < kot(cur->_data))
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
std::pair<iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BALCK;
return std::make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
while (cur != nullptr)
{
if (kot(data) > kot(cur->_data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(data) < kot(cur->_data))
{
parent = cur;
cur = cur->_left;
}
else
{
return std::make_pair(iterator(cur), false);
}
}
//申请节点
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(data) > kot(parent->_data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//控制平衡
while (parent != nullptr && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//情况1:uncle存在且为红
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BALCK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
//情况2：uncle不存在/存在且为黑，旋转
else
{
if (cur == parent->_left) //右单旋
{
RotateR(grandfather);
grandfather->_col = RED;
parent->_col = BALCK;
}
else //左右双旋
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BALCK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
//情况1:uncle存在且为红
if (uncle != nullptr && uncle->_col == RED)
{
parent->_col = uncle->_col = BALCK;
grandfather->_col = RED;
//继续向上更新
cur = grandfather;
parent = cur->_parent;
}
else//情况2：uncle不存在/存在且为黑，旋转
{
if (cur == parent->_right) //左单旋
{
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BALCK;
}
else //右左双旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BALCK;
grandfather->_col = RED;
}
}
break;
}
}
_root->_col = BALCK;
return std::make_pair(iterator(newnode), true);
}
private:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentparent = parent->_parent;
parent->_left = subLR;
if (subLR != nullptr)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subL;
else
parentparent->_right = subL;
subL->_parent = parentparent; //维护三叉链
}
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentparent = parent->_parent;
parent->_right = subRL;
if (subRL != nullptr)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
parentparent->_left = subR;
else
parentparent->_right = subR;
subR->_parent = parentparent; //维护三叉链
}
}
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_data);
newnode->_col = root->_col;
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
if (newnode->_left != nullptr)
newnode->_left->_parent = newnode;
if (newnode->_right != nullptr)
newnode->_right->_parent = newnode;
return newnode;1
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
private:
Node* _root;
};
}细节主要是在旋转的细节上，其他的都是在红黑树的基础上进行封装。
set.h
#include"stl_tree.h"
namespace bit
{
template<class K>
class set
{
public:
struct SetOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetOfT>::iterator iterator;
std::pair<iterator, bool> insert(const K& key)
{
return _rb.insert(key);
}
iterator begin()
{
return _rb.begin();
}
iterator end()
{
return _rb.end();
}
iterator find(const K& key)
{
return _rb.find(key);
}
private:
RBTree<K, K, SetOfT> _rb;
};
void test_set()
{
set<int> s;
s.insert(1);
s.insert(4);
s.insert(2);
s.insert(24);
s.insert(2);
s.insert(12);
s.insert(6);
set<int>::iterator it = s.begin();
while (it != s.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
for (auto e : s)
{
std::cout << e << " ";
}
std::cout << std::endl;
set<int> copy(s);
for (auto e : copy)
{
std::cout << e << " ";
}
std::cout << std::endl;
set<int> ss;
ss.insert(111);
ss.insert(422);
copy = ss;
for (auto e : copy)
{
std::cout << e << " ";
}
std::cout << std::endl;
}
}
map.h
#include"stl_tree.h"
namespace bit
{
template<class K, class V>
class map
{
public:
class MapOfT
{
public:
const K& operator()(const std::pair<K,V>& kv)
{
return kv.first;
}
};
typedef typename RBTree<K, std::pair<K, V>, MapOfT>::iterator iterator;
iterator begin()
{
return _rb.begin();
}
iterator end()
{
return _rb.end();
}
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _rb.insert(kv);
}
V& operator[](const K& key)
{
auto ret = _rb.insert(std::make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, std::pair<K, V>, MapOfT> _rb;
};
void test_map()
{
map<std::string, std::string> dict;
dict.insert(std::make_pair("sort", "排序"));
dict.insert(std::make_pair("string", "字符串"));
dict.insert(std::make_pair("map", "地图"));
dict["left"];
dict["left"] = "剩余";
dict["map"] = "地图/容器";
auto it = dict.begin();
while (it != dict.end())
{
std::cout << it->first << ":" << it->second << std::endl;
++it;
}
std::cout << std::endl;
}
}test.cpp
#include"set.h"
#include"map.h"
int main()
{
//bit::set_test();
bit::test_map();
}
