分析注map/set底层都是红黑树实现的。可能有的人会想set是key的map是key/value的那底层难道这两个容器分别写一个红黑树吗不是的经过前人对源码的剖析大佬将红黑树搞成了一个类模板上层是set和map各自两个类模板通过传不同的模板参数给底层的红黑树模板达到一个复用的效果感觉跟stack/queue的容器适配器实现思路很像。迭代器实现思路迭代器主要是要解决两个重要的部分就是operator和operator--。先说吧。首先要明确set/map的迭代器在便利的时候走的是中序也就意味着begin()是整棵数的最左结点end()就为空因为end()表示最后一个有效位置的下一个位置。一次就走到中序便利的下一个结点处中序便利是左根右把当前结点看成根的话之后都到的就是其右子树的最左结点。如下图10结点之后到15结点30结点之后到35结点。那如果右子树为空呢看下图加入现在便利到15结点其右子树为空这就表示以10结点为根的这棵子树已经全部便利完了因为中序的顺序是左根右嘛接下来要去看下图中蓝色框出的那棵子树的根结点在其父结点也就是18结点的左边还是右边如果是左边的话之后就来到18结点如果在右边假设现在便利到50结点其右子树为空且右子树在以40结点为根的整棵子树的右边该子树便利完以40结点为根的子树在以30为根的子树的右边说明以30为根的子树便利完了看下图中紫色框出部分的子树的根结点30就是在18结点的右边就说明整棵树已经走完了。说的有点复杂其实意思就是严格遵循左根右的便利原则去考虑问题。右子树便利完了就说明整棵子树便利完了看看整棵子树在根结点的左还是右在左就继续从根结点开始便利在右就说明整棵树就便利完了。--的思路就跟完全相反了右根左具体就不细讲了在课件上有代码贴出来了。key不能修改的问题最简单的一种方式就是加上const从底层规避掉能否修改的问题。operator[]之前博客里说过这个是怎么实现的本质就是复用insertinsert的返回值是个pair插入成功就返回true插入失败就返回false但iterator自始至终都是指向着key所在的结点。总结整体的书写逻辑根据本文最开始列出的那几个一个个板块来。总体而言上层的set/map就是一个躯壳底层最内核的东西就是红黑树。set.h#pragma once #includeRBTree.h namespace xxc { templateclass K class set { //仿函数 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } pairiterator, bool insert(const K k) { return _t.Insert(k); } private: RBTreeK, const K, SetKeyOfT _t; }; }map.h#pragma once #includeRBTree.h namespace xxc { templateclass K, class V class map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first;//返回key } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }RBTree.h#pragma once #includeiostream using namespace std; enum Color { RED, BLACK }; //上层传下来是key就是key是pair就是pair templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; Color _col; RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { } }; templateclass T, class Ref, class Ptr struct TreeIterator { typedef RBTreeNodeT Node; typedef TreeIteratorT, 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) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } Self operator() { //如果右子树在就走到中序便利的第一个(右子树的最左结点) if (_node-_right) { Node* min _node-_right; while (min-_left) { min min-_left; } _node min; } //如果右子树不在就退回去 //次数必须结合课件里的图去对照着看 else { Node* cur _node; Node* parent cur-_parent; //如果父结点存在并且当前子树在根节点的右边则说明当前子树已经便利完 //这里真得带着课件里的图一起看有点说不清楚 //把博客里贴着的那张图50结点当成cur40结点当成parent带着代码一点点走 //你可以理解为这里是从最小的那棵子树开始判断是不是根的右子树一直到整棵树 while (parent cur parent-_right) { cur parent; parent parent-_parent; } //如果整棵树都走完了则parent为nullptr_node赋值为nullptr //如果某一棵子树走完了相当于是左根右的左走完了继续走根 //此时parent就为新子树的根。 _node parent; } return *this; } }; //T表示的就是set里的key或者map里的key/value也就是pair //由于set和map共用的RBTreeKeyOfT获取的就是set里的key或者map里的key方便下边Insert里的比较逻辑 templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef TreeIteratorT, T, T* Iterator; typedef TreeIteratorT, const T, const T* ConstIterator; Iterator Begin() { Node* min _root; //有可能为空树此时Begin就为nullptr while (min min-_left) { min min-_left; } return Iterator(min); } Iterator End() { return Iterator(nullptr); } //data有可能是key有可能是pair看上层调用的时候传过来的是什么 pairIterator, bool Insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; return { Iterator(_root), true }; } KeyOfT kot; Node* parent nullptr; Node* cur _root; 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 { Iterator(cur), false }; } } cur new Node(data); Node* newnode cur;//这里要保存一下因为下边调整颜色的时候cur会往上走会变化 cur-_col RED; if (kot(data) kot(parent-_data)) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; while (parent parent-_col RED) { Node* g parent-_parent; if (g-_left parent) { Node* u g-_right; if (u u-_col RED) { parent-_col BLACK; u-_col BLACK; g-_col RED; cur g; parent cur-_parent; } else { if (cur parent-_left) { RotateR(g); parent-_col BLACK; g-_col RED; } else { RotateL(parent); RotateR(g); cur-_col BLACK; g-_col RED; } break; } } else { Node* u g-_left; if (u u-_col RED) { parent-_col BLACK; u-_col BLACK; g-_col RED; cur g; parent cur-_parent; } else { if (cur parent-_right) { RotateL(g); parent-_col BLACK; g-_col RED; } else { RotateR(parent); RotateL(g); cur-_col BLACK; g-_col RED; } break; } } } _root-_col BLACK; return { Iterator(newnode), true }; } //Find只要传keyRBTree第一个模板参数在这里派上了用处 Node* Find(const K key) { KeyOfT kot; Node* cur _root; while (cur) { if (kot(cur-data) key) { cur cur-_right; } else if (kot(cur-data) key) { cur cur-_left; } else { return cur; } } return nullptr; } private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } } void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parent _root) { _root subR; subR-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } } private: Node* _root nullptr; };测试代码#define _CRT_SECURE_NO_WARNINGS 1 #includeset.h #includemap.h #includeiostream #includevector #includestring using namespace std; void test_set() { xxc::setint s; s.insert(4); s.insert(1); s.insert(2); s.insert(12); s.insert(22); s.insert(2223); s.insert(-2); s.insert(0); xxc::setint::iterator it s.begin(); while (it ! s.end()) { // *it 1; cout *it ; it; } cout endl; } void test_map() { xxc::mapstring, string dict; dict.insert({ sort, 排序 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); dict[left] 左边剩余; // 修改 dict[insert] 插入; // 插入修改 dict[string]; // 插入 xxc::mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { // 不能修改first可以修改second //it-first x; it-second x; cout it-first : it-second endl; it; } cout endl; } int main() { test_set(); test_map(); return 0; }
分析注map/set底层都是红黑树实现的。可能有的人会想set是key的map是key/value的那底层难道这两个容器分别写一个红黑树吗不是的经过前人对源码的剖析大佬将红黑树搞成了一个类模板上层是set和map各自两个类模板通过传不同的模板参数给底层的红黑树模板达到一个复用的效果感觉跟stack/queue的容器适配器实现思路很像。迭代器实现思路迭代器主要是要解决两个重要的部分就是operator和operator--。先说吧。首先要明确set/map的迭代器在便利的时候走的是中序也就意味着begin()是整棵数的最左结点end()就为空因为end()表示最后一个有效位置的下一个位置。一次就走到中序便利的下一个结点处中序便利是左根右把当前结点看成根的话之后都到的就是其右子树的最左结点。如下图10结点之后到15结点30结点之后到35结点。那如果右子树为空呢看下图加入现在便利到15结点其右子树为空这就表示以10结点为根的这棵子树已经全部便利完了因为中序的顺序是左根右嘛接下来要去看下图中蓝色框出的那棵子树的根结点在其父结点也就是18结点的左边还是右边如果是左边的话之后就来到18结点如果在右边假设现在便利到50结点其右子树为空且右子树在以40结点为根的整棵子树的右边该子树便利完以40结点为根的子树在以30为根的子树的右边说明以30为根的子树便利完了看下图中紫色框出部分的子树的根结点30就是在18结点的右边就说明整棵树已经走完了。说的有点复杂其实意思就是严格遵循左根右的便利原则去考虑问题。右子树便利完了就说明整棵子树便利完了看看整棵子树在根结点的左还是右在左就继续从根结点开始便利在右就说明整棵树就便利完了。--的思路就跟完全相反了右根左具体就不细讲了在课件上有代码贴出来了。key不能修改的问题最简单的一种方式就是加上const从底层规避掉能否修改的问题。operator[]之前博客里说过这个是怎么实现的本质就是复用insertinsert的返回值是个pair插入成功就返回true插入失败就返回false但iterator自始至终都是指向着key所在的结点。总结整体的书写逻辑根据本文最开始列出的那几个一个个板块来。总体而言上层的set/map就是一个躯壳底层最内核的东西就是红黑树。set.h#pragma once #includeRBTree.h namespace xxc { templateclass K class set { //仿函数 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } pairiterator, bool insert(const K k) { return _t.Insert(k); } private: RBTreeK, const K, SetKeyOfT _t; }; }map.h#pragma once #includeRBTree.h namespace xxc { templateclass K, class V class map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first;//返回key } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; iterator begin() { return _t.Begin(); } iterator end() { return _t.End(); } pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }RBTree.h#pragma once #includeiostream using namespace std; enum Color { RED, BLACK }; //上层传下来是key就是key是pair就是pair templateclass T struct RBTreeNode { T _data; RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; Color _col; RBTreeNode(const T data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { } }; templateclass T, class Ref, class Ptr struct TreeIterator { typedef RBTreeNodeT Node; typedef TreeIteratorT, 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) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } Self operator() { //如果右子树在就走到中序便利的第一个(右子树的最左结点) if (_node-_right) { Node* min _node-_right; while (min-_left) { min min-_left; } _node min; } //如果右子树不在就退回去 //次数必须结合课件里的图去对照着看 else { Node* cur _node; Node* parent cur-_parent; //如果父结点存在并且当前子树在根节点的右边则说明当前子树已经便利完 //这里真得带着课件里的图一起看有点说不清楚 //把博客里贴着的那张图50结点当成cur40结点当成parent带着代码一点点走 //你可以理解为这里是从最小的那棵子树开始判断是不是根的右子树一直到整棵树 while (parent cur parent-_right) { cur parent; parent parent-_parent; } //如果整棵树都走完了则parent为nullptr_node赋值为nullptr //如果某一棵子树走完了相当于是左根右的左走完了继续走根 //此时parent就为新子树的根。 _node parent; } return *this; } }; //T表示的就是set里的key或者map里的key/value也就是pair //由于set和map共用的RBTreeKeyOfT获取的就是set里的key或者map里的key方便下边Insert里的比较逻辑 templateclass K, class T, class KeyOfT class RBTree { typedef RBTreeNodeT Node; public: typedef TreeIteratorT, T, T* Iterator; typedef TreeIteratorT, const T, const T* ConstIterator; Iterator Begin() { Node* min _root; //有可能为空树此时Begin就为nullptr while (min min-_left) { min min-_left; } return Iterator(min); } Iterator End() { return Iterator(nullptr); } //data有可能是key有可能是pair看上层调用的时候传过来的是什么 pairIterator, bool Insert(const T data) { if (_root nullptr) { _root new Node(data); _root-_col BLACK; return { Iterator(_root), true }; } KeyOfT kot; Node* parent nullptr; Node* cur _root; 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 { Iterator(cur), false }; } } cur new Node(data); Node* newnode cur;//这里要保存一下因为下边调整颜色的时候cur会往上走会变化 cur-_col RED; if (kot(data) kot(parent-_data)) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; while (parent parent-_col RED) { Node* g parent-_parent; if (g-_left parent) { Node* u g-_right; if (u u-_col RED) { parent-_col BLACK; u-_col BLACK; g-_col RED; cur g; parent cur-_parent; } else { if (cur parent-_left) { RotateR(g); parent-_col BLACK; g-_col RED; } else { RotateL(parent); RotateR(g); cur-_col BLACK; g-_col RED; } break; } } else { Node* u g-_left; if (u u-_col RED) { parent-_col BLACK; u-_col BLACK; g-_col RED; cur g; parent cur-_parent; } else { if (cur parent-_right) { RotateL(g); parent-_col BLACK; g-_col RED; } else { RotateR(parent); RotateL(g); cur-_col BLACK; g-_col RED; } break; } } } _root-_col BLACK; return { Iterator(newnode), true }; } //Find只要传keyRBTree第一个模板参数在这里派上了用处 Node* Find(const K key) { KeyOfT kot; Node* cur _root; while (cur) { if (kot(cur-data) key) { cur cur-_right; } else if (kot(cur-data) key) { cur cur-_left; } else { return cur; } } return nullptr; } private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } } void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parent _root) { _root subR; subR-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } } private: Node* _root nullptr; };测试代码#define _CRT_SECURE_NO_WARNINGS 1 #includeset.h #includemap.h #includeiostream #includevector #includestring using namespace std; void test_set() { xxc::setint s; s.insert(4); s.insert(1); s.insert(2); s.insert(12); s.insert(22); s.insert(2223); s.insert(-2); s.insert(0); xxc::setint::iterator it s.begin(); while (it ! s.end()) { // *it 1; cout *it ; it; } cout endl; } void test_map() { xxc::mapstring, string dict; dict.insert({ sort, 排序 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); dict[left] 左边剩余; // 修改 dict[insert] 插入; // 插入修改 dict[string]; // 插入 xxc::mapstring, string::iterator it dict.begin(); while (it ! dict.end()) { // 不能修改first可以修改second //it-first x; it-second x; cout it-first : it-second endl; it; } cout endl; } int main() { test_set(); test_map(); return 0; }
