增加红黑树迭代器的代码
首先我们可以复用上一节写出的红黑树代码,在原有基础上略作修改即可,这里我们只对map和set的迭代器功能实现做讲解,并不是完全实现,目的是为了深化学习map和set的底层原理
1. map和set通用模板迭代器结构体定义
template<class T, class Ref, class Ptr> struct __RBTreeIterator { typedef RBTreeNode<T> Node; typedef __RBTreeIterator<T, Ref, Ptr> Self; Node* _node; };
这段代码是为了同时实现 std::map 和 std::set 的红黑树结构而定义的迭代器。在STL中， std::map 和 std::set 都使用红黑树作为底层数据结构，但它们之间有一些差异，主要是在元素类型和键-值对之间。
这个迭代器定义的目的是为了在不重复实现两种不同容器的迭代器的情况下，实现红黑树的通用迭代器，以便它可以同时用于 std::map 和 std::set。让我解释一下为什么需要这样的定义：
- 通用性：这个迭代器的定义使得它可以适用于不同的数据类型
T，无论是std::map的键值对还是std::set的元素。这种通用性是非常有价值的，因为它允许你在不同的上下文中使用相同的迭代器。 - 代码重用：通过使用通用迭代器，STL可以避免在不同容器的迭代器之间重复编写相似的代码。这简化了STL的实现，减少了代码冗余。
- 一致性：STL追求一致性，希望用户可以像使用
std::map的迭代器一样使用std::set的迭代器，或者反之。这使得STL更容易理解和使用。
因此，这个迭代器定义的目的是为了实现通用性、代码重用和一致性，以提供更好的STL体验。在STL中，通常会看到这种类型的通用迭代器，以简化不同容器的实现。
2. 迭代器拷贝构造
__RBTreeIterator(Node* node) :_node(node) {}
这个构造函数是 __RBTreeIterator 迭代器的构造函数，它接受一个指向红黑树节点的指针作为参数，并将这个指针存储在 _node 成员变量中。
构造函数的主要目的是初始化迭代器的状态，使其指向红黑树中的特定节点，从而使迭代器能够正确地遍历红黑树中的元素。在迭代器创建时，你可以传入一个节点指针，它将成为迭代器的起始位置。
这种构造函数的设计允许你在创建迭代器时指定起始位置，以便从红黑树中的特定节点开始遍历。这在实现红黑树的迭代器时是常见的设计，因为你可能希望从根节点、某个特定节点或其他位置开始遍历树。
3. 迭代器解引用重载
Ref operator*() { return _node->_data; }
这个 operator* 函数是迭代器的解引用操作符重载函数。它的目的是返回当前迭代器指向的元素的引用，允许你通过迭代器来访问元素的值。
在这个具体的实现中，_node->_data 是红黑树节点中存储的元素值，它的类型是 T。operator* 函数返回的是这个元素值的引用，所以你可以通过迭代器来读取或修改当前节点的值。
通常情况下，解引用操作符重载允许你以类似于指针的方式来访问迭代器指向的对象，这使得使用迭代器遍历容器时，你可以像访问容器元素一样来访问数据，增强了代码的可读性和易用性。在STL和C++中，迭代器的行为通常模仿指针的行为，因此你可以使用类似于指针的语法来操作元素。
4. 迭代器箭头重载
Ptr operator->() { return &_node->_data; }
这个 operator-> 函数是迭代器的箭头成员访问操作符重载函数。它的目的是返回一个指向当前迭代器指向的元素的指针，以便你可以通过迭代器来访问元素的成员。
在这个具体的实现中，_node->_data 是红黑树节点中存储的元素值，它的类型是 T。operator-> 函数返回的是一个指向这个元素值的指针，所以你可以使用箭头操作符来访问元素的成员变量或调用其成员函数。
这个操作符的重载允许你以一种更直接的方式来访问迭代器指向的元素的成员。这在需要访问元素的内部数据或调用其方法时非常有用。
例如，如果你的元素是一个自定义类的对象，你可以使用 -> 操作符来访问该对象的成员函数，就像你正在操作该对象一样。这提供了一种更自然、更便捷的访问元素的方式。
5. 迭代器不等于重载
bool operator!=(const Self& s) const { return _node != s._node; }
这个 operator!= 函数是不等于运算符的重载函数。它的目的是比较当前迭代器和另一个迭代器 s 是否不相等。
在这个具体的实现中，它比较了 _node 成员变量，如果两个迭代器的 _node 不相等，就返回 true，表示它们不相等；否则，返回 false，表示它们相等。
这个操作符的重载使得你可以使用不等于运算符 != 来比较两个迭代器，以确定它们是否指向不同的位置。这对于循环遍历容器中的元素或判断迭代器是否达到容器末尾非常有用。通常情况下，你可以使用这个操作符来控制循环的终止条件。
6. 迭代器判断相等重载
bool operator==(const Self& s) const { return _node == s._node; }
这个 operator== 函数是等于运算符的重载函数。它的目的是比较当前迭代器和另一个迭代器 s 是否相等。
在这个具体的实现中，它比较了 _node 成员变量，如果两个迭代器的 _node 相等，就返回 true，表示它们相等；否则，返回 false，表示它们不相等。
这个操作符的重载使得你可以使用等于运算符 == 来比较两个迭代器，以确定它们是否指向相同的位置。这对于检查迭代器是否相等以及判断是否达到容器末尾非常有用。通常情况下，你可以使用这个操作符来执行迭代器的相等性检查。
7. 迭代器++重载
Self& operator++() { if (_node->_right) { // 下一个就是右子树的最左节点 Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; } else { // 找祖先里面孩子不是祖先的右的那个 Node* parent = _node->_parent; Node* cur = _node; while (parent && cur == parent->_right) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }
这个 operator++ 函数是前置自增运算符的重载函数，用于使迭代器指向下一个元素。在红黑树的迭代器中，它实现了迭代器的前进操作。
这个函数的工作方式如下：
- 如果当前节点的右子树存在，迭代器将被移动到右子树的最左节点。这是因为在红黑树中，右子树的最左节点是比当前节点大的下一个节点。
- 如果当前节点没有右子树，迭代器将向上移动到祖先节点，直到找到一个祖先节点，它的右子节点不等于当前节点。这是因为在红黑树中，如果当前节点没有右子树，下一个节点要么是它的父节点，要么是它的某个祖先节点的左子节点。
这个函数的目的是使迭代器指向下一个元素，以实现对红黑树的顺序遍历。在STL中，前置自增操作符通常用于移动迭代器到容器中的下一个元素。
8. 迭代器–重载
Self& operator--() { if (_node->_left) { // 下一个是左子树的最右节点 Node* right = _node->_left; while (right->_right) { right = right->_right; } _node = right; } else { // 孩子不是父亲的左的那个祖先 Node* parent = _node->_parent; Node* cur = _node; while (parent && cur == parent->_left) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } return *this; }
这个 operator-- 函数是前置自减运算符的重载函数，用于使迭代器指向前一个元素。在红黑树的迭代器中，它实现了迭代器的后退操作。
这个函数的工作方式与 operator++ 函数相似，但是方向相反：
- 如果当前节点的左子树存在，迭代器将被移动到左子树的最右节点。这是因为在红黑树中，左子树的最右节点是比当前节点小的上一个节点。
- 如果当前节点没有左子树，迭代器将向上移动到祖先节点，直到找到一个祖先节点，它的左子节点不等于当前节点。这是因为在红黑树中，如果当前节点没有左子树，上一个节点要么是它的父节点，要么是它的某个祖先节点的右子节点。
这个函数的目的是使迭代器指向前一个元素，以实现对红黑树的逆序遍历。在STL中，前置自减操作符通常用于向前移动迭代器到容器中的前一个元素。
修改红黑树结构体的成员及成员函数
1. 修改红黑树结构体的成员定义
template<class K, class T, class KeyOfT> struct RBTree { typedef RBTreeNode<T> Node; public: typedef __RBTreeIterator<T, T&, T*> iterator; private: Node* _root = nullptr; };
这里就是在红黑树结构体中将模板迭代器重命名为iterator
2. 增加迭代器begin()和end()函数
iterator begin() { Node* left = _root; while (left && left->_left) { left = left->_left; } return iterator(left); } iterator end() { return iterator(nullptr); }
这两个函数是用于创建红黑树迭代器的成员函数，通常用于在你的红黑树容器类中实现迭代器的 begin() 和 end() 函数。
begin()函数用于返回指向红黑树中最小元素的迭代器。它通过从根节点开始，沿着左子树的路径一直向下移动，直到找到最左边的叶子节点，这个叶子节点就是最小的元素。然后它创建一个迭代器对象，将这个最小元素的节点指针传递给迭代器的构造函数，最后返回这个迭代器。end()函数用于返回表示红黑树结束位置的迭代器。通常情况下，结束位置是一个空指针（nullptr）。这个函数直接创建一个迭代器对象，将空指针传递给迭代器的构造函数，然后返回这个迭代器。
这两个函数的实现使得你可以使用标准的迭代器语法来遍历红黑树中的元素。例如，你可以使用 begin() 获取指向第一个元素的迭代器，然后使用 end() 获取表示结束位置的迭代器，然后在循环中递增迭代器以遍历整个红黑树。这与STL容器的迭代器用法非常相似，使得在处理红黑树时更加方便和统一。
3. 修改红黑树Insert函数
pair<iterator, bool> Insert(const T& data) { KeyOfT kot; if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); } Node* parent = nullptr; Node* cur = _root; while (cur) { if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else { return make_pair(iterator(cur), false); } } cur = new Node(data); Node* newnode = cur; cur->_col = RED; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfater = parent->_parent; assert(grandfater); assert(grandfater->_col == BLACK); // 关键看叔叔 if (parent == grandfater->_left) { Node* uncle = grandfater->_right; // 情况一 : uncle存在且为红，变色+继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; }// 情况二+三：uncle不存在 + 存在且为黑 else { // 情况二：右单旋+变色 if (cur == parent->_left) { RotateR(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：左右单旋+变色 // g // p u // c RotateL(parent); RotateR(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } else // (parent == grandfater->_right) { Node* uncle = grandfater->_left; // 情况一 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfater->_col = RED; // 继续往上处理 cur = grandfater; parent = cur->_parent; } else { // 情况二：左单旋+变色 if (cur == parent->_right) { RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // 情况三：右左单旋+变色 RotateR(parent); RotateL(grandfater); cur->_col = BLACK; grandfater->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); }
修改后它的返回值是一个 pair，其中包含一个迭代器和一个布尔值，用于表示插入是否成功。
函数的主要步骤：
- 首先，检查红黑树是否为空，如果是空的，直接创建一个新节点
_root，将其染成黑色（根节点必须是黑色），然后返回一个包含指向新节点的迭代器和true的pair，表示插入成功。 - 如果红黑树不为空，则进入插入元素的循环。在循环中，首先通过
KeyOfT对象kot来比较当前节点和要插入的数据，以确定应该将新节点插入到左子树还是右子树，或者是否已经存在相同的数据。如果找到相同的数据，函数会返回一个包含指向相同数据的迭代器和false的pair，表示插入失败。 - 如果没有找到相同的数据，创建一个新节点
cur，将其染成红色，然后将其插入到适当的位置，这与标准的二叉搜索树插入操作相似。 - 插入完成后，函数进入红黑树修正循环，以确保满足红黑树的性质。在修正循环中，它首先检查当前节点的父节点和祖父节点的颜色，以确定需要采取哪种修正操作。具体的修正操作包括颜色变换和旋转操作，以保持红黑树的平衡性和性质。
- 最后，将根节点
_root的颜色强制设置为黑色，以确保根节点始终为黑色。然后返回一个包含指向新插入节点的迭代器和true的pair，表示插入成功。
这个函数的实现遵循红黑树的插入规则和修正策略，以保持红黑树的平衡和性质。它返回一个迭代器，可以用于访问新插入的元素，以及一个布尔值，指示插入是否成功。
