map, set的封装1、共用同一棵树2、提取Key值的仿函数3、第一个模板参数Key4、Iterator5、Key值不支持修改6、map的重载[]7、析构实现了红黑树我们就要对红黑树做进一步封装map, set以能够供实际工程上的使用。对红黑树封装成map, set我们参考SGI-STL30版本的源代码。我们对封装的要求是(实现红黑树)实现共用同一棵树实现提取Key值的仿函数实现iterator和const_iterator实现Key值不支持修改的方式实现map的重载[]1、共用同一棵树我们知道数据结构set存储数据采用的是key策略而map存储数据采用的是key-value策略。而实际上STL30版本实现的map, set使用了同一种红黑树。那么STL30是如何做到同一棵红黑树实现两种不同存储数据的方式的呢如上图这是STL30用红黑树封装map时向红黑树rb_tree中传递的模板参数。第二个模板参数是value_typevalue_type其实是一个重命名这个重命名恰好是map节点存储的pair数据的类型。我们再观察STL30实现的rb_tree以及rb_tree节点的定义向rb_tree的模板参数Value处传入map的pairKey, Value类型那么最终编译器就会实例化出存储数据类型为pairKey, Value的红黑树节点类型。整个实例化过程是这样的同理我们也可以简单图示用红黑树实例化出set类的过程事实上我们可以借助STL30的做法自己来简单封装红黑树为map, set。2、提取Key值的仿函数在某些场景下我们需要提取Key值。比如实现insert()插入一个节点的方法时为了向下搜寻新节点的位置我们必须将新节点与每一层的某一个节点进行Key值的比较。而此刻我们封装map, set时事先不知道节点数据类型到底是什么也就不能轻易地直接让节点数据直接比较。我们可以在map, set内定义一个仿函数然后通过模板参数传入红黑树中在比较Key值之前将Key值提取出来以map为例给出提取data中Key值的全过程对“提取Key值的仿函数”一节内容的勘误向RBTree中直接传入提取Key值仿函数的模板名是不对的因为只传入了模板名编译器不知道你想实例化哪个版本的仿函数。所以要实例化即填入模板参数。建议把仿函数写在map, set的外部并且类型写成struct更规范3、第一个模板参数Key我们给底层的RBTree设置的模板参数列表的第一个位置是用来传递Key值类型的因为我们会实现诸如Find(), Erase()的方法。比如Find()需要直接传入Key类型的值以进行查找。为了方便区分我们干脆再传入一个Key类型。4、IteratorRBTree迭代器的实现思路与链表非常相似都是将节点指针封装成一个类然后重载相关运算符的行为。*解引用与-解引用!与重载如何重载即如何找到RBTree的后继分三种情况如果当前节点存在右子树那么后继为右子树的最左节点。如果当前节点不存在右子树而当前节点恰好是其父节点的左孩子那么后继为父节点。如果当前节点不存在右子树而当前节点是其父节点的右孩子这时应向祖先溯源直至找到孩子是父亲的左节点然后返回这个父亲。Begin()和End()如何实现Begin()找到RBTree中序最左节点即可如何实现End()目前我们的做法是返回nullptr构造的迭代器const迭代器的创建也是很重要的我们可以参考链表的const迭代器制作RBTree的const迭代器。map, set的迭代器就是RBTree迭代器的封装。5、Key值不支持修改mao, set中Key值是不支持修改的。我们可以在传入底层RBTree的模板参数上加上const但是要注意传入RBTree的T类型要与传入RBTreeIterator的T类型保持一致上图在封装RBTree迭代器为map, set迭代器时添加了typename。这是因为RBTree还没有实例化那么RBTreeIterator也就还没有实例化。这里添加typename是告诉编译器这是一个类类型而不是静态成员变量。下面验证const迭代器有效性时也遇到了要添加typename的情况这里也告诉了编译器这是一个类型。虽然模板参数给的是一个不确定的T但是加上typename相当于请求编译器通过编译。未来调用模板函数时编译器就可以通过传入的参数推导出T是什么类型进而实例化出一个确定的const迭代器类型。6、map的重载[]我们先回忆一下map的重载[]是什么(*((this-insert(make_pair(k,mapped_type()))).first)).second// mapped_type其实就是Key-Value策略里的Value值使用map的重载[]首先是试图向底层RBTree插入一个节点如果没找到存有相同Key值的节点那么就执行insert()插入方法也就是插入成功。然后insert()返回被插入节点的迭代器和bool值(true)进而通过这个迭代器找到节点最终找到Value值。如果找到了存有相同Key值的节点那么插入失败。insert()返回被找到存有相同Key值的节点的迭代器(和false)通过这个迭代器找到Value值。我们应该将insert()改造成这样然后修改对应的函数返回值即可。注意到需要向上调整节点颜色的情况。此时cur并不一定是新插入的节点。在这种场景下我们需要另外记录新插入节点{的地址)。接着外层set, map的insert()也要跟着修改。7、析构析构主要采取递归的思路。当然我们也可以理清这些需求的思路其它思路也可以以完善map, setoperator–拷贝构造函数代码
map, set的封装1、共用同一棵树2、提取Key值的仿函数3、第一个模板参数Key4、Iterator5、Key值不支持修改6、map的重载[]7、析构实现了红黑树我们就要对红黑树做进一步封装map, set以能够供实际工程上的使用。对红黑树封装成map, set我们参考SGI-STL30版本的源代码。我们对封装的要求是(实现红黑树)实现共用同一棵树实现提取Key值的仿函数实现iterator和const_iterator实现Key值不支持修改的方式实现map的重载[]1、共用同一棵树我们知道数据结构set存储数据采用的是key策略而map存储数据采用的是key-value策略。而实际上STL30版本实现的map, set使用了同一种红黑树。那么STL30是如何做到同一棵红黑树实现两种不同存储数据的方式的呢如上图这是STL30用红黑树封装map时向红黑树rb_tree中传递的模板参数。第二个模板参数是value_typevalue_type其实是一个重命名这个重命名恰好是map节点存储的pair数据的类型。我们再观察STL30实现的rb_tree以及rb_tree节点的定义向rb_tree的模板参数Value处传入map的pairKey, Value类型那么最终编译器就会实例化出存储数据类型为pairKey, Value的红黑树节点类型。整个实例化过程是这样的同理我们也可以简单图示用红黑树实例化出set类的过程事实上我们可以借助STL30的做法自己来简单封装红黑树为map, set。2、提取Key值的仿函数在某些场景下我们需要提取Key值。比如实现insert()插入一个节点的方法时为了向下搜寻新节点的位置我们必须将新节点与每一层的某一个节点进行Key值的比较。而此刻我们封装map, set时事先不知道节点数据类型到底是什么也就不能轻易地直接让节点数据直接比较。我们可以在map, set内定义一个仿函数然后通过模板参数传入红黑树中在比较Key值之前将Key值提取出来以map为例给出提取data中Key值的全过程对“提取Key值的仿函数”一节内容的勘误向RBTree中直接传入提取Key值仿函数的模板名是不对的因为只传入了模板名编译器不知道你想实例化哪个版本的仿函数。所以要实例化即填入模板参数。建议把仿函数写在map, set的外部并且类型写成struct更规范3、第一个模板参数Key我们给底层的RBTree设置的模板参数列表的第一个位置是用来传递Key值类型的因为我们会实现诸如Find(), Erase()的方法。比如Find()需要直接传入Key类型的值以进行查找。为了方便区分我们干脆再传入一个Key类型。4、IteratorRBTree迭代器的实现思路与链表非常相似都是将节点指针封装成一个类然后重载相关运算符的行为。*解引用与-解引用!与重载如何重载即如何找到RBTree的后继分三种情况如果当前节点存在右子树那么后继为右子树的最左节点。如果当前节点不存在右子树而当前节点恰好是其父节点的左孩子那么后继为父节点。如果当前节点不存在右子树而当前节点是其父节点的右孩子这时应向祖先溯源直至找到孩子是父亲的左节点然后返回这个父亲。Begin()和End()如何实现Begin()找到RBTree中序最左节点即可如何实现End()目前我们的做法是返回nullptr构造的迭代器const迭代器的创建也是很重要的我们可以参考链表的const迭代器制作RBTree的const迭代器。map, set的迭代器就是RBTree迭代器的封装。5、Key值不支持修改mao, set中Key值是不支持修改的。我们可以在传入底层RBTree的模板参数上加上const但是要注意传入RBTree的T类型要与传入RBTreeIterator的T类型保持一致上图在封装RBTree迭代器为map, set迭代器时添加了typename。这是因为RBTree还没有实例化那么RBTreeIterator也就还没有实例化。这里添加typename是告诉编译器这是一个类类型而不是静态成员变量。下面验证const迭代器有效性时也遇到了要添加typename的情况这里也告诉了编译器这是一个类型。虽然模板参数给的是一个不确定的T但是加上typename相当于请求编译器通过编译。未来调用模板函数时编译器就可以通过传入的参数推导出T是什么类型进而实例化出一个确定的const迭代器类型。6、map的重载[]我们先回忆一下map的重载[]是什么(*((this-insert(make_pair(k,mapped_type()))).first)).second// mapped_type其实就是Key-Value策略里的Value值使用map的重载[]首先是试图向底层RBTree插入一个节点如果没找到存有相同Key值的节点那么就执行insert()插入方法也就是插入成功。然后insert()返回被插入节点的迭代器和bool值(true)进而通过这个迭代器找到节点最终找到Value值。如果找到了存有相同Key值的节点那么插入失败。insert()返回被找到存有相同Key值的节点的迭代器(和false)通过这个迭代器找到Value值。我们应该将insert()改造成这样然后修改对应的函数返回值即可。注意到需要向上调整节点颜色的情况。此时cur并不一定是新插入的节点。在这种场景下我们需要另外记录新插入节点{的地址)。接着外层set, map的insert()也要跟着修改。7、析构析构主要采取递归的思路。当然我们也可以理清这些需求的思路其它思路也可以以完善map, setoperator–拷贝构造函数代码
双梁正问题 【 torch 实战】（Python代码实现）)
