map和set的封装

1.红黑树相关迭代器的实现

1.1operator++

在自增/减时要满足红黑树中序遍历的顺序：左子树、根、右子树（符合递增或递减）
++时：
右子树存在，找到右子树中的最左节点
右子树不存在，向上层遍历，直到当前节点是其父节点的左节点，取父节点（左、中）

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 = parent->_parent;}_node = parent;}return *this;
}

–时同理：
左子树存在，找到左子树中的最右节点
左子树不存在，找到孩子是父亲右节点的祖先节点

1.2operator[]

[k]返回v，map是kv模型，可以实现[],set不能,这里的operator[]在map的封装中实现。

pair<iterator, bool> insert(const pair<K, V>& kv)
{return _t.Insert(kv);
}V& operator[](const K& key)
{pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;
}

1.3其他接口

Ref operator*()
{return _node->_data;
}Ptr operator->()
{return &_node->_data;
}bool operator!=(const Self& s)
{return _node != s._node;
}Iterator Begin()
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);
}Iterator End()
{return Iterator(nullptr);
}ConstIterator End() const
{return ConstIterator(nullptr);
}ConstIterator Begin() const
{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);
}Iterator Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return Iterator(cur);}}return End();
}
// 20:10
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);Node* newnode = cur;cur->_col = RED; // 新增节点给红色if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = 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//      c RotateL(parent);RotateR(grandfather);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);
}

2.KeyOfT

map和set的底层都是红黑树，但map是kv模型，而set是k模型。在取key值时，set能直接取，但map要取kv.first。这时候我们可以用一个KeyOfT的类去获得map和set里面的k值。

在底层红黑树取k值时分别通过set和map中KetOfT的仿函数取到对应k值。

3.map 封装

#pragma once#include"RBT.h"
#include<iostream>
using namespace std;
namespace bit
{template<class K, class V>class Mymap{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, const K, MapKeyOfT>::ConstIterator const_iterator;const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map(){Mymap<string, int> m;m.insert({ "苹果",1 });m.insert({ "菠萝",5 });m.insert({ "香蕉",2 });m.insert({ "西瓜",3 });Mymap<string, int>::iterator it = m.begin();while (it != m.end()){it->second += 1;//cout << it.operator->()->first << ":" << it->second << endl;cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}

4.set封装

#pragma once#include"RBT.h"
#include<iostream>
using namespace std;namespace bit
{template<class K>class 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;const_iterator begin() const{return _t.Begin();}const_iterator end() const{return _t.End();}iterator begin(){return _t.Begin();}iterator end(){return _t.End();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const K& key){return _t.Insert(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;}
}

5.测试

#include"mymap.h"
#include"myset.h"
int main()
{bit::test_map();bit::test_set();return 0;
}

6.源码

6.1RBT.h

#pragma once
#include<vector>
#include<iostream>
using namespace std;
enum Colour
{RED,BLACK
};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 = parent->_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;RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}// t2 = t1RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End(){return Iterator(nullptr);}ConstIterator End() const{return ConstIterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}Iterator Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return Iterator(cur);}}return End();}// 20:10pair<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);Node* newnode = cur;cur->_col = RED; // 新增节点给红色if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = 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//      c RotateL(parent);RotateR(grandfather);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->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = 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->_right == parent){ppNode->_right = subR;}else{ppNode->_left = 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);}private: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;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}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;//size_t _size = 0;
};