三、红黑树迭代器
map和set的迭代器的实现其实本质上是红黑树迭代器的实现，迭代器的实现需要定义模板类型、模板类型引用、模板类型指针。
1.红黑树中迭代器重命名
在红黑树中重命名模板类型、模板类型引用、模板类型指针，定义为public，外部就能使用iterator了：
1. template<class K, class T, class KeyOfT> 2. class RBTree 3. { 4. typedef RBTreeNode<T> Node; 5. 6. public: 7. typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针 8. 9. //红黑树函数... 10. 11. private: 12. Node* _root; 13. };
2.正向迭代器定义
红黑树的迭代器的本质是对节点指针进行封装，所以迭代器中只有封装红黑树节点指针这一个成员变量 。正向迭代器：
1. template<class T,class Ref,class ptr> 2. struct __TreeIterator 3. { 4. typedef RBTreeNode<T> Node; 5. typedef __TreeIterator<T, Ref, ptr> Self; 6. 7. Node* _node;//成员变量 8. 9. };
3.迭代器构造
用节点指针构造正向迭代器：
1. //构造函数 2. __TreeIterator(Node* node) 3. :_node(node) 4. {}
4.正向迭代器重载*
Ref对正向迭代器解引用，返回节点数据引用：
1. //* 解引用，返回节点数据 2. Ref Operator*() 3. { 4. return _node->_data; 5. }
5.正向迭代器重载->
Ptr对正向迭代器使用->，返回节点数据指针：
1. //-> 返回节点数据地址 2. Ptr Operator->() 3. { 4. return &_node->_data; 5. }
6.正向迭代器重载==
判断节点是否相同
1. //判断两个迭代器是否相同 2. bool operator==(const Self& s) 3. { 4. return _node == s._node;//判断节点是否相同 5. }
7.正向迭代器重载!=
判断节点是否不同
1. //判断两个迭代器是否不同 2. bool operator!=(const Self& s) 3. { 4. return _node != s._node;//判断节点是否不同 5. }
8.正向迭代器++
①当节点的右子树不为空时，++就要走到右子树的最左节点
②当节点的右子树为空时，++就要走到节点的父亲
1. //红黑树迭代器的++也就是红黑树的++ 2. Self operator++() 3. { 4. //1.右子树不为空 5. if (_node->_right) 6. { 7. //下一个访问的是右树的中序第一个节点（即右子树最左节点）。 8. Node* left = _node->_right; 9. 10. //找最左节点 11. while (left->_left) 12. { 13. left = left->_left; 14. } 15. _node = left; 16. } 17. else//2.右子树为空，下一个访问的就是当前节点的父亲 18. { 19. Node* cur = _node; 20. Node* parent = cur->_parent; 21. while (parent && cur == parent->_right) 22. { 23. cur = cur->_parent; 24. parent = parent->_parent; 25. } 26. _node = parent; 27. } 28. 29. return *this; 30. } 31. };
9.正向迭代器--
①当节点的左子树不为空时，++就要走到左子树的最右节点
②当节点的左子树为空时，++就要走到节点的父亲
1. //红黑树迭代器的--也就是红黑树的-- 2. Self operator--() 3. { 4. //1.左子树不为空 5. if (_node->_left) 6. { 7. //下一个访问的是左树的中序左后节点（即做子树最右节点）。 8. Node* right = _node->_left; 9. 10. //找最右节点 11. while (right->_right) 12. { 13. right = right->_right; 14. } 15. _node = right; 16. } 17. else//2.左子树为空，下一个访问的就是当前节点的父亲 18. { 19. Node* cur = _node; 20. Node* parent = cur->_parent; 21. while (parent && cur == parent->_left) 22. { 23. cur = cur->_parent; 24. parent = parent->_parent; 25. } 26. _node = parent; 27. } 28. 29. return *this; 30. }
10.红黑树中实现迭代器
实现begin( )找最左节点，end( )最后一个节点的下一个位置
1. template<class K, class T, class KeyOfT> 2. class RBTree 3. { 4. typedef RBTreeNode<T> Node; 5. 6. public: 7. typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针 8. 9. //找最左节点 10. iterator begin() 11. { 12. Node* left = _root; 13. while (left && left->_left) 14. { 15. left = left->_left; 16. } 17. 18. return iterator(left)//返回最左节点的正向迭代器 19. } 20. 21. //结束 22. iterator end() 23. { 24. return iterator(nullptr); 25. } 26. 27. private: 28. Node* _root; 29. };
四、set模拟实现
调用红黑树对应接口实现set，插入和查找函数返回值当中的节点指针改为迭代器:
1. #pragma once 2. #include "RBTree.h" 3. namespace delia 4. { 5. template<class K> 6. class set 7. { 8. //仿函数，获取set的key 9. struct SetKeyOfT 10. { 11. const K& operator()(const K& key) 12. { 13. return key; 14. } 15. }; 16. public: 17. typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; 18. 19. //迭代器开始 20. iterator begin() 21. { 22. return _t.begin(); 23. } 24. 25. //迭代器结束 26. iterator end() 27. { 28. return _t.end(); 29. } 30. 31. //插入函数 32. pair<iterator,bool> insert(const K& key) 33. { 34. 35. return _t.Insert(key); 36. } 37. 38. //查找 39. iterator find(const K& key) 40. { 41. return _t.find(key); 42. } 43. private: 44. RBTree<K, K, SetKeyOfT> _t; 45. }; 46. }
五、map模拟实现
调用红黑树对应接口实现map，插入和查找函数返回值当中的节点指针改为迭代器，增加operator[ ]的重载:
1. #pragma once 2. #include "RBTree.h" 3. namespace delia 4. { 5. template<class K, class V> 6. class map 7. { 8. //仿函数，获取map的first 9. struct MapKeyOfT 10. { 11. const K& operator()(const pair<const K, V>& kv) 12. { 13. return kv.first; 14. } 15. }; 16. public: 17. typedef typename RBTree<K, K, MapKeyOfT>::iterator iterator; 18. 19. //迭代器开始 20. iterator begin() 21. { 22. return _t.begin(); 23. } 24. 25. //迭代器结束 26. iterator end() 27. { 28. return _t.end(); 29. } 30. 31. //插入 32. pair<iterator, bool> insert(const pair<const K, V>& kv) 33. { 34. return _t.Insert(kv); 35. } 36. 37. //重载operator[] 38. V& operator[](const K& key) 39. { 40. pair<iterator, bool> ret = insert(make_pair(key, V())); 41. iterator it = ret.first; 42. return it->second; 43. } 44. 45. //查找 46. iterator find(const K& key) 47. { 48. return _t.find(key); 49. } 50. 51. private: 52. RBTree<K, pair<const K, V>, MapKeyOfT> _t; 53. }; 54. }
