目录

一、map/set 的封装

1.1 封装思路

1.2 红黑树节点调整

1.3 map 和 set 的定义

1.4 仿函数 KeyOfValue

1.5 map/set 的插入

二、map/set 迭代器实现

2.1 迭代器的定义

2.2 解引用运算符重载

2.3 成员访问运算符重载

2.4 (不)等于运算符重载

2.5 begin() 与 end()

2.6 ++ 运算符重载

2.7 -- 运算符重载

2.8 [ ]下标访问运算符重载

三、源代码+测试用例

3.1 map/set 

3.2 迭代器

3.3 测试用例

3.4 红黑树

一、map/set 的封装

在实现了红黑树的部分功能后，我们可以便可以将红黑树作为底层结构来封装map 和 set ，其中map是 K-Value 模型 ，而 set 是 Key 模型。

我们接下来将使用模板、仿函数用一棵红黑树实现 map和set。

1.1 封装思路

因为 map 存储的是 pair ，而 set 存储的是 Key ，所以其解决的根本方向就是：

如果是 map，红黑树中就按照 pair 的 K 进行比较，从而插入；

如果是 set，红黑树中就按照 Key 值进行比较，进而插入。

让 map / set 主动传出待比较的数据，红黑树只用根据数据间关系进行插入即可，不用在乎待比较的数据是何种结构。

1.2 红黑树节点调整

上文我们实现的红黑树是按照键值对的方式进行存储的，而接下来我们要同时封装 map/set，故不能直接定死存储的结构，所以我们在此进行修改。

将原来的 kv 模型改为 data 模型，data 即是比较的数据内容。

注意，将 Kv模型改为 data后，插入与查找中比较的代码都要进行更新，稍后会讲解。

1.3 map 和 set 的定义

map 和 set 底层都使用的红黑树，所以我们 map/set的功能就是调用红黑树的成员函数即可。

template
class Map
{
private:RBTree> _t;
};template
class Set
{
private:RBTree _t;
};

因为 Map 有两个模板参数，而 Set 只有一个模板参数。所以当我们使用的一个红黑树实现时，要进行匹配处理。即使 Set 是一个模板参数，在调用红黑树时也要传入两个模板参数。因为第一个模板参数是匹配 Map 满足红黑树的两个模板参数，而第二个模板参数是为了让底层红黑树拿到比较的数据。

为什么 Map 除了传入 pair 外，第一个参数直接传入 K，为什么不能省略？

因为 Find 的存在，map中 Find 函数是直接按 pair 中的 K 进行查找的，所以要额外设置该参数。

1.4 仿函数 KeyOfValue

接下来我们就要将数据取出供红黑树比较了，如果是 map，就按 pair 中的 K去比较，如果是 set，就按 Key 比较。

为此我们可以在 map 和 set 内部定义一个仿函数将其数据取出。

template
class Map
{//Map-keyofvalue 仿函数struct MapKeyOfvalue{const K& operator()(const std::pair& kv){return kv.first;}};
private:RBTree> _t;
};template
class Set
{//Set-keyofvalue 仿函数struct SetKeyOfvalue{const K& operator()(const K& key){return key;}};
private:RBTree _t;
};

然后我们将其仿函数也作为模板，传入红黑树中，对应的，红黑树要添加一个模板参数来接收该仿函数。

改动代码如下：

 改动这些之后，我们便要将红黑树中比较数据大小的地方进行修改

用仿函数将数据取出，然后进行比较：

//根据模板参数创建仿函数
KeyOfvalue kovalue;
if (!_root)
{_root = new Node(data);_root->_col = BLACK;return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{//比较处————进行改动if (kovalue(cur->_data) > kovalue(data)){parent = cur;cur = cur->_left;}//比较处————进行改动else if (kovalue(cur->_data) < kovalue(data)){parent = cur;cur = cur->_right;}else{return false;}
}
//创建新节点，使用data进行构造
cur = new Node(data);
//比较处————进行改动
if (kovalue(parent->_data) > kovalue(data))
{parent->_left = cur;
}
else
{parent->_right = cur;
}
cur->_parent = parent;

这样，红黑树便可以适配 map/set 的插入了。

1.5 map/set 的插入

接下来 map/set 的插入直接套用红黑树的即可。

代码如下：

//map的插入，插入pair
bool insert(const pair& kv)
{return _t.Insert(kv);
}//set的插入，插入key
bool insert(const K& key)
{return _t.Insert(key);
}

接下来进行测试，看我们map/set能否正常的插入数据。

二、map/set 迭代器实现

2.1 迭代器的定义

//			 节点数据	引用/const引用  指针/const指针
template 
struct __RBTreeIterator
{typedef RBTreeNode Node;typedef __RBTreeIterator self;Node* _node;
public:__RBTreeIterator(Node* node):_node(node){}
}

首先，我们要明确，其实 map/set 只是一层套壳，其中的功能都是由红黑树实现后，再封装到map/set中供我们使用，迭代器也不例外。

2.2 解引用运算符重载

解引用即返回该节点的存储的数据，主要用于 set 中，返回该数据的引用。

Ref operator*()
{return _node->_data;
}

2.3 成员访问运算符重载

成员访问操作符即返回该节点的地址，主要用于 map 中，方便访问 pair 中的first以及second。

Ptr operator->()
{return &(_node->_data);
}

2.4 (不)等于运算符重载

bool operator==(const self& s) 
{return _node == s._node;
}bool operator!=(const self& s) 
{return _node != s._node;
}

2.5 begin() 与 end()

迭代器常用成员函数begin()与end()，其中begin()对应红黑树的最左节点，end()对应最后一个节点的下一个节点，即nullptr(为了简化，并未设置哨兵节点实现将其完美实现)

iterator begin()
{Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);
}iterator end()
{return iterator(nullptr);
}

如果 map/set 中想使用红黑树中的迭代器，我们需要在 map/set 中进行声明。

声明如下：

如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
告诉编译器这是一个类型，并不是一个静态变量

//如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
//告诉编译器这是一个类型，并不是一个静态变量
typedef typename RBTree, MapKeyOfvalue>::iterator iterator;

注意：typename受限定符限制，尽量放在public下

2.6 ++ 运算符重载

首先我们需要明确，迭代器++是让当前迭代器指向红黑树中序遍历的下一个节点。

以下图的35节点为例。

• 当迭代器指向 35 时，进行 ++，指向右子树最左节点，即 40。
• 当迭代器指向 40 时，进行 ++，右子树为空，指向父节点，即 45。
• 当迭代器指向 45 时，进行 ++，指向右子树最左节点，即 48。
• 当迭代器指向 48 时，进行 ++，指向未遍历的父节点，即 50。

分析上面的情况，发现迭代器 ++ 始终围绕着右子树是否存在进行。

现在我们将其抽象化，分析其规律。

1. 右子树不为空，进行 ++ 则是指向右子树中序的第一个(最左节点)。
2. 右子树为空，++ 找孩子不是父亲右节点的祖先。

代码实现：

self& operator++()
{//如果右子树存在if (_node->_right){Node* left = _node->_right;//则寻找右子树的最左节点while (left->_left){left = left->_left;}_node = left;}//如果右子树不存在else{//找孩子不是父亲右节点的节点Node* parent = _node->_parent;Node* cur = _node;=while (cur == parent->_right){cur = cur->_parent;parent = parent->_parent;//防止最后一个节点寻找祖先导致程序崩溃if (parent == nullptr){break;}}_node = parent;}return *this;
}

需要注意，当 ++ 到最后一个节点的时候。有可能在寻找非父亲右节点的祖先时，父节点一路走到 nullptr 的情况，如图：

所以在每次 parent 更新时都进行一次判断，即可。

测试：

这里顺序把后置 ++ 的代码实现一下，直接套用前置 ++ 即可。

//迭代器后置++
self operator++(int)
{self it_temp(_node);++(*this);return it_temp;
}

2.7 -- 运算符重载

有了前面++的模拟实现，实现 --就是反着遍历即可。

1. 左子树不为空，进行 -- 则是指向左子树中序的最后一个(最右节点)。
2. 左子树为空，-- 找孩子不是父亲左节点的祖先。

代码如下:

self& operator--()
{//如果左子树存在if (_node->left){//找左子树的最右节点Node* right = _node->_left;while (right->_right){right = right->_right;}_node = rihgt;}//如果左子树不存在else{//找孩子不是父亲左节点的节点Node* parent = _node->parent;Node* cur = _node;while (parent->_left == cur){cur = cur->_parent;parent = parent->_parent;if (parent == nullptr){break;}}_node = parent;}return *this;
}

2.8 [ ]下标访问运算符重载

我们来看 map 的 [ ] 下标访问操作符，其中 [ ]返回的是mapped_type(pair) 类型。

我们便要对 map 中 insert 的返回值做出修改：

 注意，set 中的 insert 也是返回 pair，虽然很反常，但是官方库中确实是这样书写的。

因为只有 set 没有 [ ] 运算符重载，所以我们 set 中不必提供该函数，只用在 map 中提供即可。

首先，我们向 map 中 insert 数据 pair；pair的第一个参数为用户传入的 key 值，第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int，则调用 int的构造函数，如果是 string ，则默认构造 string)。

pair result = insert(make_pair(key, V()));

然后我们返回迭代器指向的 pair 数据中的second。

//result.first取出迭代器，使用->运算符重载取出data地址，访问second并返回
return result.first->second;

完整的函数书写如下：

V& operator[](const K& key)
{pair result = insert(make_pair(key, V()));//如果存在，则插入失败//如果不存在，则插入数据//无论是否存在,都返回 second;return result.first->second;
}

接下来我们要对红黑树的 Insert 的返回值处进行改动，进而契合 map 的 pair 数据类型。改动有三处，这里贴图大家观察即可。

测试：

三、源代码+测试用例

3.1 map/set 

namespace brant
{templateclass Map{public:struct MapKeyOfvalue{const K& operator()(const std::pair& kv){return kv.first;}};//外层要想使用红黑树的iterator，typedef typename RBTree, MapKeyOfvalue>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair insert(const pair& kv){return _t.Insert(kv);}void InOrder(){_t.Inorder();}V& operator[](const K& key){pair result = insert(make_pair(key, V()));return result.first->second;}private:RBTree, MapKeyOfvalue> _t;};templateclass Set{struct SetKeyOfvalue{const K& operator()(const K& key){return key;}};public:typedef typename RBTree::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair insert(const K& key){return _t.Insert(key);}void InOrder(){_t.Inorder();}private:RBTree _t;};
}

3.2 迭代器

enum Color { RED, BLACK };
template 
struct RBTreeNode
{RBTreeNode* _left;	RBTreeNode* _right;	RBTreeNode* _parent;	T _data;Color _col;					RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)              {}
};//			 节点数据	引用/const引用  指针/const指针
template 
struct __RBTreeIterator
{typedef RBTreeNode Node;typedef __RBTreeIterator self;typedef __RBTreeIterator iterator;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}//map常使用operator ->  返回地址，然后通过——> 访问Ptr operator->(){return &(_node->_data);}bool operator==(const self& s)  {return _node == s._node;}bool operator!=(const self& s) {return _node != s._node;}iterator begin(){Node* left = _node;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}self& operator++(){//如果右子树存在if (_node->_right){Node* left = _node->_right;//则寻找右子树的最左节点while (left->_left){left = left->_left;}_node = left;}//如果右子树不存在else{//找孩子不是父亲右的节点Node* parent = _node->_parent;Node* cur = _node;while (cur == parent->_right){cur = cur->_parent;parent = parent->_parent;//防止最后一个节点寻找祖先导致程序崩溃if (parent == nullptr){break;}}_node = parent;}return *this;}self operator++(int){self it_temp(_node);++(*this);return it_temp;}self& operator--(){if (_node->left){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}else{Node* parent = _node->parent;Node* cur = _node;while (parent->_left == cur){cur = cur->_parent;parent = parent->_parent;if (parent == nullptr){break;}}_node = parent;}return *this;}
};

3.3 测试用例

void test_iterator()
{brant::Set s;s.insert(1);s.insert(2);s.insert(3);s.insert(4);s.insert(5);brant::Set::iterator it_set = s.begin();cout << "set:" << endl;while (it_set != s.end()){cout << *it_set << " ";it_set++;}cout << endl;brant::Map m;m.insert(make_pair(1, 100));m.insert(make_pair(2, 200));m.insert(make_pair(3, 300));m.insert(make_pair(4, 400));m.insert(make_pair(5, 500));brant::Map::iterator it_map = m.begin();cout << "map:" << endl;while (it_map != m.end()){cout << (*it_map).first << "：" << (*it_map).second << endl;++it_map;}
}void test_map_()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜","苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };brant::Map countMap;for (auto& str : arr){countMap[str]++;}brant::Map::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl; for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

3.4 红黑树

只截取了改动和增添的部分。原来的红黑树在这.

template 
class RBTree
{typedef RBTreeNode Node;public:typedef __RBTreeIterator iterator;typedef __RBTreeIterator const_iteraotr;iterator begin(){//找最左节点Node* left = _root;while (left && left->_left){left = left->_left;}//用一个节点构造迭代器return iterator(left);}iterator end(){//因为没有哨兵节点，直接使用空进行返回return iterator(nullptr);}
pair  Insert(const T& data)
{KeyOfvalue kovalue;if (!_root){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}Node* parent = nullptr;Node* cur = _root;//找插入的位置while (cur){if (kovalue(cur->_data) > kovalue(data)){parent = cur;cur = cur->_left;}else if (kovalue(cur->_data) < kovalue(data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur),false);}}cur = new Node(data);//插入成功，返回新增节点 //注意：cur 可能会改变(情况1变色处理,cur指向可能会改变)//使用newnode记录新创建节点的地址Node* newnode = cur;if (kovalue(parent->_data) > kovalue(data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfater = parent->_parent;assert(grandfater);assert(grandfater->_col == BLACK);if (grandfater->_left == parent){Node* uncle = grandfater->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else{Node* uncle = grandfater->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;cur = grandfater;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfater);parent->_col = BLACK;grandfater->_col = RED;}else{RotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode), true);
}
};