【C++】set与map模拟实现
目录
一、关联式容器
二、set与map
（一）set
（二）map
三、底层原理
四、红黑树迭代器
（一）红黑树的begin() 与 end()
（二）红黑树迭代器的++
（三）红黑树迭代器的--
五、红黑树迭代器的封装
（一）set的迭代器
（二）map的迭代器
六、set与map的模拟实现
（一）RBTree
（二）Set
（三）Map
一、关联式容器
vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
而关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
关联式容器有两种，一种是map、set、multimap、multiset采用树形结构，他们的底层都是红黑树，另一种是哈希结构。
SGI-STL中关于键值对的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
二、set与map
（一）set
1、set是关联式容器，它表面上只存放value，实际底层中存放的是由<value,value>组成的键值对。
2、set调用find将采用中序遍历，可以用于排序+去重。
3、为了保证元素的唯一性，set中的元素均为const，所以并不能对元素进行修改，但可以进行插入删除。
使用示例：
#include <set>
void TestSet()
{
// 用数组array中的元素构造set
int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
set<int> s(array, array+sizeof(array)/sizeof(array));
cout << s.size() << endl;
// 正向打印set中的元素，从打印结果中可以看出：set可去重
for (auto& e : s)
cout << e << " ";
cout << endl;
// 使用迭代器逆向打印set中的元素
for (auto it = s.rbegin(); it != s.rend(); ++it)
cout << *it << " ";
cout << endl;
// set中值为3的元素出现了几次
cout << s.count(3) << endl;
}（二）map
1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair:
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4.map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
#include <string>
#include <map>
void TestMap()
{
map<string, string> m;
// 向map中插入元素的方式：
// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
m.insert(pair<string, string>("peach", "桃子"));
// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
m.insert(make_pair("banan", "香蕉"));
// 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引
用结果，
m["apple"] = "苹果";
cout << m.size() << endl;
// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
for (auto& e : m)
cout << e.first << "--->" << e.second << endl;
cout << endl;
// map中的键值对key一定是唯一的，如果key存在将插入失败
auto ret = m.insert(make_pair("peach", "桃色"));
if (ret.second)
cout << "<peach, 桃色>不在map中, 已经插入" << endl;
else
cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
<< ret.first->second <<" 插入失败"<< endl;
// 删除key为"apple"的元素
m.erase("apple");
if (1 == m.count("apple"))
cout << "apple还在" << endl;
else
cout << "apple被吃了" << endl;
}三、底层原理
红黑树详见：【数据结构】红黑树-CSDN博客
set 和 map 都是底层使用红黑树实现的，将红黑树封装为目标容器。巧妙的是，底层红黑树代码只有一份，但可以通过传入不同的模板参数分别实现set 与 map。
通过上图我们可以得到，set是在传入参数给红黑树是模板为<key, key>的形式，而map是在传入参数给红黑树是模板为<key, pair<key, val>>的形式。红黑树在接收参数时，接收set时节点存入的是key形式的数据，而接收map时节点存入的是pair<key, val>形式的数据。因此，set和map中底层虽然都是红黑树，但这两种数据结构中的红黑树实例化类型并不相同。
这里就出现了一个问题，也就是红黑树底层并不知道数据内存的是单个key值，还是一个<key, val>键值对，那么如果使用该数据呢（例如在插入节点时需要按照key值大小来寻找插入位置）。实际上是可以通过仿函数来实现以上问题。
template <class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)//传入节点的值
{
return key;//返回key
}
};
private:
RBTree<K, K, SetKeyOfT> _t;
};
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)//传入节点的值
{
return kv.first;//返回kv.first
}
};
private:
RBTree<const K, pair<K,V>, MapKeyOfT> _t;
};
//利用模板确定传入对象是set还是map
template <class K, class T,class KeyOfT>
class RBTree//红黑树
{};本文通过增加传入模板参数将该仿函数传入给底层的红黑树，红黑树通过调用该仿函数来取得数据中的key值。
四、红黑树迭代器
STL库中红黑树底层实际是有个头节点，而本文采用的是无头结点的常规红黑树仿写红黑树的迭代器。下面是红黑树中迭代器的封装。
typedef RBTreeIterator<V, V&, V*> iterator;
typedef RBTreeIterator<V, const V&, const V*> const_iterator;（一）红黑树的begin() 与 end()
本次将 begin() 返回最左下节点生成的迭代器，而 end() 返回值为 nullptr 的迭代器。
（二）红黑树迭代器的++
针对于set 与 map 的迭代器的++，是变为中序遍历中该节点的后继节点。
因此针对红黑树的++也得满足上述条件：
1、如果当前节点的右孩子不为空，则迭代器++至该右子树中最小的的节点；
2、如果当前节点的右孩子为空，迭代器++至子树为上层节点左子树的祖先节点。
Self& operator++()
{
//右子树不为空
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
//右子树为空
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}（三）红黑树迭代器的--
针对于set 与 map 的迭代器的--，是变为中序遍历中该节点的前驱节点。
因此针对红黑树的--也得满足上述条件：
1、如果当前节点的左孩子不为空，则迭代器--至该左子树中最大的的节点；
2、如果当前节点的左孩子为空，迭代器--至子树为上层节点右子树的祖先节点。
Self& operator--()
{
//左子树不为空
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
//左子树为空
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}五、红黑树迭代器的封装
（一）set的迭代器
对于set，它的key都是不能改的。也就是无论是普通迭代器还是const 迭代器，我们统一使用红黑树的const迭代器进行封装。
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}针对于上述代码，底层红黑树也必须提供对于const迭代器的 begin() 与 end()。
（二）map的迭代器
对于map，它的key同样不能修改，但是其value是可以修改的。
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}因此封装红黑树迭代器的时候，无论普通迭代器还是const迭代器都需要在pair键值对中对key加上const修饰。
六、set与map的模拟实现
（一）RBTree
#pragma once
#pragma once
#include <iostream>
#include <cassert>
using namespace std;
enum Color
{
red, black
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _color;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _color(red)
{}
};
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)
{}
RBTreeIterator(const iterator& it)
:_node(it._node)
{}
// 请完善迭代器的++操作，让迭代器可以移动
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && parent->_left == cur)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 请完善下面两个操作，让迭代器可以像指针一样操作
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
// 请完善下面两个操作，让迭代器能够支持比较
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
template<class K, class V, class KeyOfVal>
class RBTree
{
public:
typedef RBTreeNode<V> Node;
typedef RBTreeIterator<V, V&, V*> iterator;
typedef RBTreeIterator<V, const V&, const V*> const_iterator;
RBTree()
:_root(nullptr)
{}
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return const_iterator(left);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
//中序遍历
void Inorder()
{
_Inorder(_root);
}
// 左单旋
void RotateL(Node* pParent)
{
Node* parent = pParent;
Node* pNode = parent->_parent;
Node* subR = parent->_right;
parent->_right = subR->_left;
if (subR->_left)
subR->_left->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if (pNode == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pNode->_left == parent)
{
pNode->_left = subR;
}
else
{
pNode->_right = subR;
}
subR->_parent = pNode;
}
}
// 右单旋
void RotateR(Node* pParent)
{
Node* parent = pParent;
Node* pNode = parent->_parent;
Node* subL = parent->_left;
parent->_left = subL->_right;
if (subL->_right)
subL->_right->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
if (pNode == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pNode->_left == parent)
{
pNode->_left = subL;
}
else
{
pNode->_right = subL;
}
subL->_parent = pNode;
}
}
//插入节点
pair<iterator, bool> Insert(const V& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = black;
return make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfVal kov;
while (cur)
{
if (kov(cur->_data) < kov(data))
{
parent = cur;
cur = cur->_right;
}
else if (kov(cur->_data) > kov(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);
}
}
cur = new Node(data);
Node* ret = cur;
if (kov(parent->_data) < kov(data))
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
while (parent && parent->_color == red)
{
Node* grandparent = parent->_parent;
Node* uncle = nullptr;
if (grandparent == nullptr)
break;
if (parent == grandparent->_left)
uncle = grandparent->_right;
else
uncle = grandparent->_left;
if (uncle && uncle->_color == red)
{
parent->_color = uncle->_color = black;
grandparent->_color = red;
cur = grandparent;
parent = cur->_parent;
}
else
{
if (grandparent->_right == parent && parent->_right == cur)
{
RotateL(grandparent);
parent->_color = black;
grandparent->_color = red;
}
else if (grandparent->_left == parent && parent->_left == cur)
{
RotateR(grandparent);
parent->_color = black;
grandparent->_color = red;
}
else if (grandparent->_right == parent && parent->_left == cur)
{
RotateR(parent);
RotateL(grandparent);
cur->_color = black;
grandparent->_color = red;
}
else if (grandparent->_left == parent && parent->_right == cur)
{
RotateL(parent);
RotateR(grandparent);
cur->_color = black;
grandparent->_color = red;
}
else
assert(false);
break;
}
_root->_color = black;
}
return make_pair(iterator(ret), true);
}
//判断是否为红黑树
bool isRBTree()
{
if (_root->_color == red)
return false;
Node* cur = _root;
int ref = 0;
while (cur)
{
if (cur->_color == black)
++ref;
cur = cur->_left;
}
return check(_root, 0, ref);
}
private:
bool check(Node* t, int num, int ref)
{
if (t == nullptr)
{
if (num != ref)
{
cout << "黑色节点数目异常" << endl;
return false;
}
return true;
}
if (t->_color == red && t->_parent->_color == red)
{
cout << "出现连续红色节点" << endl;
return false;
}
if (t->_color == black)
num++;
return check(t->_left, num, ref) && check(t->_right, num, ref);
}
//中序遍历
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << KeyOfVal()(root->_data) << " ";
_Inorder(root->_right);
}
Node* _root;
};
（二）Set
#pragma once
#include "RBTree.h"
namespace mh
{
template<class K>
class set
{
struct KeyOfVal
{
const K& operator()(const K& data)
{
return data;
}
};
typedef typename RBTree<K, K, KeyOfVal>::const_iterator iterator;
typedef typename RBTree<K, const K, KeyOfVal>::const_iterator const_iterator;
public:
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
pair<typename RBTree<K, K, KeyOfVal>::iterator, bool> ret = _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, KeyOfVal> _t;
};
}（三）Map
#pragma once
#include "RBTree.h"
namespace mh
{
template<class K, class V>
class map
{
struct KeyOfVal
{
const K& operator()(const pair<K, V>&data)
{
return data.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, KeyOfVal>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, KeyOfVal>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return end();
}
pair<iterator, bool> insert(const pair<K, V>& data)
{
return _t.Insert(data);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, KeyOfVal> _t;
};
}