set与map的详细封装步骤

一.set与map在STL中的源码

二.修改红黑树

1.插入与查找时的比较方式

2.插入时的返回值

3.补充成员函数

三.封装set与map

1.迭代器的实现

2.函数接口

3.map中的operator[]

四.完整代码

set.h

map.h

RBTree.h

一.set与map在STL中的源码

想要简单实现set与map 需要我们稍微理解其底层代码。以下是简化部分

set：

template <class Key, class Compare = less<Key>, class Alloc = alloc>
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, identity<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing set//·····
}

map：

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;typedef Compare key_compare;//·····private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing map//·····
}

从两者私有部分不难看出，两者的底层都使用了红黑树。但一棵红黑树只能为K-V模型或K模型，那是如何同时满足map的K-V模型和set的K模型的呢？

不难看出，set与map虽然共用了一颗红黑树，但传入值的方式不一样

set传入的为<K，K>， map传入的是<K, pair<const K, V> >

关于两类模板参数，第一个K方便find和erase接口，第二个则决定我们的红黑树是那种模型，那怎样将两种模型泛化到一起呢？

由于用户只能从上层调用接口，我们在底层添加模板参数T，set对于T传入K，map对于T传入

pari<const K, V>。具体如下

set:

template<class K>
class set
{public:private:RBTree<K, const K, SetKeyOfT> _t;
};

map:

template<class K, class V>
class map
{public:private:// key不能修改（第一个k为什么不加const？//第一个K 只用于删除和查找， 外层修改不到。RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

RBTree:

enum Colour
{RED,   //0BLACK  //1
};//RBTree树节点
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){ }
};template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node;public:private:Node* _root = nullptr;
};

二.修改红黑树

1.插入与查找时的比较方式

当我们插入元素时，set插入的元素为K，比较大小时可以直接比较，map插入的元素为pair<K,V>，在C++中pair直接比较则会首先按照first的大小比较，first相同时再按照second大小比较，这显然不是我们期望的只用K关键字比较。那么如何才能使用一种统一的方式解决这个问题呢？

采用仿函数

在map和set类中添加各自的仿函数，其功能是拿到各自的Key，便于红黑树的比较。

set：

template<class K>
class set
{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:private:RBTree<K, const K, SetKeyOfT> _t;
};

map：

template<class K, class V>
class map
{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:private:// key不能修改（第一个k为什么不加const？//第一个K 只用于删除和查找， 外层修改不到。RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

RBTree：模板中添加仿函数

enum Colour
{RED,   //0BLACK  //1
};//RBTree树节点
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){ }
};template<class K, class T，class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;public:private:Node* _root = nullptr;
};

2.插入时的返回值

在C++源码中， set与map插入的返回值都是pair类型：其意为如果插入成功与否，都返回一个pair类型，如果成功则返回插入位置的迭代器与true，如果失败则返回重复元素位置的迭代器与false。所以，我们应修改Insert函数的返回值。

完善后的Insert函数(内含的迭代器部分在下面会讲，先关注返回值与比较部分即可)：

//插入成功--->返回插入位置和true
//插入失败--->返回该元素存在的位置和false
pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root), true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){// K// pair<K, V>// kot对象，是用来取T类型的data对象中的keyif (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->_col = RED;//记录cur位置Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}// 别忘记指向父亲cur->_parent = parent;// 往上更新  如果父亲的颜色是黑色就停止while (parent && parent->_col == RED){// 关键看叔叔Node* grandfather = parent->_parent;//如果叔叔在右边if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔存在且为红， 往上变色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上cur = grandfather;parent = cur->_parent;}// 叔叔不存在或者存在且为黑else{if (cur == parent->_left){//     g  //   p   u// c RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// p     u//    cRotateL(parent);RotateR(grandfather);//cur去了g的位置  g去了u的位置cur->_col = BLACK;grandfather->_col = RED;}//根一定是黑色的break;}}else//叔叔在左边{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{//    g// u     p//          cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// u     p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 如果根节点变红了 设回黑_root->_col = BLACK;return make_pair(Iterator(newnode), true);}

3.补充成员函数

在简单实现中，我们需要把必要的默认成员函数补上。

//我们手写了默认成员函数后 编译器不在为我们自动生成// + default 要编译器给我们生成默认构造 运行效率更好
RBTree() = default;//拷贝
RBTree(const RBTree<K, T, KeyOfT>& t)
{//深拷贝_root = _Copy(t._root);
}
//赋值 重载运算符
RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t)
{//t是形参 相当于和副本交换了swap(_root, t._root);return *this;
}~RBTree()
{_Distory(_root);_root = nullptr;
}private://递归式删除void _Distory(Node* root){if (root == nullptr)return;_Distory(root->_left);_Distory(root->_right);delete root;root = nullptr;}Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col;newroot->_left = _Copy(root->_left);if (newroot->_left)newroot->_left->_parent = newroot;newroot->_right = _Copy(root->_right);if (newroot->_right)newroot->_right->_parent = newroot;return newroot;}

三.封装set与map

1.迭代器的实现

对于迭代器，我们要实现begin()、end()、*iterator、iterator->、++iterator、!=这四种常见功能。另外，我们希望从外部访问迭代器，只访问到树节点的数据：set只访问K，map只访问pair<const K， V>，因为用户访问树节点的左右父亲颜色等没有意义。

初始化：用一个树的节点来初始化

begin()与end()：

对于一棵红黑树，其中序遍历时有序的，也就是说我们在用迭代器从begin()访问到end()的过程中也是有序的。基于此，迭代器的begin()指向的位置应当是整棵树中最小的数即最左的节点(图中改为1)。end()作为最大节点的后一个元素，为空即可。

*iterator：对迭代器解引用，应返回对数据的引用

iterator->：引出迭代器的元素，应返回对应数据的地址(编译器会帮我们优化)

++iterator：对于前置++操作，在上图中访问顺序为1-6-8-11-13-15-17-22-25-27

规律为：若一个节点有右子树，则访问其右子树的最左节点；若没有右子树，则倒着往上寻找一个孩子为父亲左的一个祖先。

!=：直接比较两个值相不相等即可。

在树外新建一个类进行实现，当然也可以嵌在树中当内部类。

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& s){return _node != s._node;}//前置++Self& operator++(){//++操作迭代器指向的元素一定是按顺序的if (_node->_right){//如果有右树， 下一个节点为右数的最左边Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//没有右树，倒着在祖先里找，找孩子是父亲左的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};Iterator Begin()
{//空不空无所谓Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}Iterator End()
{return Iterator(nullptr);
}

2.函数接口

在我们map与set里面对迭代器的接口封装以下即可。

set：

template<class K>
class set
{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct SetKeyOfT{const K& operator()(const K& key){return key;}};
public://消除二义性 让编译器知道你要给一个类型取别名 而不是 定义一个变量typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:RBTree<K, const K, SetKeyOfT> _t;
};

map：

template<class K, class V>
class map
{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;	iterator begin(){return _t.Begin();}iterator end(){return _t.End();}private:// key不能修改（第一个k为什么不加const？//第一个K 只用于删除和查找， 外层修改不到。RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

3.map中的operator[]

对于map，其支持方括号下标访问。

形如：

map<string, int> mp;

mp[”x”] = 1；

其原理为若有”x“，则修改其对应值为1，若无“x”，则插入”x“，值为1。

所以重载[]时应进行插入，用pair类型接收。

V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert({key,V()});//map迭代器是一个节点的指针 "->"我们重载过 得到pair类型 pair<const K, V> 返回second；return ret.first->second;
}

四.完整代码

最后补充const迭代器以及一些细节，代码里有注释。附测试。

set.h

#pragma once//template <class Key, class Compare = less<Key>, class Alloc = alloc>
//class set {
//public:
//    typedef Key key_type;
//    typedef Key value_type;
//private:
//    typedef rb_tree<key_type, value_type,
//        identity<value_type>, key_compare, Alloc> rep_type;
//    rep_type t;  // red-black tree representing set
//}// 抓重点
// 化繁为简，只关注跟抓重点部分有关系的，其他通通不关注namespace Xiang
{template<class K>class set{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://消除二义性 让编译器知道你要给一个类型取别名 而不是 定义一个变量typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void PrintSet(const set<int>& s){for (auto e : s){cout << e << endl;}}void test_set(){set<int> s;s.insert(4);s.insert(2);s.insert(5);s.insert(15);s.insert(7);s.insert(1);s.insert(5);s.insert(7);PrintSet(s);set<int>::iterator it = s.begin();while (it != s.end()){//*it += 5;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;set<int> copy = s;for (auto e : copy){cout << e << " ";}cout << endl;//cout << copy._t.IsBalance() << endl;}
}

map.h

#pragma once
//template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
//class map {
//public:
//    typedef Key key_type;
//    typedef pair<const Key, T> value_type;
//
//private:
//    typedef rb_tree<key_type, value_type,
//        select1st<value_type>, key_compare, Alloc> rep_type;
//    rep_type t;  // red-black tree representing map
//};namespace Xiang
{template<class K, class V>class map{//仿函数  因为map中红黑树的T 为pair， set中为K， 为了泛型编程//我们使用仿函数对map和set进行统一处理struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://消除二义性 让编译器知道你要给一个类型取别名 而不是 定义一个变量typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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();}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}//find 返回迭代器iterator find(const K& key){return _t.Find(key);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert({key,V()});//map迭代器是一个节点的指针 "->"我们重载过 得到pair类型 pair<const K, V> 返回second；return ret.first->second;}private:// key不能修改（第一个k为什么不加const？//第一个K 只用于删除和查找， 外层修改不到。RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map1(){map<string, int> m;m.insert({ "乐",1 });m.insert({ "通",1 });m.insert({ "给",1 });m.insert({ "哦",3 });cout << m["乐"] << endl << "有乐" << endl;map<string, int>::iterator it = m.begin();while (it != m.end()){//it->first += 'x';it->second += 1;//cout << it.operator->()->first << ":" << it->second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_map2(){string arr[] = { "a", "", "a", "", "d", "c", "","他怕", "李", "好", "哦","给","888", "达瓦","h" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

RBTree.h

#pragma onceenum Colour
{RED,   //0BLACK  //1
};//RBTree树节点
template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data)// 新插入节点默认红的//因为插入红节点可能违反规则三，但插入黑节点一定违反规则四, _col(RED){ }
};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& s){return _node != s._node;}//前置++Self& operator++(){//++操作迭代器指向的元素一定是按顺序的if (_node->_right){//如果有右树， 下一个节点为右数的最左边Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else{//没有右树，倒着在祖先里找，找孩子是父亲左的祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T, T&, T*> Iterator;typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;//我们手写了默认成员函数后 编译器不在为我们自动生成// + default 要编译器给我们生成默认构造 运行效率更好RBTree() = default; //拷贝RBTree(const RBTree<K, T, KeyOfT>& t){//深拷贝_root = _Copy(t._root);}//赋值 重载运算符RBTree<K, T, KeyOfT>& operator=(const RBTree<K, T, KeyOfT> t){//t是形参 相当于和副本交换了swap(_root, t._root);return *this;}~RBTree(){_Distory(_root);_root = nullptr;}//begin 为最左节点   end为空节点Iterator Begin(){//空不空无所谓Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}Iterator End(){return Iterator(nullptr);}ConstIterator End() const{return ConstIterator(nullptr);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (KeyOfT(cur->_data) < key){cur = cur->_right;}else if (KeyOfT(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur);}}return End();}//插入成功--->返回插入位置和true//插入失败--->返回该元素存在的位置和falsepair<Iterator, bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root), true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){// K// pair<K, V>// kot对象，是用来取T类型的data对象中的keyif (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->_col = RED;//记录cur位置Node* newnode = cur;if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}// 别忘记指向父亲cur->_parent = parent;// 往上更新  如果父亲的颜色是黑色就停止while (parent && parent->_col == RED){// 关键看叔叔Node* grandfather = parent->_parent;//如果叔叔在右边if (parent == grandfather->_left){Node* uncle = grandfather->_right;//叔叔存在且为红， 往上变色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上cur = grandfather;parent = cur->_parent;}// 叔叔不存在或者存在且为黑else{if (cur == parent->_left){//     g  //   p   u// c RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// p     u//    cRotateL(parent);RotateR(grandfather);//cur去了g的位置  g去了u的位置cur->_col = BLACK;grandfather->_col = RED;}//根一定是黑色的break;}}else//叔叔在左边{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else // 叔叔不存在，或者存在且为黑{//    g// u     p//          cif (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//    g// u     p//    cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 如果根节点变红了 设回黑_root->_col = BLACK;return make_pair(Iterator(newnode), true);}//右旋void RotateR(Node* parent){// 要更改六条边Node* subL = parent->_left;Node* subLR = subL->_right;// 先处理parent和SubLRparent->_left = subLR;if (subLR)subLR->_parent = parent;//再处理parent和 subl//因为 后面需要把 parent的parent和subl链接//需要先保存parent的parentsubL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;//处理 subl的 父节点if (parent == _root){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}//左旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root->_col == RED){return false;}int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){++refNum;}cur = cur->_left;}return _Check(_root, 0, refNum);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}private://递归式删除void _Distory(Node* root){if (root == nullptr)return;_Distory(root->_left);_Distory(root->_right);delete root;root = nullptr;}Node* _Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_data);newroot->_col = root->_col;newroot->_left = _Copy(root->_left);if (newroot->_left)newroot->_left->_parent = newroot;newroot->_right = _Copy(root->_right);if (newroot->_right)newroot->_right->_parent = newroot;return newroot;}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;return max(_Height(root->_left), _Height(root->_right)) + 1;}bool _Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return _Check(root->_left, blackNum, refNum)&& _Check(root->_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};