【C++】map和set的模拟实现
在本篇博客中,作者将会带领你模拟实现C++STL库中的容器map和set,其中我只实现一些比较重要的成员函数,在进行之前,你需要先懂得红黑树,因为map和set的底层数据结构就是红黑树,红黑树的讲解可以看下面这篇博客:
一.map和set的基本结构
在模拟实现map和set之前,我们需要知道它们的基本结构。
map和set是基于红黑树而实现的容器,如下图所示。
所以在模拟实现map和set之前,我们需要先实现出一棵红黑树出来,而红黑树的实现,在这里不进行过多的讲解,不懂的可以看上面的博客链接,在这里,我就直接从模拟map和set开始。
红黑树的实现
blog_RBTree.h
#pragma once
#include<iostream>
#include<time.h>
using namespace std;
namespace blog_RBTree
{
enum Color
{
BLACK,
RED
};
template<class T>
struct TreeNode
{
//成员变量
T _data;//数据
TreeNode<T>* _left;
TreeNode<T>* _right;
TreeNode<T>* _parent;
Color _col;//保存结点的颜色
//构造函数
TreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)//每生成一个新结点,都将结点的颜色默认给红色,至于为什么,后面会解释
{}
};
template<class T>
class RBTree
{
typedef TreeNode<T> Node;
public:
//构造函数
RBTree()
:_root(nullptr)//给根结点一个nullptr
{}
//插入结点
bool insert(const T& data)
{
//如果树为NULL,则直接将新结点给到_root
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
return true;
}
Node* cur = _root;
Node* cur_parent = nullptr;
while (cur != nullptr)
{
if (data > cur->_data)
{
cur_parent = cur;
cur = cur->_right;
}
else if (data < cur->_data)
{
cur_parent = cur;
cur = cur->_left;
}
else//说明该值已经存在,不进行插入
{
return false;
}
}
//将新结点插入
cur = new Node(data);
if (cur_parent->_data > data)
{
cur_parent->_left = cur;
cur->_parent = cur_parent;
}
else
{
cur_parent->_right = cur;
cur->_parent = cur_parent;
}
//调整结点代码
while (cur_parent != nullptr && cur_parent->_col == RED)
{
Node* grandparent = cur_parent->_parent;
if (grandparent->_left == cur_parent)//正方向
{
Node* uncle = grandparent->_right;
if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
cur_parent = cur->_parent;
}
else//情况二和情况三
{
//这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
if (cur_parent->_right == cur)//这种情况就是情况三
{
//先进行一个左单旋
RotateL(cur_parent);
swap(cur, cur_parent);
}
//代码走到这里就一定是情况二了
RotateR(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
else if (grandparent->_right == cur_parent)//反方向
{
Node* uncle = grandparent->_left;
if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
cur_parent = cur->_parent;
}
else//反方向的情况二和情况三
{
if (cur_parent->_left == cur)
{
RotateR(cur_parent);
swap(cur, cur_parent);
}
RotateL(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
}
_root->_col = BLACK;
}
private:
//左单旋
void RotateL(Node* cur_parent)
{
Node* cur = cur_parent->_right;
Node* cur_left = cur->_left;
//改变指针的链接关系
cur_parent->_right = cur_left;
if (cur_left != nullptr)
{
cur_left->_parent = cur_parent;
}
cur->_left = cur_parent;
Node* cur_parent_parent = cur_parent->_parent;
cur_parent->_parent = cur;
//旋转完成后要判断cur_parent是否为根
if (cur_parent_parent != nullptr)//说明cur_parent不是根
{
if (cur_parent_parent->_data < cur_parent->_data)
{
cur_parent_parent->_right = cur;
cur->_parent = cur_parent_parent;
}
else
{
cur_parent_parent->_left = cur;
cur->_parent = cur_parent_parent;
}
}
else//说明cur_parent是根
{
_root = cur;
cur->_parent = nullptr;
}
}
//右单旋
void RotateR(Node* cur_parent)
{
Node* cur = cur_parent->_left;
Node* cur_right = cur->_right;
cur_parent->_left = cur_right;
if (cur_right != nullptr)
{
cur_right->_parent = cur_parent;
}
cur->_right = cur_parent;
Node* cur_parent_parent = cur_parent->_parent;
cur_parent->_parent = cur;
if (cur_parent_parent != nullptr)
{
if (cur_parent_parent->_data > cur_parent->_data)
{
cur_parent_parent->_left = cur;
cur->_parent = cur_parent_parent;
}
else
{
cur_parent_parent->_right = cur;
cur->_parent = cur_parent_parent;
}
}
else
{
_root = cur;
cur->_parent = nullptr;
}
}
private:
Node* _root;
};
}
二.map和set的模拟实现
当我们的红黑树完成好后,就可以开始实现我们的map和set了,但是我的这棵红黑树虽然已经能用了,但是对于模拟实现map和set而言,还有一些问题,对于这些问题,我会在后续的实现中进行改进和讲解。
1.红黑树的改变
在模拟实现map和set之前,我们需要改变一下我们的红黑树,为什么呢?
我们先来看看红黑树的结点定义:
template<class T> struct TreeNode { //成员变量 T _data;//数据 TreeNode<T>* _left; TreeNode<T>* _right; TreeNode<T>* _parent; Color _col;//保存结点的颜色 //构造函数 TreeNode(const T& data) :_data(data) ,_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_col(RED)//每生成一个新结点,都将结点的颜色默认给红色,至于为什么,后面会解释 {} };
从红黑树的结点定义中,我们可以看到红黑树中存的是一个T类型的模板参数,然而,我们知道,map和set之间的区别就是,set中存的是一个普通类型的变量,而map中存的是一个pair,所以这里就会有一个问题。
当我们的红黑树进行插入的时候,它会进行一个比较:如下图所示
if (data > cur->_data)
这个时候的问题就是,如果我们用的是set,那还没有问题,但是当我们用map的时候就有问题了,因为此时的data是一个pair,pair之间的比较不是我们想要的,我们想要的是pair中的Key值来进行比较,所以这个时候的红黑树是不满足我们的要求的,所以我们需要对它进行改变。
对于红黑树的改变是,我们用一个仿函数GCV来实现set或map的比较。如下图所示。
gcv(data) > gcv(cur->_data)//GCV是一个仿函数,用于将data中需要比较的值取出来,例如:如果是set,则将Key取出来,如果是map,则将pair中的Key取出来
在上面的代码中,我在数据data前加了一个gcv,这个gcv是一个类重载了operator()这个运算符重载。这个gcv的仿函数的作用是将data中要比较的值取出来。这样不管是set还是map都能实现我们想要的效果。
2.set和map的基本雏形
当我们的红黑树改变完成后,就可以来实现我们的set和map了。
首先我们来看一下map和set的基本雏形:
map和set类中的成员变量都是一棵红黑树,其中GetCompareValue就是上面所说的仿函数。
对于map和set的插入,我们直接调用_tree红黑树的插入即可。
namespace my_blog_my_set
{
template<class T>
class blog_my_set
{
public:
//获取需要比较的值
struct GetCompareValue//GCV仿函数
{
const T operator()(const T& data)
{
return data;
}
};
bool insert(const T& data)
{
return _tree.insert(data);
}
private:
//成员变量
blog_RBTree::RBTree<T, GetCompareValue> _tree;
};
}
namespace my_blog_my_map
{
template<class Key , class T>
class blog_my_map
{
public:
//获取需要比较的值
struct GetCompareValue//GCV仿函数
{
const Key operator()(const pair<Key,T>& data)
{
return data.first;
}
};
bool insert(const pair<Key,T>& data)
{
return _tree.insert(data);
}
private:
//成员变量
blog_RBTree::RBTree<pair<Key, T>, GetCompareValue> _tree;
};
}
3.迭代器的实现
当我们的插入完成后,就可以来实现迭代器功能了,对于迭代器的实现,其实不是实现map和set的迭代器,而是实现红黑树的迭代器,这样我们就可以在map和set中去调用红黑树的迭代了来完成复用。
对于红黑树的迭代器来说,其实迭代器就是一个类,这个类中的成员变量是一个结点的指针,我们在这个类中通过重载一系列运算符来实现它的的迭代器。
迭代器的基本雏形
在实现迭代器之前,我们先来实现一下迭代器的基本雏形,来看看它的大致结构。
//红黑树的迭代器
template<class T>
struct RBTreeIterator
{
typedef TreeNode<T> Node;
typedef RBTreeIterator Self;
//构造函数
RBTreeIterator(Node* tmp)
:_node(tmp)
{}
//重载*
T& operator*()
{
return _node->_data;
}
//重载->
T* operator->()
{
return &_node->_data;
}
//成员变量
Node* _node;
};
通过上面的代码,我们可以知道红黑树的迭代器中,就只有一个结点的指针的成员变量,同时,我还实现了比较常用的*运算符和->运算符,我的迭代器雏形就基本完成了。接下来完成剩下的运算符重载。
operator!=
对于重载!=来说,只要比较两个对象中的_node是否相等即可。
bool operator!=(const Self& tmp)
{
if (_node != tmp._node)
{
return true;
}
else
{
return false;
}
}
operator++
对于重载++来说,就是去实现树的一种非递归遍历,而这种非递归遍历不是借助于栈的,且这种非递归遍历需要有parent指针才能做到,首先我们知道,通过迭代器++,可以使迭代器移动到下一个中序遍历顺序的下一个位置,那具体怎么做呢,我们来看下图。
Self operator++()
{
Node* cur = _node;
if (cur->_right != nullptr)
{
cur = cur->_right;
while (cur->_left != nullptr)
{
cur = cur->_left;
}
_node = cur;
}
else
{
Node* cur_parent = cur->_parent;
while (cur_parent != nullptr && cur_parent->_right == cur)
{
cur = cur_parent;
cur_parent = cur->_parent;
}
_node = cur_parent;
}
return *this;
}
这个时候,我们的迭代器的基本功能就已经实现完成了, 接下来可以继续编写我们的set和map类的其他成员函数了。
4.insert返回值的改变
当我们的迭代器实现后,接下来要改变insert函数的返回值,为什么,在上面我们实现的insert函数中,返回值是一个bool类型,而通过查C++手册我们发现,insert的返回值并不是简单的bool中,而是一个pair,其中这个pair中有两个参数,一个是bool,一个是iterator。
对于这部分的改变,我们只需要改变红黑树的insert,然后再改变一下map和set返回值即可,红黑树insert改变后如下。
//插入结点
pair<iterator,bool> insert(const T& data)
{
GCV gcv;//仿函数变量
//如果树为NULL,则直接将新结点给到_root
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
iterator it(_root);
return make_pair(it, true);
}
Node* cur = _root;
Node* cur_parent = nullptr;
while (cur != nullptr)
{
if (gcv(data) > gcv(cur->_data))
{
cur_parent = cur;
cur = cur->_right;
}
else if (gcv(data) < gcv(cur->_data))
{
cur_parent = cur;
cur = cur->_left;
}
else//说明该值已经存在,不进行插入
{
iterator it(cur);
return make_pair(it, false);
}
}
//将新结点插入
cur = new Node(data);
if (gcv(cur_parent->_data) > gcv(data))
{
cur_parent->_left = cur;
cur->_parent = cur_parent;
}
else
{
cur_parent->_right = cur;
cur->_parent = cur_parent;
}
Node* ret = cur;//保存插入新结点的位置
//调整结点代码
while (cur_parent != nullptr && cur_parent->_col == RED)
{
Node* grandparent = cur_parent->_parent;
if (grandparent->_left == cur_parent)//正方向
{
Node* uncle = grandparent->_right;
if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
cur_parent = cur->_parent;
}
else//情况二和情况三
{
//这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
if (cur_parent->_right == cur)//这种情况就是情况三
{
//先进行一个左单旋
RotateL(cur_parent);
swap(cur, cur_parent);
}
//代码走到这里就一定是情况二了
RotateR(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
else if (grandparent->_right == cur_parent)//反方向
{
Node* uncle = grandparent->_left;
if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
cur_parent = cur->_parent;
}
else//反方向的情况二和情况三
{
if (cur_parent->_left == cur)
{
RotateR(cur_parent);
swap(cur, cur_parent);
}
RotateL(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
}
_root->_col = BLACK;
iterator it(ret);
return make_pair(it, true);
}
4.begin和end函数的实现
在上面,我们已经成功的实现了红黑树的迭代器,接下来就可以来实现map和set中的begin和end的成员函数了,对于实现begin和end函数来说,我们是去实现红黑树的begin和end函数,再在map和set中去调用红黑树中的begin和end的函数。
//正向begin迭代器 去找最左结点
iterator begin()
{
Node* tmp = GetRoot();
while (tmp->_left != nullptr)
{
tmp = tmp->_left;
}
return iterator(tmp);
}
//正向end迭代器
iterator end()
{
return iterator(nullptr);
}
实现完了红黑树的begin和end函数,我们接下来在map和set中去调用这两个函数即可。
5.operator[]的实现
在迭代器部分完成后,接下来我们来实现一下operator[],注意,这个方法只有map有,set是没有的!!!
在实现operator[]之前,我们首先要知道operator[]是怎么用的,干什么的。
首先我们来看看operator[]的用法:operator["abc"]=222;
如上面这个用法中,我们可以分成两部分来看:
①operator["abc"]:去map中找到Key值为abc的结点,找到后返回其Value的引用。
②=222:将上面这个Value的值赋值为222。
但是我们知道,operator[]还有另一种用法:operator["abc"],这种用法就是没有给Value赋值到,这个时候,会默认给这个类型的缺省值。
知道了operator[]的用法后,我们就可以来实现了,其实operator[]的实现是通过insert函数来实现的。
//重载operator[]
T& operator[](const Key& tmp)
{
pair<iterator, bool> it = insert(make_pair(tmp, T()));
return it.first->second;
}
当做到这里,map和set的模拟实现中的比较重要的部分就已经完成了。
三.所有源代码
blog_my_set.h
#pragma once
#include"blog_RBTree.h"
using namespace blog_RBTree;
namespace my_blog_my_set
{
template<class T>
class blog_my_set
{
public:
//获取需要比较的值
struct GetCompareValue
{
const T operator()(const T& data)
{
return data;
}
};
typedef typename blog_RBTree::RBTree<T, GetCompareValue>::iterator iterator;
//插入
pair<iterator,bool> insert(const T& data)
{
return _tree.insert(data);
}
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
private:
//成员变量
blog_RBTree::RBTree<T, GetCompareValue> _tree;
};
void Test1()
{
blog_my_set<int> s;
s.insert(10);
s.insert(12);
s.insert(22);
s.insert(19);
blog_my_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << endl;
++it;
}
}
}
blog_my_map.h
#pragma once
#include"blog_RBTree.h"
using namespace blog_RBTree;
namespace my_blog_my_map
{
template<class Key , class T>
class blog_my_map
{
public:
//获取需要比较的值
struct GetCompareValue
{
const Key operator()(const pair<Key,T>& data)
{
return data.first;
}
};
typedef typename blog_RBTree::RBTree<pair<Key,T>, GetCompareValue>::iterator iterator;
iterator begin()
{
return _tree.begin();
}
iterator end()
{
return _tree.end();
}
//插入
pair<iterator, bool> insert(const pair<Key,T>& data)
{
return _tree.insert(data);
}
//重载operator[]
T& operator[](const Key& tmp)
{
pair<iterator, bool> it = insert(make_pair(tmp, T()));
return it.first->second;
}
private:
//成员变量
blog_RBTree::RBTree<pair<Key, T>, GetCompareValue> _tree;
};
void Test1()
{
blog_my_map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(56, 56));
m.insert(make_pair(45, 45));
m.insert(make_pair(8, 8));
m[100];
m[200] = 999;
blog_my_map<int,int>::iterator it = m.begin();
while (it != m.end())
{
cout << (*it).first << ":" << (*it).second << endl;
++it;
}
}
}
blog_RBTree.h
#pragma once
#include<iostream>
#include<time.h>
using namespace std;
namespace blog_RBTree
{
enum Color
{
BLACK,
RED
};
template<class T>
struct TreeNode
{
//成员变量
T _data;//数据
TreeNode<T>* _left;
TreeNode<T>* _right;
TreeNode<T>* _parent;
Color _col;//保存结点的颜色
//构造函数
TreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)//每生成一个新结点,都将结点的颜色默认给红色,至于为什么,后面会解释
{}
};
//红黑树的迭代器
template<class T>
struct RBTreeIterator
{
typedef TreeNode<T> Node;
typedef RBTreeIterator Self;
//构造函数
RBTreeIterator(Node* tmp)
:_node(tmp)
{}
//重载*
T& operator*()
{
return _node->_data;
}
//重载->
T* operator->()
{
return &_node->_data;
}
//迭代器++
Self operator++()
{
Node* cur = _node;
if (cur->_right != nullptr)
{
cur = cur->_right;
while (cur->_left != nullptr)
{
cur = cur->_left;
}
_node = cur;
}
else
{
Node* cur_parent = cur->_parent;
while (cur_parent != nullptr && cur_parent->_right == cur)
{
cur = cur_parent;
cur_parent = cur->_parent;
}
_node = cur_parent;
}
return *this;
}
bool operator!=(const Self& tmp)
{
if (_node != tmp._node)
{
return true;
}
else
{
return false;
}
}
//成员变量
Node* _node;
};
template<class T, class GCV>
class RBTree
{
public:
typedef TreeNode<T> Node;
typedef RBTreeIterator<T> iterator;
public:
//正向begin迭代器
iterator begin()
{
Node* tmp = GetRoot();
while (tmp->_left != nullptr)
{
tmp = tmp->_left;
}
return iterator(tmp);
}
//正向end迭代器
iterator end()
{
return iterator(nullptr);
}
//构造函数
RBTree()
:_root(nullptr)//给根结点一个nullptr
{}
//插入结点
pair<iterator,bool> insert(const T& data)
{
GCV gcv;//仿函数变量
//如果树为NULL,则直接将新结点给到_root
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;//把新结点给_root后,要记得把颜色给位BLACK
iterator it(_root);
return make_pair(it, true);
}
Node* cur = _root;
Node* cur_parent = nullptr;
while (cur != nullptr)
{
if (gcv(data) > gcv(cur->_data))
{
cur_parent = cur;
cur = cur->_right;
}
else if (gcv(data) < gcv(cur->_data))
{
cur_parent = cur;
cur = cur->_left;
}
else//说明该值已经存在,不进行插入
{
iterator it(cur);
return make_pair(it, false);
}
}
//将新结点插入
cur = new Node(data);
if (gcv(cur_parent->_data) > gcv(data))
{
cur_parent->_left = cur;
cur->_parent = cur_parent;
}
else
{
cur_parent->_right = cur;
cur->_parent = cur_parent;
}
Node* ret = cur;//保存插入新结点的位置
//调整结点代码
while (cur_parent != nullptr && cur_parent->_col == RED)
{
Node* grandparent = cur_parent->_parent;
if (grandparent->_left == cur_parent)//正方向
{
Node* uncle = grandparent->_right;
if (uncle != nullptr && uncle->_col == RED)//情况一,uncle存在且为红
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
cur_parent = cur->_parent;
}
else//情况二和情况三
{
//这里情况三经过第一次旋转后可以变成情况二,所以可以先判断是否是情况三
if (cur_parent->_right == cur)//这种情况就是情况三
{
//先进行一个左单旋
RotateL(cur_parent);
swap(cur, cur_parent);
}
//代码走到这里就一定是情况二了
RotateR(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
else if (grandparent->_right == cur_parent)//反方向
{
Node* uncle = grandparent->_left;
if (uncle != nullptr && uncle->_col == RED)//反方向的情况一
{
cur_parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
cur_parent = cur->_parent;
}
else//反方向的情况二和情况三
{
if (cur_parent->_left == cur)
{
RotateR(cur_parent);
swap(cur, cur_parent);
}
RotateL(grandparent);
cur_parent->_col = BLACK;
grandparent->_col = RED;
break;
}
}
}
_root->_col = BLACK;
iterator it(ret);
return make_pair(it, true);
}
//获取根结点
Node* GetRoot()
{
return _root;
}
private:
//左单旋
void RotateL(Node* cur_parent)
{
GCV gcv;
Node* cur = cur_parent->_right;
Node* cur_left = cur->_left;
//改变指针的链接关系
cur_parent->_right = cur_left;
if (cur_left != nullptr)
{
cur_left->_parent = cur_parent;
}
cur->_left = cur_parent;
Node* cur_parent_parent = cur_parent->_parent;
cur_parent->_parent = cur;
//旋转完成后要判断cur_parent是否为根
if (cur_parent_parent != nullptr)//说明cur_parent不是根
{
if (gcv(cur_parent_parent->_data) < gcv(cur_parent->_data))
{
cur_parent_parent->_right = cur;
cur->_parent = cur_parent_parent;
}
else
{
cur_parent_parent->_left = cur;
cur->_parent = cur_parent_parent;
}
}
else//说明cur_parent是根
{
_root = cur;
cur->_parent = nullptr;
}
}
//右单旋
void RotateR(Node* cur_parent)
{
GCV gcv;
Node* cur = cur_parent->_left;
Node* cur_right = cur->_right;
cur_parent->_left = cur_right;
if (cur_right != nullptr)
{
cur_right->_parent = cur_parent;
}
cur->_right = cur_parent;
Node* cur_parent_parent = cur_parent->_parent;
cur_parent->_parent = cur;
if (cur_parent_parent != nullptr)
{
if (gcv(cur_parent_parent->_data) > gcv(cur_parent->_data))
{
cur_parent_parent->_left = cur;
cur->_parent = cur_parent_parent;
}
else
{
cur_parent_parent->_right = cur;
cur->_parent = cur_parent_parent;
}
}
else
{
_root = cur;
cur->_parent = nullptr;
}
}
private:
Node* _root;
};
}
test.cpp
#include"blog_my_set.h"
#include"blog_my_map.h"
int main()
{
my_blog_my_set::Test1();
my_blog_my_map::Test1();
return 0;
}
原文地址:https://blog.csdn.net/EWIAW_ilove/article/details/140217505
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!