【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）！