【C++】map和set的模拟实现
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
🌠 作者@阿亮joy.
🎆专栏《吃透西嘎嘎》
🎇 座右铭每个优秀的人都有一段沉默的时光那段时光是付出了很多努力却得不到结果的日子我们把它叫做扎根
目录
👉红黑树的改造👈
节点和模板参数的改造
我们知道map 和 set 的底层数据结构都是红黑树那库里是写了两份红黑树的代码来分别实例化出 map 和 set 吗其实不是而给一颗泛型结构的红黑树传不同的实例化参数从而实现 map 和 set。
通过上图可以看到map 传给红黑树的key_type是Keyvalue_type是pair<Key, T>而 set 传给红黑树的key_type和value_type都是Key。红黑树的节点中存储数据就是value_type类型的数据并不是像我们写的那样直接存储键值对pair<K, V>。如果传给value_type的是pair<Key, T>那么就会实例化出 map而传给value_type的是Key就会实例化出 set。那么现在我们也将自己实现的红黑树改造一下。
#pragma once
// 用枚举常量来代表颜色
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
{}
};
template<class K, class T>
struct RBTree
{
typedef RBTreeNode<K, T> Node;
private:
Node* _root = nullptr;
}
改造红黑树的模板参数和节点后就会带了一个问题我们该如何比较_data的大小因为 map 的数据类型是pair<K, T>而 set 的数据类型是Key。那怎么才能用一份泛型代码同时实现键值对的比较和Key的比较呢第一种方式就是重载键值对的比较。库里也实现了键值对的比较但是并不是我们想要的。
库里实现的键值对的大小比较是如果first没有比较出结果还会比较second。这不是我们想要的因为 map 键值对的比较只会比较first并不会比较second。如果我们想要这样比较的话那么就只能自己再实现一个pair了。这样会过于麻烦那么我们可以采取第二种方式通过一个仿函数来拿到节点数据的类型。
那么现在就能比较大小了我们将 map 和 set 简单地封装一下调试看看写得对不对。
调试样例
通过上面的调试可以看到确实可以拿到Key去比较。那么这样我们就通过红黑树实例化出 map 和 set。
红黑树的迭代器
STL 明确规定begin() 与 end() 代表的是一段前闭后开的区间而对红黑树进行中序遍历可以得到一个有序的序列。因此begin() 可以放在红黑树中最小节点即最左侧节点的位置end() 放在最大节点最右侧节点的下一个位置。注最大节点的下一个位置可以认为是
nullptr。 而库里的红黑多加了一个哨兵位的头节点headerheader的左指针指向最小节点右指针指向最大节点父指针指向根节点根节点的父指针指向header。如下图所示
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);
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
Self& operator++()
{
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
// 下一个是孩子不是在父亲的右边的第一个祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
// 下一个就是左子树的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
// 下一个是孩子不是父亲的左边的第一个祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
};
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, T&, T*> iterator;
public:
// begin()为树的最左节点
iterator begin()
{
// 注需要避免_root为nullptr
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
// end()可以设置为nullptr
iterator end()
{
return iterator(nullptr);
}
private:
Node* _root = nullptr;
}
注map 和 set 的迭代器也是封装了红黑树的迭代器的。红黑树的反向迭代器可以自己尝试实现reverse_begin()是最右节点reverse_end()是 nullptr。因为我们没有添加哨兵位的头节点了所以就可能比较难用封装正向迭代器的方式来实现方向迭代器。
测试迭代器
void MapTest1()
{
map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(5, 5));
m.insert(make_pair(2, 2));
map<int, int>::iterator it = m.begin();
while (it != m.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
}
void SetTest1()
{
set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
红黑树的完整代码
现在红黑树的迭代器也实现完了那么我们再来改造一下红黑树的 insert 函数让它返回pair<iterator, bool>。insert 函数改造完成后那么红黑树的代码就实现完了。注除了红黑树的删除节点没有实现还有树的销毁和拷贝构造等内容可以参考二叉树搜索树的实现
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
// 用枚举常量来代表颜色
enum Colour
{
RED,
BLACK
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
T _data;
Colour _col;
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
{}
};
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);
}
bool operator!=(const Self& it) const
{
return _node != it._node;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
Self& operator++()
{
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
// 下一个是孩子不是在父亲的右边的第一个祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
// 下一个就是左子树的最右节点
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
// 下一个是孩子不是父亲的左边的第一个祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
};
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, T&, T*> iterator;
public:
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot; // 通过T来获取Key的一个仿函数类
// 根节点的颜色为黑色
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 以搜索二叉树的方式插入
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);
}
}
// 插入节点
cur = new Node(data);
// 因为变色和旋转要修改cur,所以将新增节点的指针保存
// 在newnode中方便后续构造迭代器
Node* newnode = cur;
cur->_col = RED; // 新插入节点默认为红色
// 判断在哪一边插入
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 当parent存在且为红色,则需要继续往上处理
// 当parent为空或为黑色时,则不需要往上处理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
assert(grandfather);
assert(grandfather->_col == BLACK);
// 关键看叔叔
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
// 情况一uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况二和三uncle不存在或uncle存在且为黑
{
// 情况二右单旋+变色
// g p
// p u ==> c g
// c u
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 情况三parent先做左单旋,grandfather再做右单旋,最后变色
// g g c
// p u ==> c u ==> p g
// c p u
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
Node* uncle = grandfather->_left;
// 情况一uncle存在且为红
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else //情况二和三uncle不存在或uncle存在且为黑
{
// 情况二左单旋+变色
// g p
// u p ==> g c
// c u
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// 情况三parent先做右单旋,grandfather再做左单旋,最后变色
// g g c
// u p ==> u c ==> g p
// c p u
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 根节点永远是黑色
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
void InOrder()
{
_InOrder(_root);
}
bool IsBalance()
{
if (_root == nullptr)
return true;
if (_root->_col != BLACK)
{
cout << "根节点不是黑色" << endl;
return false;
}
// 黑色节点数量的基准值
int mark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++mark;
cur = cur->_left;
}
return PrevCheck(_root, 0, mark);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
bool PrevCheck(Node* root, int blackNum, int mark)
{
if (root == nullptr)
{
if (blackNum != mark)
{
cout << "某条路径上的黑色节点的数量不相等" << endl;
return false;
}
else
return true;
}
if (root->_col == BLACK)
++blackNum;
// 检查父亲
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在连续的红色节点" << endl;
}
return PrevCheck(root->_left, blackNum, mark)
&& PrevCheck(root->_right, blackNum, mark);
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
private:
Node* _root = nullptr;
};
map 和 set 的完整代码
红黑树的代码已经实现完了那么现在就用红黑树实现出 map 和 set。
map 的完整代码
#pragma once
#include "RBTree.h"
namespace Joy
{
template <class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>&kv)
{
return kv.first;
}
};
public:
// typename的作用是告诉编译器这是类型的重命名,并不是静态变量
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
// 有就插入失败,没有就插入成功,但是都能够得到该节点的迭代器
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}
统计出现次数
void MapTest2()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
// 1、str不在countMap中插入pair(str, int()),然后在对返回次数++
// 2、str在countMap中返回value(次数)的引用次数++;
countMap[str]++;
}
map<string, int>::iterator it = countMap.begin();
while (it != countMap.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << "-------" << endl;
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
set 的完整代码
#pragma once
#include "RBTree.h"
namespace Joy
{
template <class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K & key)
{
return key;
}
};
public:
// typename的作用是告诉编译器这是类型的重命名,并不是静态变量
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
👉总结👈
本篇博客主要改造了之前模拟实现的红黑树以及将改造后的红黑树模拟实现出 map 和 set等等。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家💖💝❣️