这两份代码有什么区别?
查看原帖
这两份代码有什么区别?
470769
DengStar楼主2024/11/20 14:22

代码 1:t[u][c] = newNode();,测样例时,在 Windows 中输出错误答案,在 Linux 中开启 Address Sanitizer 后测试出现 heap-use-after-free 错误。
代码 2:int s = nowNode(); t[u][c] = s; 正确。
这两份代码究竟有什么区别??
我的代码用了 vector,没有在一开始就给所有节点分配内存池,而是在需要新建节点时,才在 newNode() 中扩容:

struct Trie
{
    vector<array<int, Sig>> t;
    vector<int> vis;
    int tot;
    int newNode()
    {
        array<int, Sig> tmp;
        tmp.fill(0);
        t.push_back(tmp), vis.push_back(0); // 动态扩容
        return tot++;
    }
    Trie() { tot = 0, newNode(); }

    void insert(string &str)
    {
        int u = 0;
        for(char ch: str)
        {
            int c = ch - 'a';
            if(!t[u][c])
            {
                // int s = newNode();
                t[u][c] = newNode();
            }
            u = t[u][c];
        }
        vis[u] = 1;
    }
};

错误会不会和这有关?因为我发现,如果把 vector 改成 array,在一开始分配好内存池而不是在 newNode() 中扩容,代码 1 就对了。但我不知道原因是什么。
完整错误代码

2024/11/20 14:22
加载中...