C++STL——map和set的模拟实现
ℳℓ白ℳℓ夜ℳℓ
帮助1人
map与set的部分源码参考
map和set的底层都是由红黑树实现的。
所以这里将上次实现的红黑树插入拿来用。
首先想一想，搜索二叉树不能修改值，因为会破坏整棵树的平衡。
set与map的部分源码：
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
typedef rb_tree<key_type, value_type, //set这里传了一个K，一个V
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
// typedefs:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type, //map这里传了一个K，一个V
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
这个是红黑树的部分源码：
template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
public:
typedef rb_tree_node* link_type;
protected:
size_type node_count; // keeps track of size of tree
link_type header;
Compare key_compare;
set要传入到红黑树的Value的值是K,map要传入的值是pair<const K,V>
那么，这里完全可以区分传入的是set还是map，为什么要给红黑树传入第一个模板参数呢？
第一个模板参数是用来查找的，因为无论是set还是map都是用kay去查找的。
改造红黑树
这是红黑树的结点：
enum Color//利用枚举来给红黑树配色
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)//让红黑树的结点变成一个模板就行了，因为有可能是set有可能是map
:_data(data)
, _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
T _data;
Color _color;//结点的配色
};
namespace baiye
{
template<class K>
class set
{
public:
private:
RBTree<K, K> _t;//K模型
};
}
namespace baiye
{
template<class K, class V>
class map
{
public:
private:
RBTree<K, pair<const K, V>> _p;//KV模型
};
}
然后我们发现，后面的插入这里调用出现了问题：
原来写的是VK模型，但是现在set是K模型，要兼容两个模型。
让我们来看看源码是怎么做的：
源码这里多了一个模板参数，意思是将key取出来比较大小。
这里可以写两个仿函数用：
namespace baiye
{
template<class K>
class set
{
struct setKeyOFV
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, setKeyOFV> _t;
};
}
namespace baiye
{
template<class K, class V>
class map
{
struct mapKeyOFV
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<const K, V>& kv)
{
return _p.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, mapKeyOFV> _p;
};
}
红黑树的迭代器
先来实现*与->：
template<class T>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
};
迭代器难的是 和- -操作：
原来stl中的红黑树其实有一个哨兵位的头结点：
哨兵位中还有两个指针分别指向红黑树中的最小值和最大值，但是这里我并没有去实现这个哨兵位，所以就用另一种方法。
首先先给红黑树加begin和end函数：
iterator begin()
{
Node* cur = _root;
while (cur && cur->left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
然后是 ， 是要走中序遍历的，我们要采用迭代的方式，以前要借助一个队列来进行中序遍历的方法进行 。
假设我们传入的迭代器的结点是8结点，那么下一个结点就是10号结点，也就是8号结点的右子树最小结点。
那么如果右为空呢？
右子树为空就说明不需要去右子树找了，需要向上找节点，假设是这样子的：
it指向5结点，发现右为空，那就向上走，走到6结点发现右不为空然后走到7结点，7结点右为空就要继续往上走，这个时候不应该走到6结点的位置，应该是8结点的位置。
假设这里再多出一个结点：
那么他的右为空也不能再走到7结点的位置了。
所以我们能总结出来一个规律。
右不为空就去找右子树的最小节点。
右为空就去找祖先（孩子为父节点的左的那个祖先）
如果是it在15结点这个位置，往上走没有遇到符合祖先的位置，并且已经走到空了，那就代表已经结束了。
Self& operator ()
{
if (_node->_right)//右子树不为空
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//左子树为空
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_left != cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
然后来实现- -逻辑：
Self& operator--()
{
if (_node->_left)//左子树不为空
{
Node* cur = _node->_left;
while (cur && cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur != parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
补全set与map的实现
set当中的值是不允许被修改的。
这里我们就要实现const版本的迭代器：
template<class T,class Ref, class Ptr>
struct RBTreeIterator//红黑树的迭代器
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
先将这两个函数变成能兼容const和非const版本。
看一下set源码是怎么定义迭代器的：
那么set当中就算是非const版本的迭代器也不能修改值：
template<class K>
class set
{
struct setKeyOFV
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本
typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, setKeyOFV> _t;
};
但是我们的begin函数和end函数的返回值和重命名的迭代器类型已经不相同了。
所以看看set源码是如何做到的：
后面加了一个const就解决了问题，因为权限可以缩小，传入的就算是非const版本也可以。
在set的begin与end中加了个const就说明要去调用const版本的begin与end，所以在树那里也要实现const版本的begin与end。
template<class K, class T, class KeyOFV>
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 && 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 const_iterator(cur);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
然后来实现map的const版本的迭代器：
先看看源码：
template<class K, class V>
class map
{
struct mapKeyOFV
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator;
iterator begin()
{
return _p.begin();
}
iterator end()
{
return _p.end();
}
const_iterator begin()const
{
return _p.begin();
}
const_iterator end()const
{
return _p.end();
}
bool insert(const pair<const K, V>& kv)
{
return _p.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, mapKeyOFV> _p;
};
然后就是[]重载了：
这里首先要改插入的返回值和返回类型。
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOFV kot;//仿函数对象
while (cur)
{
if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);//这里默认是红色结点
Node* newnode = cur;//因为cur会变位置，所以储存一下新节点
if (kot(parent->_data) > kot(data))
{
cur->_parent = parent;
parent->_left = cur;
}
else if (kot(parent->_data) < kot(data))
{
cur->_parent = parent;
parent->_right = cur;
}
//如果父节点为空就代表cur是根节点，没必要调整了
//还要判断cur结点是否与父节点的颜色均为红色
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;//祖父结点
if (parent == grandfather->_left)//新增结点在祖父左
{
Node* uncle = grandfather->_right;
//情况一
if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在
{
parent->_color = BLACK;
uncle->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;//最后让cur等于祖父结点的位置
parent = cur->_parent;
}
else
{
if (parent->_left == cur)//情况二
{
RotateR(grandfather);//右单旋
grandfather->_color = RED;
parent->_color = BLACK;
}
else if (parent->_right == cur)//情况三
{
RotateL(parent);//左单旋
RotateR(grandfather);//右单旋
cur->_color = BLACK;
grandfather->_color = RED;
}
break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环
}
}
else//新增结点在祖父右
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_color == RED)//情况一
{
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
if (cur == parent->_right)//情况二
{
RotateL(grandfather);
grandfather->_color = RED;
parent->_color = BLACK;
}
else if (cur == parent->_left)//情况三
{
RotateR(parent);
RotateL(grandfather);
cur->_color = BLACK;
grandfather->_color = RED;
}
break;
}
}
}
_root->_color = BLACK;
return make_pair(iterator(newnode), true);
}
[]在map中重载即可：
V& operator[](const K& key)
{
pair<iterator, bool> it = insert(make_pair(key, V()));
return it.first->second;
}
因为树种插入的函数改变了返回值，所以set与map的插入调用函数也要改变返回值，但是set当中插入的返回值是非const类型：
这里看看源码是如何解决的：
这里使用了rep_type类型去接收，然后再用p去重新构造一个pair<iterator, bool>类型。
这是构造，为了解决非const的迭代器不能拷贝给const迭代器的问题。
完整代码
RBTree.h
#include<iostream>
#include<cassert>
using namespace std;
enum Color//利用枚举来给红黑树配色
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode(const T& data)
:_data(data)
, _color(RED)//这里一定要给红色，如果给黑色其他路径就要涉及到也要加黑色结点，更加麻烦
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
T _data;
Color _color;//结点的配色
};
template<class T,class Ref, class Ptr>
struct RBTreeIterator//红黑树的迭代器
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
typedef RBTreeIterator<T, T&, T*> iterator;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
//普通迭代器传给普通迭代器用的是默认生成的拷贝构造
//当迭代器是const的时候用的就是普通迭代器构造的const迭代器
RBTreeIterator(const iterator& s)
:_node(s._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* parent = _node->_parent;
Node* cur = _node;
while (parent && parent->_left != cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)//左子树不为空
{
Node* cur = _node->_left;
while (cur && cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur != parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
template<class K, class T, class KeyOFV>
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 && 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 const_iterator(cur);
}
const_iterator end()const
{
return const_iterator(nullptr);
}
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOFV kot;//仿函数对象
while (cur)
{
if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);//这里默认是红色结点
Node* newnode = cur;//因为cur会变位置，所以储存一下新节点
if (kot(parent->_data) > kot(data))
{
cur->_parent = parent;
parent->_left = cur;
}
else if (kot(parent->_data) < kot(data))
{
cur->_parent = parent;
parent->_right = cur;
}
//如果父节点为空就代表cur是根节点，没必要调整了
//还要判断cur结点是否与父节点的颜色均为红色
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;//祖父结点
if (parent == grandfather->_left)//新增结点在祖父左
{
Node* uncle = grandfather->_right;
//情况一
if (uncle && uncle->_color == RED)//这里不要忘记验证uncle的存在
{
parent->_color = BLACK;
uncle->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;//最后让cur等于祖父结点的位置
parent = cur->_parent;
}
else
{
if (parent->_left == cur)//情况二
{
RotateR(grandfather);//右单旋
grandfather->_color = RED;
parent->_color = BLACK;
}
else if (parent->_right == cur)//情况三
{
RotateL(parent);//左单旋
RotateR(grandfather);//右单旋
cur->_color = BLACK;
grandfather->_color = RED;
}
break;//第二种和第三种情况变完之后因为最上面的组节点变为黑，所以这里跳出循环
}
}
else//新增结点在祖父右
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_color == RED)//情况一
{
uncle->_color = BLACK;
parent->_color = BLACK;
grandfather->_color = RED;
cur = grandfather;
parent = cur->_parent;
}
else {
if (cur == parent->_right)//情况二
{
RotateL(grandfather);
grandfather->_color = RED;
parent->_color = BLACK;
}
else if (cur == parent->_left)//情况三
{
RotateR(parent);
RotateL(grandfather);
cur->_color = BLACK;
grandfather->_color = RED;
}
break;
}
}
}
_root->_color = BLACK;
return make_pair(iterator(newnode), true);
}
void RotateL(Node* parent)//左单旋
{
Node* pparent = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (pparent)
{
if (pparent->_left == parent)
pparent->_left = subR;
else
pparent->_right = subR;
}
else
{
_root = subR;
}
subR->_parent = pparent;
}
void RotateR(Node* parent)//右单旋
{
Node* pparent = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (pparent)
{
if (pparent->_left == parent)
pparent->_left = subL;
else
pparent->_right = subL;
}
else
{
_root = subL;
}
subL->_parent = pparent;
}
void Inorder()
{
_Inorder(_root);
}
bool IsBalanceTree()
{
if (_root == nullptr)
return true;
if (_root->_color != BLACK)
{
cout << "根不为黑色" << endl;
return false;
}
int count = 0;
Node* cur = _root;
while (cur)
{
if (cur->_color == BLACK)
count ;
cur = cur->_left;//找一条路径上的黑节点
}
_IsBalanceTree(_root, 0, count);
}
private:
bool _IsBalanceTree(Node* root, int k, int sum)//验证
{
if (root == nullptr)
{
if (k == sum)//这里代表当前路径点和最左边的路径点相同
return true;
else
{
cout << "每条路径上黑色结点数量不同" << endl;
}
return false;
}
if (root->_color == BLACK)
k ;
if (root->_parent && root->_parent->_color == RED && root->_color == RED)
{
cout << root->_parent->_data.first << endl;
return false;
}
return _IsBalanceTree(root->_left, k, sum) && _IsBalanceTree(root->_right, k, sum);
}
void _Inorder(Node* _root)
{
if (_root == nullptr)
return;
_Inorder(_root->_left);
cout << _root->_data.first << ":" << _root->_data.second << endl;
_Inorder(_root->_right);
}
Node* _root = nullptr;
};
set.h
#include"RBTree.h"
namespace baiye
{
template<class K>
class set
{
struct setKeyOFV
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, setKeyOFV>::const_iterator iterator;//这里无论是非const迭代器也不能修改set的值，所以要变成const版本
typedef typename RBTree<K, K, setKeyOFV>::const_iterator const_iterator;
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
pair<typename RBTree<K, K, setKeyOFV>::iterator, bool> it = _t.Insert(key);//这里接收的是普通迭代器
return pair<iterator, bool>(it.first, it.second);//这里用普通迭代器构造const迭代器
}
private:
RBTree<K, K, setKeyOFV> _t;
};
void settest()
{
int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
set<int>s;
for (auto& e : arr)
{
s.insert(e);
}
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it;
}
cout << endl;
}
}
map.h
#include"RBTree.h"
namespace baiye
{
template<class K, class V>
class map
{
struct mapKeyOFV
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, mapKeyOFV>::const_iterator const_iterator;
iterator begin()
{
return _p.begin();
}
iterator end()
{
return _p.end();
}
const_iterator begin()const
{
return _p.begin();
}
const_iterator end()const
{
return _p.end();
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _p.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> it = insert(make_pair(key, V()));
return it.first->second;
}
private:
RBTree<K, pair<const K, V>, mapKeyOFV> _p;
};
void maptest()
{
int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map<int, int> m;
for (auto& e : arr)
{
m.insert(make_pair(e, e));
}
map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << " ";
it;
}
cout << endl;
}
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgcacge
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
