今天做 POJ 1204 的时候，我写了一个树结构，每个节点里有一个边数组，因为一个节点最多 26 条边，所以直接开了一个 26 的数组。相当于是邻接表写的吧。然后因为节点是用 vector 存储的，当时也考虑到 vector 在重分配 (reallocation) 的时候会让该容器之前的迭代器、指针和引用失效 (A reallocation invalidates all previously obtained iterators, references and pointers to elements of the vector), 所以才选用了数组下标替代指针的方法。因为通过下标访问元素是 vector 已经封装好了的函数，无论内存如何重分配，也不会改变任何元素的下标。

但是即使是这样，程序还是在内存重新分配的时候出了问题。这个问题非常诡异，所以写一篇文章备忘一下，也请各位看官注意。

后来就让这个 Bug 给我整了两个 Time Limit Exceeded. 在 Visual Studio .NET 里调试那是一点问题也没有，而用 G++ 4.3.4 编译的时候就出问题了。

这个是我之前写的程序的部分代码，仅保留与文章要讨论的问题相关的部分，并且有一些修改，可能看起来不是很有意义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdlib>
#include <vector>

using namespace std;

struct node {
    size_t edge[26];
    size_t &operator[](size_t i) {
        return edge[i - 'A'];
    }
};

vector<node> tree(1);

size_t create() {
    size_t i = tree.size();
    tree.push_back(node());
    return i;
}

int main(int argc, char *argv[]) {
    size_t n = tree.capacity() + 1;
    for (size_t i = 0; i < n; ++i)
        tree[i]['A'] = create(); // 这里可能出错。
    return EXIT_SUCCESS;
}

以上代码中，create() 函数能够让 tree 再增加一个元素，并且返回最后一个元素的下标。然后 tree.capacity() 表示容器为 tree 预留了多少个元素的位置，这里令 n = tree.capacity() + 1 就是想让 n 刚好超过 tree 的容量，然后让 tree “不得已”只能进行 reallocation.

让我们用 Visual Studio .NET 编译看看。一步一步跟踪发现 n 是 2, 然后 create() 调用了两次，返回的结果分别是 1 和 2（请注意在定义 tree 的时候我们给它初始化了一个元素，也就是说 tree 开始的时候 tree.size() == 1）。最后的结果是，tree 有三个元素，并且 tree[0].edge[0] == 1 && tree[1].edge[0] == 2, 没有任何问题，一切和我们预想的一样。

再用 G++ 编译看看。运行后，果然出错了。一步一步调试，n == 2 没问题，但是循环执行到 i == n – 1 的时候，将 create() 的返回值赋给 tree[i]['A'] 时，出错了。这个时候恰好是 reallocation 进行的时候。

细想可以发现，tree[i]['A'] 这个表达式是一个 char & , 再分解看 tree[i] 是一个 node, 这个 node 是 tree 中的元素，然后 tree[i]['A'] 便调用了 char &node::operator[](size_t i) 这个运算符的重载函数，返回的是 tree[i].edge[0] 的引用。这个时候，如果对 tree 进行 reallocate, 所有 tree 中的元素的地址都会改变，而如果取得引用是在 reallocate 之前，那么这个引用便失效了。

经过上面的分析，我们可以猜，对于 tree[i]['A'] = create() 这个表达式，Visual Studio .NET 先计算了等号的后半部分，再计算等号的前半部分，再对等号的前半部分赋值。而 G++ 先计算的是等号的前半部分，再计算后半部分，再对已经计算出的前半部分赋值。

现在为了证明刚才的猜想，把代码改成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

struct node {
    size_t edge[26];
    size_t &operator[](size_t i) {
        clog << "OPERATOR" << endl;
        return edge[i - 'A'];
    }
};

vector<node> tree(1);

size_t create() {
    clog << "CREATE" << endl;
    size_t i = tree.size();
    tree.push_back(node());
    return i;
}

int main(int argc, char *argv[]) {
    size_t n = tree.capacity() + 1;
    for (size_t i = 0; i < n; ++i)
        tree[i]['A'] = create(); // 这里可能出错。
    return EXIT_SUCCESS;
}

分别在 Visual Studio .NET 和 G++ 下编译。Visual Studio .NET 的输出结果是：

CREATE
OPERATOR
CREATE
OPERATOR

然后在 G++ 中编译，在出错之前，输出的结果是：

OPERATOR
CREATE
OPERATOR
CREATE

果然如此。

这次内存重分配带来的 Bug 又揭示了一个 Visual Studio .NET 和 G++ 的区别。我感觉在这件事上 Visual Studio .NET 做得比较好一点，因为等号运算应该是从右边计算到左边才好的。而且在这个等号的左边的类型是 size_t & , 右边的类型是 size_t , 本质上都是 unsigned long , 都不是我们自定义的数据类型，这就更不能先算左边了。（因为如果是自定义的数据类型，等号往往是重载，此时的等号已经变成了函数，所以从左到右还无可厚非。）

所以最后我只能用一个临时变量 size_t t = create() 再 tree[i]['A'] = t 才解决了问题，果断 AC.

原创文章，转载请注明来源：http://euyuil.com/2528/notice-re-allocation-when-using-stl-of-cplusplus/