C++小白的逆袭之路——进阶（第三章：map和set）

-指短琴长-

1051人浏览 · 2025-11-16 13:12:02

-指短琴长- · 2025-11-16 13:12:02 发布

前言

学习本内容，需要大家熟练掌握二叉搜索树相关内容，不了解的可以去我的数据结构专栏学习，链接在此：数据结构进阶——搜索二叉树。

1. 关联式容器

在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

2. 键值对

1. 什么是键值对：

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value。key代表键值，value表示与key对应的信息。

2. STL中对键值对的定义：

在这里插入图片描述

template <class T1, class T2>
struct pair 
{
	typedef T1 first_type;
	typedef T2 second_type;
	first_type first;
	second_type second;
	
	// 下面只介绍构造函数
	pair()
		: first(first_type())
		, second(second_typr())
	{}
 
	pair(const first_type& a, const second_type& b)
		: first(a)
		, second(b)
	{}
	
	// 若U，V和T1，T2类型相同，则下面这个函数是拷贝构造；
	// 如果不相同，就是一个普通的构造函数
	template<class U, class V> 
	pair (const pair<U,V>& pr)
		: first(pr.first)
		, second(pr.second)	
	{}
	
	...
	
};

有两个成员变量，first和second。first就是键，second就是值；
这里我们遇到了一个巧妙的设计，带模版的构造函数，关于这样设计的妙处我们在后面慢慢体会。

3. 创建键值对，make_pair函数：

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
	return ( pair<T1,T2>(x,y) );
}

今后再想创建pair键值对，直接使用make_pair函数即可。

3. 树形结构的关联式容器

3.1 set

3.1.1 set的介绍

1. 介绍：

set又称集合，是按照一定次序存储元素的容器，底层是用二叉搜索树（红黑树）；
在set中，元素的value也标识它，即元素的value也是键，即pair的key和value完全相同；
每个value必须是唯一的，体现集合的无重复性；
set中的元素不能在容器中修改（元素总是const，因为修改会破坏搜索树的结构），但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序（默认是小于比较，升序排序）。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

2. 注意+总结：

与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
set中插入元素时，只需要插入value即可，不需要构造键值对。
set中的元素不可以重复（因此可以使用set进行去重）。
使用set的迭代器遍历set中的元素，可以得到有序序列。
set中的元素默认按照小于来比较，即默认是升序。
set中查找某个元素，时间复杂度为： $log_2 n$
set中的元素不允许修改，因为会破坏搜索树的结构。
set中的底层使用二叉搜索树（红黑树）来实现。

3. Cplusplus中相关内容：

在这里插入图片描述

3.1.2 set的使用

1. set的模版参数列表：

在这里插入图片描述

T：set中存放元素的类型，实际在底层存储<value, value>的键值对；
Compare：set中元素默认按照小于来比较；
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。

2. set的构造函数：

函数声明	功能介绍
set (const Compare& comp = Compare(), const Allocator& = Allocator() );	构造空的set
set (InputIterator ﬁrst, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );	用[ﬁrst, last)区间中的元素构造set
set ( const set<Key,Compare,Allocator>& x);	set的拷贝构造

3. set的迭代器：

函数声明	功能介绍
iterator begin()	返回set中起始位置元素的迭代器
iterator end()	返回set中最后一个元素后面的迭代器
const_iterator cbegin() const	返回set中起始位置元素的const迭代器
const_iterator cend() const	返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin()	返回set第一个元素的反向迭代器，即end
reverse_iterator rend()	返回set最后一个元素下一个位置的反向迭代器，即rbegin
const_reverse_iterator crbegin() const	返回set第一个元素的反向const迭代器，即cend
const_reverse_iterator crend() const	返回set最后一个元素下一个位置的反向const迭代器，即crbegin

4. set容量：

函数声明	功能介绍
bool empty ( ) const	检测set是否为空，空返回true，否则返回true
size_type size() const	返回set中有效元素的个数

5. set修改操作：

函数声明	功能介绍
pair<iterator,bool> insert ( const value_type& x )	在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>
void erase ( iterator position )	删除set中position位置上的元素
size_type erase ( const key_type& x )	删除set中值为x的元素，返回删除的元素的个数
void erase ( iterator ﬁrst, iterator last )	删除set中[ﬁrst, last)区间中的元素
void swap ( set<Key,Compare,Allocator>& st );	交换set中的元素
void clear ( )	将set中的元素清空
iterator ﬁnd ( const key_type& x ) const	返回set中值为x的元素的位置，如果没找到返回end()
size_type count ( const key_type& x ) const	返回set中值为x的元素的个数
iterator lower_bound (const value_type& val) const;	返回>=val位置的迭代器
iterator upper_bound (const value_type& val) const;	返回>val位置的迭代器
pair<iterator,iterator> equal_range (const value_type& val) const;	返回val相等的一块区间（这个函数在set中没有意义，在multiset中才有意义）

6. 代码示例

构造函数：

void Test()
{
	// 无参构造函数
	set<int> s;	
	s.insert(2);
	s.insert(6);
	s.insert(5);
	s.insert(1);

	// 拷贝构造和使用迭代器区间构造
	set<int> s2(s);
	set<int> s3(s.begin(), s.end());
}

迭代器遍历：

void Test()
{
	// 用数组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[0]));
	cout << s.size() << endl;

	// 可以发现，默认是升序排序，可以去重
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;
	// set中值为3的元素出现了几次（只可能是1次，或0次，所以count也可以用来判断元素在不在）
	cout << s.count(3) << endl; 
}

插入和删除：

void Test()
{
	set<int> s;
	for (int i = 1; i < 10; i++) s.insert(i * 10); // 10 20 30 40 50 60 70 80 90

	// 判断是否插入成功
	pair<set<int>::iterator, bool> ret = s.insert(2);
	if (ret.second)
		cout << "插入成功" << endl;
	else
		cout << "插入失败" << endl;

	// 按value删，删除存在的
	s.erase(10);
	// 删除不存在的，不报错
	s.erase(39);	

	// 按位置删
	set<int>::iterator it = s.find(60);
	if (it != s.end())
		s.erase(it);	// 这里如果不判断，并且要删除的元素不存在，则会崩溃
	

	// 重新赋值
	s.clear();
	for (int i = 1; i < 10; i++) s.insert(i * 10); // 10 20 30 40 50 60 70 80 90

	set<int>::iterator itlow, itup;
	itlow = s.lower_bound(30);	// 返回>=30的位置
	itup = s.upper_bound(65);	// 返回>65的位置，对应上述set是70的位置

	// 删除一段迭代器区间
	s.erase(itlow, itup);
	for (auto e : s)
	{
		cout << e << " ";	// 0 10 20 70 80
	}
	cout << endl;
}

3.2 multiset

1. 介绍：

multiset是一种特殊的set，它与set的区别就是可以存放重复元素；
所以multiset的主要功能是排序，但不能去重。

2. 使用：

此处只简单演示set与multiset的不同，其他接口接口与set相同，同学们可参考set。

void Test()
{
	multiset<int> s;

	s.insert(2);
	s.insert(2);
	s.insert(2);
	s.insert(2);
	s.insert(2);
	s.insert(1);
	s.insert(4);
	s.insert(5);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	// 1 2 2 2 2 2 3 3 3 4 5
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// find返回中序遍历该值的第一个位置
	multiset<int>::iterator it = s.find(3);
	// 3 3 3 4 5
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 体现equal_range的价值
	pair<multiset<int>::iterator, multiset<int>::iterator> ret = s.equal_range(2);
	s.erase(ret.first, ret.second);	
	// 1 3 3 3 4 5
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 实际上equal_range的价值不大，想删多个重复元素直接用erase即可
	size_t n = s.erase(3);
	// 1 4 5
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "删了几个：" << n << endl;
}

3.3 map

3.3.1 map的介绍

1. 介绍：

map是关联容器，它按照特定的次序（按照key来比较）存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair。

 typedef pair<const key, T> value_type;

在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列）。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
map底层也是红黑树。

2. Cplusplus中相关内容：

在这里插入图片描述

value_type定义为pair<const key_type, mapped_type>。因为map期望键不能更改，值可以更改。

3.3.2 map的使用

1. map的模版参数说明：

在这里插入图片描述

key：键值对中key的类型。
T：键值对中value的类型。
Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）。
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

2. map的构造：

函数声明	功能介绍
map()	构造一个空的map

3. map的迭代器：

函数声明	功能介绍
begin()和end()	begin:首元素的位置，end:最后一个元素的下一个位置
cbegin()和cend()	与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()和rend()	反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
crbegin()和crend()	与rbegin和rend位置相同，操作相同，但crbegin和crend所指向的元素不能修改

4. map中元素的修改：

函数声明	功能简介
pair<iterator,bool> insert ( const value_type& x )	在map中插入键值对x，注意x是一个键值对，返回值也是键值对：iterator代表新插入元素的位置，bool代表释放插入成功
void erase ( iterator position )	删除position位置上的元素
size_type erase ( const key_type& x )	删除键值为x的元素
void erase ( iterator ﬁrst, iterator last )	删除[ﬁrst, last)区间中的元素
void swap ( map<Key,T,Compare,Allocator>& mp )	交换两个map中的元素
void clear ( )	将map中的元素清空
iterator ﬁnd ( const key_type& x )	在map中查找key为x的元素，找到返回该元素的位置的迭代器，否则返回end
const_iterator ﬁnd ( const key_type& x ) const	在map中查找key为x的元素，找到返回该元素的位置的const迭代器，否则返回cend
size_type count ( const key_type& x ) const	返回key为x的键值在map中的个数，注意map中key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

重点讲解一下insert插入：

在这里插入图片描述

// 下面这段测试代码是可以跑通的
void Test1()
{
	map<string, string> dict;
	dict.insert(pair<string, string>("sort", "排序"));
	dict.insert(pair<string, string>("insert", "插入"));
	dict.insert(pair<const char*, const char*>("left", "左边"));

	// 推荐写法，不用显示的写类型了，用make_pair自动推导
	dict.insert(make_pair("right", "右边"));
}

通过观察insert的接口不难发现，我们经常使用的insert，参数类型是value_type，在map中的定义是pair<const key_type, mapped_type>。也就是说，我们要想使用insert，就需要自己构造键值对pair，作为参数传递给map。
但是上面的例子中，dict的类型明明是<string, string>，实例化出的insert参数类型是const pair<const string, string>，dict.insert(pair<const char*, const char*>("left", "左边"));这句代码却可以跑通，这作何解释？我们来一步一步分析这个代码。
首先，我们构造了一个匿名对象，类型是pair<const char*, const char*>，并将其作为参数传给了insert。但是该实参和形参的类型不符，所以发生了类型转换。
发生类型转换就要产生临时变量。转换过程会先调用构造函数（单参数的构造函数支持隐式类型转化），构造一个const pair<const string, string>类型的临时变量，使用的是pair中的模版构造函数。然后将这个临时变量的引用，传给insert的形参。
因为临时变量具有常属性，所以insert的形参必须用const修饰，不然会导致权限放大而报错。

5. map的容量和元素访问：

函数声明	功能简介
bool empty ( ) const	检测map中的元素是否为空，是返回true，否则返回false
size_type size() const	返回map中有效元素的个数
mapped_type& operator[] (const key_type& k)	返回key对应的value

问题：当key不在map中时，通过operator[]获取对应value时会发生什么问题？
- 在元素访问时，有一个与operator[]类似的操作at()函数（不常用），都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。

6. 使用实例

统计水果出现的次数：

void fruitCount()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };

	map<string, int> countMap;
	for (auto& str : arr)
	{
		map<string, int>::iterator ret = countMap.find(str);
		if (ret != countMap.end())
		{
			ret->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}

	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

可以上面这个功能还可以这样写，借此引入operator[]的神奇之处：

void fruitCount()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };

	map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

operator[]在库中的定义：

mapped_type& operator[] (const key_type& k)
{
	return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}

上面代码可读性不是很强，我们可以对其进行改写，当然功能还是一样的：

mapped_type& operator[] (const key_type& k)
{
	pair<iterator, bool> ret = this->insert(make_pair(k, mapped_type()));
	return ret.first->second;
}

现在我们插入一个元素，当map中没有这个元素时，insert就相当于插入操作，返回插入新元素的位置，和true表示插入成功。
当map中有这个元素时，insert就相当于查找操作，返回找到的这个已有元素的位置，和false表示插入失败。
insert的返回结果被存在ret中，通过ret.first可以拿到对应位置的迭代器，然后解引用这个迭代器，返回对应位置的value值。
解析过operator[]后，我们再来看看统计水果的代码中，使用operator[]的可行性：
- 如果map中没有这个元素，operator[]完成插入操作，并且内置类型int也有自己的默认构造函数，会将数据初始化成0。所以插入的键值对就是<str, 0>；如果map中有这个元素，那么operator[]相当于查找，operator[str]++完成的操作就是找到key为str的元素，对其value++。

3.4 multimap

1. 介绍：

multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对：

typedef pair<const Key, T> value_type;

在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
multimap在底层用二叉搜索树（红黑树）来实现。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。

2. multimap的使用：

multimap中的接口可以参考map，功能都是类似的。
注意：
- multimap中的key是可以重复的。
- multimap中的元素默认将key按照小于来比较。
- multimap中没有重载operator[]操作。
- 使用时与map包含的头文件相同。

3.5 map和set练习

1. 两个数组的交集：

leedcode链接：https://leetcode.cn/problems/intersection-of-two-arrays/submissions/535475410/

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) 
    {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        vector<int> v;

        auto it1 = s1.begin();
        auto it2 = s2.begin();
        // 双指针算法
        while (it1 != s1.end() && it2 != s2.end())
        {
            if (*it1 == *it2)
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
            else
            {
                *it1 > *it2 ? ++it2 : ++it1;    // 如果不相等，小的++
            }
        }

        return v;
    }
};

2. 前K个高频单词：

leedcode链接：https://leetcode.cn/problems/top-k-frequent-words/description/

class Solution {
public:
	// 自定义比较规则
    struct kvCom
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string, int> countMap;
        for (auto str : words)
        {
            countMap[str]++;
        }

        // map无法直接使用sort，先转换成vector
        vector<pair<string, int>> kvV(countMap.begin(), countMap.end());
        sort(kvV.begin(), kvV.end(), kvCom());

        vector<string> v;
        for (int i = 0; i < k; i++)
        {
            v.push_back(kvV[i].first);
        }

        return v;
    }
};

4. map和set的模拟实现

学习本节，需要先了解红黑树这个数据结构，因为map和set的底层是红黑树，相关学习文章如下：数据结构进阶——红黑树。

4.1 红黑树的封装

4.1.1 红黑树的迭代器

1. begin()与end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后（左根右），可以得到一个有序的序列，所以我们使用中序遍历红黑树：

在这里插入图片描述

因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在根节点的父节点，也就是空，是整个遍历过程中经过的最后位置。

2. operator++()与operator--()

以operator++()为例讲解。

从上图中的1号节点开始遍历（先访问1号节点），因为是最左节点，所以左子树一定为空，需要往右子树遍历，去找右子树的最左节点。
找到右子树的最左节点为6号节点，访问它。然后去找6号节点右子树的最左节点，发现6号节点的右子树为空，这时就需要向上查找没有访问过的祖宗节点。
1号节点被访问过了，所以不再访问1号节点，继续向上查找。找到8号节点，没有被访问过，访问它。
接着往8号节点的右子树查找，还是找最左节点。如此循环往复。
总结一下，operator++()的思路是：
- 先访问右子树，找右子树最左节点，访问它；
- 如果右子树为空了，再向上找没有访问过的祖宗节点，进行访问；
- 怎么判断一个祖宗节点有没有被访问过？很简单，看看是不是从这个祖宗节点的右子树找上来的。如果是的话，就说明被访问过了。
operator--()与operator++()完全相反：
- 先访问左子树，找左子树最右节点，访问它；
- 如果左子树为空了，再向上找没有访问过的祖宗节点，进行访问；
- 怎么判断一个祖宗节点有没有被访问过？很简单，看看是不是从这个祖宗节点的左子树找上来的。如果是的话，就说明被访问过了。

下面我们只实现operator++()，感兴趣的同学可以自己实现一下operator()--。也就是说，我们只实现正向迭代器。

3. 下面附上红黑树迭代器代码（注：要适配map和set，迭代器还需修改）

与小节开头学习文章中的红黑树不同，这是一颗K结构的红黑树，模版参数中只有一个T。

#pragma once

#include <iostream>

enum Colour
{
	RED,
	BLACK
};

using namespace std;

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>
struct __TreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator<T> Self;
    Node* _node;

    __TreeIterator(Node* node)
        :_node(node)
    {}

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

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

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

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

    Self& operator++()
    {
        if (_node->_right)
        {
            // 右子树不为空
			// 下一个就是右子树的最左节点
            Node* cur = _node->_right;
            while(cur->_left)
            {
                cur = cur->_left;
            }
            _node = cur;
        }
        else
        {
            // 遍历顺序：左子树 根 右子树
			// 右为空，以当前节点为根节点的子树已经完全访问完了（包括当前节点）
			// 需要不断向上去找没有访问过的父亲节点。
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right) // 判断parent是否为空是为了处理根节点
            {
                // 如果当前节点是父节点的右节点，那么说明当前父节点也被遍历过了，不需要访问，接着向上找
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }

        return *this;
    }
};
/*-----------------------------------------------------------------------*/

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
/*------------------------------迭代器部分-------------------------------*/
    typedef __TreeIterator<T> iterator;

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

    iterator end()
    {
        return nullptr;
    }
/*----------------------------------------------------------------------*/
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;	// 根节点必须是黑色
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;

		// 先找到要插入的位置
		while (cur)
		{
			if (data > cur->_data)		
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		// 设定新增节点为红色
		cur = new Node(data);
		cur->_col = RED;
		if (data > parent->_data)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在并且是红色，再处理，是黑色不用处理
		while(parent && parent->_col == RED)
		{
			Node* grandFather = parent->_parent;
			
			if (parent == grandFather->_left)
			{
				// 这里只是说父亲在爷爷左边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  p	  u
				//	  c
				// 父亲是爷爷的左节点，那么叔叔就是爷爷的右节点
				Node* uncle = grandFather->_right;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续往上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						// cur 在父亲左边，右单旋（左左黑）
						//		g
						//	  p
						//	c
						RotateR(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲右边，左右双旋（左右黑）
						//		g
						//	  p
						//		c
						RotateL(parent);
						RotateR(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
			else // parent == grandFather->_right
			{
				// 这里只是说父亲在爷爷右边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  u	  p
				//		  c
				// 父亲是爷爷的右节点，那么叔叔就是左节点
				Node* uncle = grandFather->_left;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续向上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// cur 在父亲右边，左单旋（右左黑）
						//		g
						//		  p
						//			c
						RotateL(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲左边，右左双旋（左右黑）
						//		g
						//		  p
						//		c
						RotateR(parent);
						RotateL(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
		}
			
		// 不管前面如何处理，最后都要把根节点变黑
		_root->_col = BLACK;
		return true;
	}

	// 左单旋
	void RotateL(Node* parent)
	{
		...
	}

	// 右单旋
	void RotateR(Node* parent)
	{
		...
	}
};

4.1.2 KeyOfT 红黑树的值比较方法

1. 问题引入

我们的最终目标是让红黑树适配map和set，作为他们的底层结构。由此会产生一个问题，map使用时需要分别传入<key, value>键值对中key和value的类型（例如：map<string, int>）；而set在使用时只需要传入一个数据类型，因为它的key和value是完全相同的（例如：set<int>）。
对应到上面的红黑树中，实例化出的树对象就是：

RBTree<pair<string, int>> map_tree;
RBTree<int> set_tree;

对于set_tree，insert中的比较部分（例如：data < cur->_data）可以正常比较。但是对于map_tree，data是pair<string, int>类型，比较变成了两个pair之间的比较。
我们希望，map_tree中的data的比较，仅仅是比较键，即pair中的first。那么pair重载的比较运算符，能满足我们的需求吗？

STL中pair对比较运算符的定义如下。

template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

template <class T1, class T2>
  bool operator>  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return rhs<lhs; }

可以发现，标准库中对pair比较运算符的重载定义中，不仅比较了first还比较了second，这显然不是我们想要的。那该怎么办？
我们可以给红黑树新增一个模版参数 KeyOfT，它实际上是一个类类型，实例化后充当仿函数的作用。由map和set决定这个仿函数该如何实现，然后将这个仿函数用于data的比较。
这个仿函数的作用就是取出map和set，data中的key值。

2. 代码展示

Map实现：

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };

        bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
    private:
        RBTree<pair<K, V>, MapKeyOfT> _t;
    };
}

Set实现：

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K>
    class set
    {
    public:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };
    
        bool insert(const K& key)
		{
			return _t.Insert(key);
		}
    private:
        RBTree<K, SetKeyOfT> _t;
    };
}

红黑树改造：

#pragma once

#include <iostream>

enum Colour
{
	RED,
	BLACK
};

using namespace std;

template<class T>
struct RBTreeNode
{
	T _data;
	...	
};

template<class T>
struct __TreeIterator
{
   ...
};


template<class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
    ...

	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;	// 根节点必须是黑色
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
        KeyOfT kot;

		// 先找到要插入的位置
		while (cur)
		{
			if (kot(data) > kot(cur->_data))	// 使用kot预处理data
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_data))	// 使用kot
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		// 设定新增节点为红色
		cur = new Node(data);
		cur->_col = RED;
		if (kot(data) > kot(parent->_data))	// 使用kot
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		...
	}
	...
};

4.1.3 阶段测试

实现了红黑树的迭代器和 KeyOfT 后，我们就可以进行一轮阶段性的测试了

1. 先将map和set再完善一下，套上迭代器：

// MySet.h 内容如下

namespace my
{
    template<class K>
    class set
    {
    public:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<K, SetKeyOfT>::iterator iterator;
		iterator begin() 
		{
			return _t.begin();
		}

		iterator end() 
		{
			return _t.end();
		}
    
        bool insert(const K& key)
		{
			return _t.Insert(key);
		}
    private:
        RBTree<K, SetKeyOfT> _t;
    };
}

// MyMap.h 内容如下：
#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<pair<K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

        bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
    private:
        RBTree<pair<K, V>, MapKeyOfT> _t;
    };
}

2. 测试代码（测试迭代器和插入的效果）：

#include <iostream>
#include "RBTree.h"
#include "MyMap.h"
#include "MySet.h"

void test_set()
{
	my::set<int> s;
	s.insert(4);
	s.insert(5);
	s.insert(6);
	s.insert(213);
	s.insert(343);

	auto it = s.begin();
	while (it != s.end())
	{
		// *it += 1;	// 不应该支持修改
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_map()
{
	my::map<string, string> dict;
	dict.insert(make_pair("part", "部分"));
	dict.insert(make_pair("find", "查找"));
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("left", "左边"));
	dict.insert(make_pair("right", "右边"));

	auto it = dict.begin();
	while (it != dict.end())
	{
		// it->first += 'x';	// 不应该支持key修改
		// it->second += 'y';
		cout << it->first << ": " << it->second << endl;
		++it;
	}
}

int main()
{
    test_set();
    test_map();
    return 0;
}

上面的测试代码中，我故意注释掉了一部分，现在请大家把注释部分放开。这会引入一个新问题，无论是对于map还是set，都不应该支持Key的修改，但是测试结果是支持的，这是个致命的缺陷，因为会破坏整个树的结构。

需要用const迭代器解决上面的问题。

4.1.4 const 迭代器

1. 设计红黑树的 const 迭代器

const 迭代器的设计相对简单，大家可以参考我的另一篇文章：C++小白的逆袭之路——初阶（第十章：list）const 迭代器部分。

template<class T>
struct RBTreeNode
{
	...
};

template<class T, class Ref, class Ptr>	// 添加Ref，Ptr模版参数
struct __TreeIterator
{
    typedef RBTreeNode<T> Node;
/*---------------------修改--------------------------*/
    typedef __TreeIterator<T, Ref, Ptr> Self;
/*---------------------------------------------------*/
    Node* _node;

    __TreeIterator(Node* node)
        :_node(node)
    {}
/*---------------------修改--------------------------*/
    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &_node->_data;
    }
/*---------------------------------------------------*/
    Self& operator++()
    {
        ...
    }
};


template<class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
/*---------------------------------修改-----------------------------------*/
    typedef __TreeIterator<T, T&, T*> iterator;
    typedef __TreeIterator<T, const T&, const T*> const_iterator; 
/*-----------------------------------------------------------------------*/

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

    iterator end()
    {
        return nullptr;
    }
/*--------------------------------新增-----------------------------------*/
    const_iterator begin() const
    {
        Node* cur = _root;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }

    const_iterator end() const
    {
        return nullptr;
    }
/*------------------------------------------------------------------------*/
	...
};

2. set 的 const 迭代器

如何保证set的Key值不被修改呢？当我们没有思路时，不妨看看源码：

在这里插入图片描述

可以看到，set的迭代器和const迭代器，通通都是红黑树的const_iterator，原来是这样设计的，我们来抄袭一下：

// MySet.h
#pragma once

#include "RBTree.h"

namespace my
{
    template<class K>
    class set
    {
    public:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, SetKeyOfT>::const_iterator const_iterator;
		iterator begin() const
		{
			return _t.begin();
		}

		iterator end() const
		{
			return _t.end();
		}
    
        bool insert(const K& key)
		{
			return _t.Insert(key);
		}
    private:
        RBTree<K, SetKeyOfT> _t;
    };
}

实际上，已经不需要再实现cbegin()和cend()了，begin()和end()就完全够用了，把const_iterator写出来也只是意思一下。

3. map 的 const 迭代器

map和set不同，map要限制Key的修改，但是要把Value放开，看看源码：

在这里插入图片描述

可以看到，map的迭代器还是中规中矩的，const是const，普通迭代器是普通迭代器。为了实现限制Key的修改，把Value放开，map直接在红黑树成员的定义部分，在pair内部用const修饰了K。

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<pair<const K, V>, MapKeyOfT>::iterator iterator;	// 这里也要跟着改，用const修饰K
		typedef typename RBTree<pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

        bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
    private:
/*--------------------------这里K直接用const修饰-------------------------*/
        RBTree<pair<const K, V>, MapKeyOfT> _t;
/*----------------------------------------------------------------------*/
    };
}

也不需要cbegin()和cend()了，都多余了。

4.1.5 红黑树改造，支持map的[ ]

根据以往模拟实现STL容器的经验，重载[]就是要对insert下手。

1. 改造红黑树的 Insert

对返回值部分做修改，返回一个pair<>，Key是当前节点，Value是布尔类型，表示是否插入成功。

template<class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
	...
	
    pair<Node*, bool> Insert(const T& data)	// 修改返回值
    {
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;	// 根节点必须是黑色
/*----------------------------------修改-------------------------------*/
			return make_pair(_root, true);
/*--------------------------------------------------------------------*/
		}

		Node* parent = nullptr;
		Node* cur = _root;
        KeyOfT kot;

		// 先找到要插入的位置
		while (cur)
		{
			if (kot(data) > kot(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
/*----------------------------------修改-------------------------------*/
				return make_pair(cur, false);	// 插入失败，Key已存在，就返回这个已存在节点（给外部[]提供查找功能）
/*--------------------------------------------------------------------*/
			}
		}

		// 设定新增节点为红色
		cur = new Node(data);
/*----------------------------------新增-------------------------------*/
        Node* newnode = cur;    // 提前记录
/*---------------------------------------------------------------------*/
		cur->_col = RED;
		if (kot(data) > kot(parent->_data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在并且是红色，再处理，是黑色不用处理
		while(parent && parent->_col == RED)
		{
			Node* grandFather = parent->_parent;
			
			if (parent == grandFather->_left)
			{
				// 这里只是说父亲在爷爷左边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  p	  u
				//	  c
				// 父亲是爷爷的左节点，那么叔叔就是爷爷的右节点
				Node* uncle = grandFather->_right;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续往上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						// cur 在父亲左边，右单旋（左左黑）
						//		g
						//	  p
						//	c
						RotateR(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲右边，左右双旋（左右黑）
						//		g
						//	  p
						//		c
						RotateL(parent);
						RotateR(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
			else // parent == grandFather->_right
			{
				// 这里只是说父亲在爷爷右边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  u	  p
				//		  c
				// 父亲是爷爷的右节点，那么叔叔就是左节点
				Node* uncle = grandFather->_left;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续向上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// cur 在父亲右边，左单旋（右左黑）
						//		g
						//		  p
						//			c
						RotateL(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲左边，右左双旋（左右黑）
						//		g
						//		  p
						//		c
						RotateR(parent);
						RotateL(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
		}
			
		// 不管前面如何处理，最后都要把根节点变黑
		_root->_col = BLACK;
/*----------------------------------修改-------------------------------*/
		return make_pair(newnode, true);	// 插入成功，就返回新节点
/*--------------------------------------------------------------------*/
    }
};

2. map重载[]

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

/*-------------------------------修改---------------------------------*/
        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            // 第一次->first访问的是迭代器，第二次->second才是访问value
            return ret.first->second;  
        }

        pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
/*---------------------------------------------------------------------*/
    private:
        RBTree<pair<const K, V>, MapKeyOfT> _t;
    };
}

测试代码：

#include <iostream>
#include "RBTree.h"
#include "MyMap.h"

void test_map()
{
	my::map<string, string> dict;
    dict["part"] = "部分";
    dict["find"] = "查找";
    dict["sort"] = "排序";
    dict["left"] = "左边";
    dict["right"] = "右边";

	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ": " << it->second << endl;
		++it;
	}

    cout << "测试修改" << endl;
    dict["part"] = "11";
    dict["find"] = "22";
    dict["sort"] = "33";
    dict["left"] = "44";
    dict["right"] = "55";
    it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ": " << it->second << endl;
		++it;
	}
}

int main()
{
    test_map();
    return 0;
}

3. 体会pair的巧妙之处

template <class T1, class T2>
struct pair 
{	
	typedef T1 first_type;
	typedef T2 second_type;
	first_type first;
	second_type second;
	
	// 若U，V和T1，T2类型相同，则下面这个函数是拷贝构造；
	// 如果不相同，就是一个普通的构造函数
	template<class U, class V> 
	pair (const pair<U,V>& pr)
		: first(pr.first)
		, second(pr.second)	
	{}
	
	...
	
};

pair有一个十分巧妙的设计，即当U，V和T1，T2类型相同，则上面的函数是拷贝构造；如果不相同，就是一个普通的构造函数。
那这有什么用呢？在上面对红黑树Insert的改造中，返回值是pair<Node*, bool>类型的，而在map的Insert中，返回值是pair<iterator, bool>类型。之所以pair<Node*, bool>能转化成pair<iterator, bool>类型，就是因为，Node*类型能构造iterator类型，bool类型能构造bool类型。
即只要U能构造T1，V能构造T2，一个pair就能构造另一个pair。

思考：如果红黑树的insert返回pair<iterator, bool>类型可以吗？（此处的iterator是红黑树中定义的）

只考虑到map，这是完全可行的，但是考虑到set，就不可行。因为set中，也会调用insert，要想和红黑树的Insert适配，就只能把返回值也设置成pair<iterator, bool>。但是还有问题，因为set中的iterator其实是红黑树中的const_iterator，和红黑树Insert返回的iterator根本是两个类型。要想支持这样搞，就必须实现红黑树中iterator向const_iterator转换的构造函数。

4.1.6 实现map和set的find

1. 看看我们目前实现的map和set，和库中的有什么不同

看一眼库中的：

在这里插入图片描述

再看一眼我们实现的：

在这里插入图片描述

先不看后面的参数，我们只关注库中的前两个模版参数，第二个value_type我们理解，可以和我们实现的代码中，红色圈起来的部分对应上。那库中蓝色圈起来的部分，是什么？它为什么还要多传个key_type，这个key_type不是在value_type中吗？

库中多传一个key_type，说明底层的红黑树也和我们实现的不一样，要多一个模版参数接收key_type。

因为map和set的find方法需要这个参数。 无论是map还是set的find，都只需要传一个参数，即Key。那么红黑树在实现Find时，就应该只传入Key，但是你会尴尬的发现，对于map，我们的红黑树中并没有Key的类型，只有<Key, Value>的类型。之前的仿函数只是将Key的值取出来，而不是取出类型！！！ 那么下面这个Find的参数，你怎么声明？

在这里插入图片描述

解决方案就是再传一个模版参数，单独传入Key的类型：

在这里插入图片描述

2. 实现红黑树Find

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
	...
	pair<Node*, bool> Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, true); // 找到了，返回真
			}
		}

		return make_pair(cur, false); // 找不到，返回假（此时cur为空）
	}
};

3. 实现map和set的find

map：

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };

        // 对类模版取内置类型，加typename
/*------------------------------------修改---------------------------------*/
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
/*------------------------------------------------------------------------*/
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            // 第一次->first访问的是迭代器，第二次->second才是访问value
            return ret.first->second;  
        }

        pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

/*----------------------------新增-----------------------------*/
        iterator find(const K& key)
        {
            pair<iterator, bool> ret = _t.Find(key);
            return ret.first;
        }
/*------------------------------------------------------------*/
    private:
/*------------------------------------修改---------------------------------*/
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
/*------------------------------------------------------------------------*/
    };
}

set：

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K>
    class set
    {
    public:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        // 对类模版取内置类型，加typename
/*------------------------------------修改---------------------------------*/
		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();
		}
    
        pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

/*------------------------------------新增---------------------------------*/
        iterator find(const K& key)
        {
            pair<iterator, bool> ret = _t.Find(key);
            return ret.first;
        }
/*------------------------------------------------------------------------*/
    private:
/*------------------------------------修改---------------------------------*/
        RBTree<K, K, SetKeyOfT> _t;
/*------------------------------------------------------------------------*/
    };
}

4.2 红黑树封装+map和set模拟实现完整代码

1. 红黑树封装

#pragma once

#include <iostream>

enum Colour
{
	RED,
	BLACK
};

using namespace std;

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 __TreeIterator
{
    typedef RBTreeNode<T> Node;
    typedef __TreeIterator<T, Ref, Ptr> Self;
    Node* _node;

    __TreeIterator(Node* node)
        :_node(node)
    {}

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

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

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

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

    Self& operator++()
    {
        if (_node->_right)
        {
            // 右子树不为空
			// 下一个就是右子树的最左节点
            Node* cur = _node->_right;
            while(cur->_left)
            {
                cur = cur->_left;
            }
            _node = cur;
        }
        else
        {
            // 遍历顺序：左子树 根 右子树
			// 右为空，以当前节点为根节点的子树已经完全访问完了（包括当前节点）
			// 需要不断向上去找没有访问过的父亲节点。
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right) // 判断parent是否为空是为了处理根节点
            {
                // 如果当前节点是父节点的右节点，那么说明当前父节点也被遍历过了，不需要访问，接着向上找
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }

        return *this;
    }
};

/*
	set: RBtree<K, K, SetKeyofT>
	map: RBTree<K, pair<K, V>, MapKeyofT>
*/
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
private:
	Node* _root = nullptr;

public:
    typedef __TreeIterator<T, T&, T*> iterator;
    typedef __TreeIterator<T, const T&, const T*> const_iterator; 

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

    iterator end()
    {
        return nullptr;
    }

    const_iterator begin() const
    {
        Node* cur = _root;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }

    const_iterator end() const
    {
        return nullptr;
    }

	pair<Node*, bool> Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, true); // 找到了，返回真
			}
		}

		return make_pair(cur, false); // 找不到，返回假（此时cur为空）
	}

    pair<Node*, bool> Insert(const T& data)
    {
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;	// 根节点必须是黑色
			return make_pair(_root, true);
		}

		Node* parent = nullptr;
		Node* cur = _root;
        KeyOfT kot;

		// 先找到要插入的位置
		while (cur)
		{
			if (kot(data) > kot(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(data) < kot(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		// 设定新增节点为红色
		cur = new Node(data);
        Node* newnode = cur;    // 提前记录
		cur->_col = RED;
		if (kot(data) > kot(parent->_data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		// 如果父节点存在并且是红色，再处理，是黑色不用处理
		while(parent && parent->_col == RED)
		{
			Node* grandFather = parent->_parent;
			
			if (parent == grandFather->_left)
			{
				// 这里只是说父亲在爷爷左边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  p	  u
				//	  c
				// 父亲是爷爷的左节点，那么叔叔就是爷爷的右节点
				Node* uncle = grandFather->_right;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续往上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						// cur 在父亲左边，右单旋（左左黑）
						//		g
						//	  p
						//	c
						RotateR(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲右边，左右双旋（左右黑）
						//		g
						//	  p
						//		c
						RotateL(parent);
						RotateR(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
			else // parent == grandFather->_right
			{
				// 这里只是说父亲在爷爷右边，而cur有可能在父亲的左节点也有可能在右节点
				// 后面还要再做讨论
				//		g
				//	  u	  p
				//		  c
				// 父亲是爷爷的右节点，那么叔叔就是左节点
				Node* uncle = grandFather->_left;
				// 叔叔存在，并且叔叔是红色（叔叔红）
				if (uncle && uncle->_col == RED)
				{
					// 变色
					uncle->_col = parent->_col = BLACK;
					grandFather->_col = RED;

					// 继续向上处理
					cur = grandFather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// cur 在父亲右边，左单旋（右左黑）
						//		g
						//		  p
						//			c
						RotateL(grandFather);
						parent->_col = BLACK;
						grandFather->_col = RED;
					}
					else
					{
						// cur 在父亲左边，右左双旋（左右黑）
						//		g
						//		  p
						//		c
						RotateR(parent);
						RotateL(grandFather);
						grandFather->_col = RED;
						cur->_col = BLACK;
					}
					// 旋转之后直接就平衡了，直接break
					break;
				}
			}
		}
			
		// 不管前面如何处理，最后都要把根节点变黑
		_root->_col = BLACK;
		return make_pair(newnode, true);
    }
    
	// 左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 更新左右节点
		parent->_right = subRL;
		subR->_left = parent;

		Node* parentParent = parent->_parent;

		// 更新父节点
		parent->_parent = subR;
		if (subRL != nullptr)
		{
			subRL->_parent = parent;
		}
		
		// 将子树链接进整体
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
			subR->_parent = parentParent;
		}
		else
		{
			parentParent->_right = subR;
			subR->_parent = parentParent;
		}
	}

	// 右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		// 更新左右节点
		parent->_left = subLR;
		subL->_right = parent;

		Node* parentParent = parent->_parent;

		// 更新父节点
		parent->_parent = subL;
		if (subLR != nullptr)
		{
			subLR->_parent = parent;
		}

		// 将子树链接进整体
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
			subL->_parent = parentParent;
		}
		else
		{
			parentParent->_right = subL;
			subL->_parent = parentParent;
		}
	}
};

2. map模拟实现

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K, class V>
    class map
    {
    public:
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };

        // 对类模版取内置类型，加typename
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            // 第一次->first访问的是迭代器，第二次->second才是访问value
            return ret.first->second;  
        }

        pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

        iterator find(const K& key)
        {
            pair<iterator, bool> ret = _t.Find(key);
            return ret.first;
        }
    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
    };
}

3. set模拟实现

#pragma once

#include "RBTree.h"

namespace my
{
    template<class K>
    class set
    {
    public:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        // 对类模版取内置类型，加typename
		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();
		}
    
        pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

        iterator find(const K& key)
        {
            pair<iterator, bool> ret = _t.Find(key);
            return ret.first;
        }
    private:
        RBTree<K, K, SetKeyOfT> _t;
    };
}