**
因为本人之前一直写的是电子笔记，对自己学会的东西作一个总结，所以基本都是文字，本来想全发成博客的形式，发现全发成博客比较花费时间，而且一直发博客质量不是很好，而且通过发博客学到的东西也会变少，所以准备先把笔记发出来，后续再将它们改成博客的形式，争取2天至少改一篇博客，觉得我总结的还行的可以先关注我，后续会发成博客形式，内容也会更加完善
**
pair对象：
因为pair是用结构体写的，所以它里面的成员默认是公共的，并且pair也没有设置私有的成员，所以可以不实例化对象，直接进行赋值，但下次要想调用这个，就不能得到了
然后就是make_pair了，它最大的优点就是可以直接给pair传值（也是一次性传值的那种，传完了就不管，也调用不到，只有通过返回值赋给其它的对象），不用管类型，因为make_pair是用一个模板写的函数，模板函数可以自己进行类型推导，可以直接获取类型，然后再由自己内部实现的给pair值，这样我们在使用时就不用管类型直接可以传我们想传的值，这样就很方便
构造map时最重要的就是送代器的实现：
当实现送代器时， 是以一种中序遍历的方法实现的，但并不是递规，因为送代器就是像是一种++的操作得一个一个来，所以在开始实现时，我们得在RBT树的根节点上再添加一个header节点方便我们实现，这个header的父亲节点是root，左孩子是root的最左边的孩子，右孩子是root的最右边的孩子，如果没有左树或右树，那二个节点连接的都是root节点，这样我们在实现一个正常的iterator时我们传进去的begin是最左边的孩子，从小往大来送代，就是中序遍历
当开始遍历时我们要先找看它有没有右孩子（找到父亲节点的孩子不是右孩子的节点），如果没有右孩子，那就往上遍历，如果有右孩子，那就从这个右孩子的最左孩子开始遍历，（按RBT的结构来说这个最左孩子一定是它右孩子中最小的一个比它大的节点，所以也符合顺序，这就是中序遍历的原因，可以排序）因为它把左边遍历完了后，就会去它右边找，这时如果右边有节点还有并且还有左孩子那么又是左、中、右的一个遍历，最后遍历完时，一定是那棵子树最右边的那个节点，在这个过程中，它每次左边完了后，去它的父亲节点，然后要判断一下，遍历上来的是不是右孩子，如果不是，就去右边，如果是右孩子遍历完之后上来的那就说明，右边已经遍历完了，要找它的父亲节点，因为这时这个父亲节点一定是遍历过的，所以它也要往上走，但它如果是父亲节点的右孩子的话，那它的父亲节点，也一定被遍过，就要继续往上走，直到找到它不是父亲节点的右孩子时，就找到了，总之就是这是个中序遍历，如果右边被遍历过了，那它的父亲也一定被遍历过了，要找到这个节点的孩子不是右孩子的节点（这句话的意思是，这个节点得是左节点或父节点），最后因为之前有一个header节点，所以当右子树为空树时，因为root节点，去找右子树时，发现是空所以它向上遍历，因为header的右刚好连的是root，所以root节点变为了父节点，而header变为了现在的节点，这样就会出错，因为header不是用了存储数据的，只是一个控制作用，所以要考虑到这种情况，再最后的时候，要进行判断以防这种情况
这个手动实现的中序遍历，只要能在中间节点上，那它一定有右孩子，不然右孩子一定是空，因为我们每次找的都是父亲节点不是右孩子的节点
->这人操作符是c++中很特别的一个操作符，编译器对它的实现也很复杂，它看上去像是一个双目运算符，但实际上应该是一个单目运算符，在重载它是只有一个隐式参数this，但它又是不是一个单目运算符，它是一个特殊的单目运算符，因为它的后面要有 一个标识符，它的前面是一个类的指针，这个标识符就是它的类的一个成员，所以说它是一个特殊的单目运算符，它后面的并不是直接定义好的东西，而是一个类的成员，通过前面的类指针可以直接访问它，所以只需要操作前面的类指针就行了，但它又不能少，因为它是一个标识，标识着你要访问哪一个成员，所以在对->进行操作符重载时，它的样子就很奇怪，因为编译器要保证你要访问到的是那成员，又因为你只操作那个指针不能访问到它，因为你不知道要访问谁，，所以你必须通过它定义的->进行访问，那我们重载的是什么，因为我们不能直接获得包含那个成员的类指针，所以我们才进行重载，所以我们的目的是获得到那个成员的类指针，所以说对->的重载就相当于把它改变后编译器自己在后边又添加一个->，如果说重载完后，不是一个类指针，分两种情况进行处理，当重载完后是一个类是，那就去那个类中找操作->的重载，如果没有报错，如果有继续递规上面的过程，直到找到那个类的指针，如果不是类的话就直接报错返回了
map、set等容器的实现，它们的实现有很多共同的地方，也有很多不同的地方，先从共同的地方说起，它们这些容器最主要的功能是查找效率高，是将数据存进来然后再进行查找，所以它们的底层是用红黑树实现，不用AVL树的原因是它的查找效率虽然是所有树中最高的，但它的插入和删除开销很大，要进行多次旋转，所以使用红黑它们的查找时间复杂度相近，但插入和删除的开销相比较很小，所以底层使用红黑树作为核心，然后为这棵树还提供了一个送代器，因为容器一般都是使用送代器进行访问的，直接给一个红黑树的节点就很奇怪，相当于一个封装，而且送代器更加好用和易于理解，不用关心底层的实现，所以插入节点返回两个值，一个是bool一个是iterator，bool是为了表示这个节点有没有插入成功，iterator是表示插入的是哪个结点（这里就体现出了返回送代器的好处拿到之后就可以进行各种操作），所以返回的是一个pair对象，里面存放着一个bool数据和一个iterator，给送代器传参时传一个红黑树的结点就行了，送代器的二个比较不好实现的操作符重载在上面已经做了解释，然后还的一个相同的就是红黑树节点的申请，只需要传给他要放入数据的类型就行了，不同的是，它们存储的数据不同，map存的pair对象，而set存的是一个值，先说map，因为存的是pair对象，但以红黑树这种结构存放数据是可以排序的，所以map用key值作为比较的对象，以它的大小来进行决定顺序，而val可以通过key来找到，所以key就相当于索引，然后set只存放一个值，所以它的key就是val，直接拿来比较就行了，因为只用一个红黑树要实现四个容器，并且它们的比较方式不同，所以就要用仿函数对（）进行重载然后把里面的东西对应成相应的比较对象就可以进行比较了，另外map有一个【】的方法所以就要对【】进行重载，让它最后返回一个可修改的second值，里面还有一个小 技巧 ，因为pair要从两个值但只发过来了一个key值，所以要想一个可以传两个值，但val这个值可以改变的方法，所以val就用一个模板函数代替了，因为它有类型推导的功能，具体之前已在分区2细说过了，然后它们也应该提供各的begin和end接口，需要说的生成的begin和end都是一个iterator对象，这个begin和end也在红黑树内部就有的，直接通过实例化的RBT节点调用给自己就行了，在红黑树内部实现的原因是，只有在红黑树内部用它才是最方便的，可以直接得到，不用在map
通过原生送代器结构体再实例化对象了，因为红黑树插入时本来也返回送代器对象所以有实例化的iterator对象，所以直接有它的接口可用，可以通过红黑树直接得到，如果不写在红黑中在使用它时还是要先通过 红黑树的结点来造它，多此一举，太麻烦了，set的话就是比较map少了个[]接口
map[]重载的原理：
map在进行[]重载时会因为它必须先把key值传进去，但又不知道val值，所以会有一个模板型的函数 ，但这个函数没有函数名，也没有参数，它的类型是模板，这样做的目的就是为了代替val，因为函数可以做类型推导（make_pair就是利用了这一点才实现了真接给pair赋值的功能）
所以，当make_pair在推导val的类型时发现是模板，所以把它的模板就作为类型给传了进去，这时pair对象里面也是一个模板，当pair对象看见传进来的类型也是模板时，把传进来的模板类型给它赋过去，val还是那个函数，这样做之后大家的模板参数都是一样的了，当val那个函数的类型改变时pair对象的类型也会改变，当传进去一个值时，函数看见后知道它的返回值是这个后并不会进入函数体，而是直接做类型推导，推导出这个模板函数的类型，之后val的类型确定了，那pair的类型也就随之改变了，而原来的函数因为已经有返回值，所以就把自己替换为返回值了，这样就完成了在不知道val的情况下，进行传值了
#pragma once #include <iostream> #include <time.h> using namespace std; enum Color { BLACK, RED }; template <class T> struct RBTNode { typedef RBTNode<T> Node; Node* _pLeft = nullptr; Node* _pRight = nullptr; Node* _pParent = nullptr; T _data; Color _color = RED; }; template <class T> struct __TreeIterator { typedef RBTNode<T> Node; typedef Node* pNode; typedef __TreeIterator<T> Self; Node* _node; __TreeIterator(Node* node) :_node(node) {} T& operator * () { return _node->_data; } T* operator -> () { return &(operator*()); } bool operator != (const Self& it) { return _node != it._node; } Self& operator ++ () //要找到父亲节点的孩子不是它的右孩子 { if (_node->_pRight) { _node = _node->_pRight; while (_node->_pLeft) { _node = _node->_pLeft; } } else { pNode parent = _node->_pParent; while (_node == parent->_pRight) { _node = parent; parent = parent->_pParent; } if (_node->_pRight != parent) { _node = parent; } } return *this; } Self operator ++ (int) { Self tmp(*this); ++(*this); return tmp; } Self& operator -- () { if (_node->_pLeft) { _node = _node->_pLeft; while (_node->_pRight) { _node = _node->_pRight; } } else { pNode parent = _node->_pParent; while (_node = parent->_pLeft) { _node = parent; parent = parent->_pParent; } if (parent->_pLeft != parent) { _node = parent; } } return *this; } Self operator -- (int) { Self tmp(*this); --(*this); return tmp; } }; template <class K, class V, class KeyOfValue> class RBTree { public: typedef RBTNode<V> Node; typedef __TreeIterator<V> Iterator; typedef Node* pNode; typedef Node* PNode; RBTree() { _header = new Node; _header->_pParent = nullptr; _header->_pLeft = _header; _header->_pRight = _header; } Iterator begin() { return Iterator(_header->_pLeft); } Iterator end() { return Iterator(_header); } Iterator rbegin() { return Iterator(_header->_right); } Iterator rend() { return Iterator(_header); } pair<Iterator, bool> Insert(const V& data) { if (_header->_pParent == nullptr) { pNode root = new Node; root->_data = data; root->_color = BLACK; root->_pParent = _header; _header->_pParent = root; _header->_pLeft = root; _header->_pRight = root; return make_pair(Iterator(root), true); } KeyOfValue keyofvalue; pNode cur = _header->_pParent; pNode parent = nullptr; while (cur) { if (keyofvalue(data) > keyofvalue(cur->_data)) { parent = cur; cur = cur->_pRight; } else if (keyofvalue(data) < keyofvalue(cur->_data)) { parent = cur; cur = cur->_pLeft; } else { return make_pair(Iterator(cur), false); } } pNode newNode = new Node; newNode->_data = data; if (keyofvalue(data) > keyofvalue(parent->_data)) { parent->_pRight = newNode; } else { parent->_pLeft = newNode; } newNode->_pParent = parent; cur = newNode; while (cur != _header->_pParent && cur->_pParent->_color == RED) { pNode parent = cur->_pParent; pNode gParent = parent->_pParent; if (gParent->_pLeft == parent) { pNode uncle = gParent->_pRight; if (uncle && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; gParent->_color = RED; cur = gParent; } else { if (cur == parent->_pRight) { RotateL(parent); swap(parent, cur); } RotateR(gParent); parent->_color = BLACK; gParent->_color = RED; break; } } else { if (gParent->_pRight == parent) { pNode uncle = gParent->_pLeft; if (uncle && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; gParent->_color = RED; cur = gParent; } else { if (cur == parent->_pLeft) { RotateR(parent); swap(parent, cur); } RotateL(gParent); parent->_color = BLACK; gParent->_color = RED; break; } } } } _header->_pParent->_color == BLACK; _header->_pLeft = leftMost(); _header->_pRight = rightMost(); return make_pair(Iterator(newNode), true); } void RotateR(Node* parent) { Node* subL = parent->_pLeft; Node* subLR = subL->_pRight; //单向连接subL,parent,subLR subL->_pRight = parent; parent->_pLeft = subLR; //向上连接subLR if (subLR) { subLR->_pParent = parent; } //subL, parent->parent双向连接 if (parent != _header->_pParent) { Node* gParent = parent->_pParent; if (gParent->_pLeft == parent) { gParent->_pLeft = subL; } else { gParent->_pRight = subL; } subL->_pParent = gParent; } else { subL->_pParent = _header; _header->_pParent = subL; } //向上连接parent,subL parent->_pParent = subL; } void RotateL(Node* parent) { Node* subR = parent->_pRight; Node* subRL = subR->_pLeft; subR->_pLeft = parent; parent->_pRight = subRL; if (subRL) { subRL->_pParent = parent; } if (parent != _header->_pParent) { Node* gParent = parent->_pParent; if (gParent->_pLeft == parent) { gParent->_pLeft = subR; } else { gParent->_pRight = subR; } subR->_pParent = gParent; } else { subR->_pParent = _header; _header->_pParent = subR; } parent->_pParent = subR; } pNode leftMost() { pNode cur = _header->_pParent; while (cur && cur->_pLeft) { cur = cur->_pLeft; } return cur; } pNode rightMost() { pNode cur = _header->_pParent; while (cur && cur->_pRight) { cur = cur->_pRight; } return cur; } private: pNode _header; }; #include "testRBT.hpp" using namespace std; template <class K, class V> class Map { public: struct MapKeyOfValue { const K& operator () (const pair<K, V>& data) { return data.first; } }; typedef typename RBTree<K, pair<K, V>, MapKeyOfValue>::Iterator Iterator; pair<Iterator, bool> Insert(const pair<K, V>& data) { return _t.Insert(data); } Iterator begin() { return _t.begin(); } Iterator end() { return _t.end(); } V& operator [] (const K& key) { return (*(Insert(make_pair(key, V()))).first).second; } private: RBTree<K, pair<K, V>, MapKeyOfValue> _t; }; template <class K> class Set { public: struct SetKeyOfValue { const K& operator () (const K& data) { return data; } }; typedef typename RBTree<K, K, SetKeyOfValue>::Iterator Iterator; pair<Iterator, bool> Insert(const K& key) { return _t.Insert(key); } Iterator begin() { return _t.begin(); } Iterator end() { return _t.end(); } private: RBTree<K, K, SetKeyOfValue> _t; }; void testMapSet() { Map<int, int> m; m.Insert(make_pair(0, 0)); m.Insert(make_pair(5, 5)); m.Insert(make_pair(9, 9)); m.Insert(make_pair(1, 1)); auto it = m.begin(); while (it != m.end()) { cout << it->first << "--->" << it->second << endl; it++; } /*Set<int> s; s.Insert(4); s.Insert(5); s.Insert(2); s.Insert(66); s.Insert(43); auto it = s.begin(); while (it != s.end()) { cout << *it << endl; it++; }*/ } int main() { testMapSet(); return 0; } - 版权声明：文章来源于网络采集，版权归原创者所有，均已注明来源，如未注明可能来源未知，如有侵权请联系管理员删除。
