0 
#include <vector>

struct Node;

std::vector<Node> heap;

struct Node {
    int x, c;

    explicit Node(int x): x(x), c(0) {}

    void update() {
        if(x > 0) {
            if(c == 0) {
                c = heap.size();
                heap.emplace_back(x / 2);
            }
            heap[c].update();
        }
    }
};

int main() {
    heap.emplace_back(100);
    heap.back().update();
}

考虑上面的代码。g++ -fsanitize=address当用( )编译gcc version 10.2.0 (Ubuntu 10.2.0-5ubuntu1~20.04)然后运行时，我得到AddressSanitizer: heap-use-after-free. 经过一番谷歌搜索后，当我尝试访问先前已释放的指针时，似乎会发生此错误。检查 ASan 的输出表明该对象已被 vector.emplace_back 释放。我相信这是矢量调整自身大小的结果，并得到了heap.reserve(1000)使代码运行良好的事实的支持。

然后我尝试用 push_back 替换 emplace_back，产生了类似的结果。但是，用循环替换递归可以正常工作。

int main() {
    heap.emplace_back(100);
    int prevc = 0;
    while(true) {
        int x = heap[prevc].x, c = 0;
        if(x > 0) {
            if(c == 0) {
                c = heap.size();
                heap.emplace_back(x / 2);
            }
            prevc = c;
        }else {
            break;
        }
    }
}

经过进一步检查，似乎在第一次调用update(). 此外，访问heap[0]andheap[1]很好，但访问heap[c]失败。

现在我很困惑。我找不到任何未定义的行为，也看不到向量内部调整大小导致我无法访问元素的任何原因。此外，我不确定为什么这仅会因递归而失败。我究竟做错了什么？

4

1 回答 1

2

正如 user4581301 在评论中指出的那样，问题实际上不是访问向量中的元素，而是访问c失败，因为this已通过heap调整大小删除。

在我的特殊情况下，我想写一个没有指针的二叉树，所以递归是必要的。具有讽刺意味的是，这背后的原因是为了避免指针陷阱，但这适得其反。为了将来参考，我找到了四种可能的解决方案：

  1. heap.reserve()到一个heap永远不会调整自身大小的足够大的值。
  2. 使用数组和指向最后一个元素的索引的指针模拟向量（基本上是选项 1，但可能更快）
  3. 添加类似的东西Node self = *this;并通过self. 注意：doingNode *self = this;不起作用，因为self将与this.
  4. 只需使用指针；它们的存在是有原因的。
于 2021-04-07T23:10:47.073 回答