GCC13.2下C++23中数组向量移动时的异常问题排查

问题描述 #

我在实现Trie树时遇到了以下问题：使用std::array<int,26>存储子节点索引，节点对象保存在std::vector<Node>中。新增节点时vector会触发动态扩容，若不在Trie构造函数中为vector预留内存，扩容后std::array的内容会出现错乱。不确定这是代码实现错误，还是忽略了容器的特性。已知std::array的移动构造行为和其他容器不同，但不清楚这是否是问题根源。

原代码 #

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <string>
#include <iomanip>

using namespace std;

class Trie {
    struct Node {
        Node() : child{}, words{0} {
            fill_n(child.begin(), 26, -1);
        }
        void print(ostream& oss) {
            for(auto&& x : child) oss << setw(2) << x << ' ';
            oss << words << endl;
        }
        array<int,26> child{};
        int words{0};
    };
    vector<Node> data{};
    Node root{};

public:
    Trie() : data{}, root{}{
        //data.reserve(32);
    }

    void print(ostream& oss = cerr) {
        root.print(oss);
        for(auto&& nd : data) nd.print(oss);
    }

    void insert(string word) {
        Node* node = &root;
        for (auto&& w : word) {
            int& i = node->child[w-'a'];
            if (i == -1) {
                cerr << "cap: (" << data.capacity();
                data.emplace_back(Node{});
                cerr << '/' << data.capacity() << ")\n";
                i = data.size() - 1;
            }
            node = &data[i];
        }
        ++node->words;
    }

    bool search(string word) {
        Node* node = &root;
        for (auto&& w : word) {
            int& i = node->child[w - 'a'];
            if (i == -1)
                return false;
            else {
                node = &data[i];
            }
        }
        return node->words > 0;
    }

    bool startsWith(string prefix) {
        Node* node = &root;
        for (auto&& w : prefix) {
            int& i = node->child[w - 'a'];
            if (i == -1)
                return false;
            else {
                node = &data[i];
            }
        }
        return true;
    }
};


int main() {
    Trie obj;
    obj.insert("abcdefghijklmnopqrstuvwxyz");

    cerr << obj.search("abcd") << ", " << obj.startsWith("abcd") << endl;
    obj.print();

    return 0;
}

问题根源 #

问题的核心不是std::array的移动构造，而是vector扩容导致的指针失效：

• std::vector扩容时，会重新分配更大的内存空间，将原有元素移动/拷贝到新内存后释放旧内存。此时，之前通过&data[i]获取的Node*指针会指向已被释放的旧内存，后续访问这些野指针会触发未定义行为，表现为std::array内容错乱。
• 你在insert循环中，每次创建新节点后都会保存&data[i]作为下一个节点的指针。当vector后续扩容时，这些指针全部失效，后续访问指针指向的child数组自然会出现异常。

解决方法 #

方法一：提前预留内存 #

在Trie构造函数中调用data.reserve(N)（N为预估的节点数量），避免vector触发扩容。这样所有节点的内存地址不会改变，指针始终有效：

Trie() : data{}, root{} {
    data.reserve(32); // 预留足够内存，根据实际场景调整大小
}

方法二：使用索引而非指针访问节点 #

放弃保存Node*指针，改用节点在vector中的索引访问。可以将root也纳入vector管理，彻底避免指针失效问题。示例调整如下：

class Trie {
    struct Node {
        Node() : child{}, words{0} {
            fill_n(child.begin(), 26, -1);
        }
        void print(ostream& oss) {
            for(auto&& x : child) oss << setw(2) << x << ' ';
            oss << words << endl;
        }
        array<int,26> child{};
        int words{0};
    };
    vector<Node> data{};
    // 用0作为root的索引，初始化时先把root放入vector
public:
    Trie() {
        data.emplace_back(Node{});
    }

    void print(ostream& oss = cerr) {
        for(auto&& nd : data) nd.print(oss);
    }

    void insert(string word) {
        int node_idx = 0; // root的索引
        for (auto&& w : word) {
            int& child_idx = data[node_idx].child[w-'a'];
            if (child_idx == -1) {
                data.emplace_back(Node{});
                child_idx = data.size() - 1;
            }
            node_idx = child_idx;
        }
        ++data[node_idx].words;
    }

    bool search(string word) {
        int node_idx = 0;
        for (auto&& w : word) {
            int child_idx = data[node_idx].child[w - 'a'];
            if (child_idx == -1)
                return false;
            node_idx = child_idx;
        }
        return data[node_idx].words > 0;
    }

    bool startsWith(string prefix) {
        int node_idx = 0;
        for (auto&& w : prefix) {
            int child_idx = data[node_idx].child[w - 'a'];
            if (child_idx == -1)
                return false;
            node_idx = child_idx;
        }
        return true;
    }
};

这种方式完全依赖索引访问，不受vector扩容影响，是更健壮的实现方式。

内容的提问来源于stack exchange，提问作者DeltaVega