在for循环中重新排序测试条件:编译器错误？

Question

我有一个存储在数组中的树,我正在尝试找到一个特定的节点:

std::vector<Node> nodes = ...
const unsigned short sentinel = -1;
unsigned short index = 0;
for (Node* node = &nodes[index]; // root node
     index != sentinel;
     node = &nodes[index])
{
    if (foo(*node)) {
       index = node->left;
    } else {
       index = node->right;
    }
}

换句话说,没什么特别的.但是,MSVC 2012失败,尝试访问nodes[sentinel]超出范围.事实证明它首先计算&nodes[index],然后测试index.(调试模式,无优化).

对我来说,这看起来像代码生成错误,但我至少在十年内没有看到过这样的错误.这是简单的未经优化的代码.当然,即使重新排列,node在index测试之前实际上并没有被使用,并且在x86上拥有这样的越界指针并不是非常不安全,但是MSVC vector<>在该非法索引上是合理的断言.

干净的构造并再次检查组件; 它是可重复的.树也不是空的,总是有一个根节点.

我忽略了什么,或者这真的是一个严重的编译器错误？

Answer 1

如果你有这样的for循环:

for (init; cond; step) { body; }

然后这是表达式/语句的执行顺序:

1. 在里面
2. 条件; 否则就是假的
3. 身体
4. 步
5. 条件; 否则就是假的
6. 身体
7. 步
8. ...

换句话说,它是这个的同义词:

{
  init;
  while (cond) {
    body;
    step;
  }
}

在你的情况下,可能发生的身体套index到sentinel.然后你期望cond执行并打破循环,但请注意,在每次执行主体之后,step会在cond之前执行.这意味着node = &nodes[index]确实会执行新值index,即sentinel.所以VS正在产生应有的东西.

你的循环似乎与传统for循环完全不同; 我认为将它变成一个显式while循环会更有意义.如果我正在对您的代码进行代码审查,我肯定会要求.

Answer 2

您的代码重写为 while 循环就像

Node* node = &nodes[index]; // root node
while(index != sentinel)
{
    {
        if (foo(*node)) {
           index = node->left;
        } else {
           index = node->right;
        }
    }

    node = &nodes[index];
}

最后一行可能是对节点[-1]的访问。

我会将你的循环重写为

unsigned short index = 0;
do
{
    Node* node = &nodes[index];
    if (foo(*node)) {
       index = node->left;
    } else {
       index = node->right;
    }
} while(index != sentinel);