SGI STL红黑树中迭代器的边界值分析

前言

　　一段程序最容易出错的就是在判断或者是情况分类的边界地方，所以，应该对于许多判断或者是情况分类的边界要格外的注意。下面，就分析下STL中红黑树的迭代器的各种边界情况。(注意：分析中STL使用的版本是SGI STL，由于不同的版本的STL具体实现细节不一样，所以可能会有出入)。

一、begin()获取第一个迭代器的自减

　　begin()函数获取的是一个容器的首迭代器，指向容器中的第一个元素(这里的第一个不一定是指储存顺序(物理)上的第一个，一般是指逻辑上的第一个，在红黑树中是指树中的最左节点)。那么对于首个迭代器进行自减会怎样？

(1)首迭代器指向(即最左节点)不是根节点

最左节点不是根节点，就是根节点有左子树。那么第一个迭代器，指向一定是左子树的最左节点。--begin() ，会调用的decrement()函数，该函数如下：

 1   void decrement()
 2   {
 3     if (node->color == __rb_tree_red &&
 4         node->parent->parent == node)
 5       node = node->right;
 6     else if (node->left != 0) {
 7       base_ptr y = node->left;
 8       while (y->right != 0)
 9         y = y->right;
10       node = y;
11     }
12     else {
13       base_ptr y = node->parent;
14       while (node == y->left) {
15         node = y;
16         y = y->parent;
17       }
18       node = y;
19     }
20   }

　　因为第一个迭代器是执行最左节点，所以其没有左子树，node->parent->parent也不等于node，所以他会回溯，找到第一个node 不是其父节点的左节点，那么他的父节点就是其结果。由于最左节点上溯不可能会有节点不是其父节点的左节点，那么while的最后一个循环时，node指向根节点，y指向header节点，此时node != y->left,(y->left指向就是最左节点)，那么循环结束node = y，即指向了header节点，也是end().

(2)首迭代器指向(最左节点)是根节点

　　最左节点就是根节点，这就说明根节点没有左子树。此时--begin(),同样也是调用的decrement()函数，此时node->parent->parent != node,同时最左节点也没有左子树。那么函数会进入while循环，第一次y指向头结点（header指向的节点），node即是根节点，也是最左节点，循环条件满足，node == y->left(即最左节点)，进入循环，node = y，node现在是头结点了，y = y->parent，指向根节点了，(头结点的parent是根节点，这是实现的技巧)。此时y->left,即根节点的左子节点，根没有左子树，所以为0，此时循环条件不满足，跳出循环，再node = y。即node又变为根节点了。即对于根没有左子树的红黑树，对--begin()，其结果还是begin()。

1 iterator it = rb_tree.begin();
2  it == --it;

二、end()获取last迭代器的自减

　　last = end(); last指向的是头结点(也这是红黑树实现中的技巧，header和end()都指向头结点)。此时--last，会调用decrement函数，此时node即是头结点，node->color == __rb_tree_red &&node->parent->parent == node,为真。(头节点的颜色规定为红，而且头节点的parent是根节点，根节点的parent又是头结点，所以node->parent->parent==node)。这时候node = node->right。头结点的右节点，指向的红黑树的最右节点，最大的节点。此时--last，指向最大节点是正确的。

三、指向最右节点迭代器自增

　　无论什么样的情况，自增都是调用的increment()函数，那么就先上increment函数吧，如下：

 1 void increment()
 2   {
 3     if (node->right != 0) {
 4       node = node->right;
 5       while (node->left != 0)
 6         node = node->left;
 7     }
 8     else {
 9       base_ptr y = node->parent;
10       while (node == y->right) {
11         node = y;
12         y = y->parent;
13       }
14       if (node->right != y)
15         node = y;
16     }
17   }

(1)最右节点不是根节点

　　这种情况，就是根节点还有右子树。这种情况下，对指向最右节点的迭代器自增，会调用上面increment函数。应该是指向最右节点，所以node->right == 0,所以只能上溯，找到其现行的节点不是其父节点的右节点。最右节点上溯，不可能会有现行的节点不是其父节点的右节点，while的最后一次循环时，node指向根节点，y指向头结点(即end()指向的节点)，这时，node ！= y->right(存储的是最右节点)，跳出循环。在判断node->right != y，现在node是根节点，其有右节点不是头结点，所以判断结果为真，node=y，最后node为y，即头结点，也就是end()返回的迭代器指向的节点，亦是last节点，指向最右的节点的迭代器自增，得到last迭代器，这是正确的。

(2)最右节点是根节点

如下图

此时，指向最右的迭代器自增，调用increment函数，node->right == 0,进入while循环。y开始是node的parent，即头结点，node == y->right(最右节点，此情况下即根节点)，循环条件成立，进入循环。然后node = y，node变为头结点，y=y->parent(头结点的parent即根节点),y变为根节点。此时判断循环条件，y->right,即根节点的右子节点，这种情况下的根右子节点为空，node为头结点不为空，循环条件不成立，跳出循环。接下来是

1       if (node->right != y)
2         node = y;

此时node是头结点，其右节点就是树的最右节点，这种情况下就是根节点，y就是根节点，那么if判断条件不成立，返回的时候node就是头结点，即end()返回迭代器指向的节点。此时迭代器就是last迭代器。对指向最右节点的迭代器自增，得到last迭代器，亦end()返回的迭代器，这是正确的。

结语

本文中讨论了各种边界情况，其中发现在SGI STL的红黑树中的一个有趣情况，对于迭代器first = begin(),其指向的节点是根节点的时候，(最左节点是根节点)，对first自减得到的还是first。对于一些非边界的迭代器的自增和自减，不是这里讨论的范围。