c++ - 在 C++ 中实现一个 trie

Question

我想在 cpp 中实现一个 trie。当我尝试打印出 trie 中的所有字符串时，没有打印任何内容。但是代码编译成功。我认为我的插入有问题。我的猜测是我应该在某处通过引用传递，以便实际修改特里树，但我不确定问题出在哪里或出在哪里。

我的结构:

struct Node {
    unordered_map<char, Node*> children;
    bool completeWord;
};

class Trie {
private:
    Node* root;
    void printAll(Node* tmp);
public:
    Trie();
    void insert(string s);
    void printAll();
};

Trie::Trie() {
    root = new Node();
    root->completeWord = false;
}

方法:

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto m = p->children;
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        else
            p = m[c];
    }
    p->completeWord = true;
}

printAll 用于调试:

void Trie::printAll() {
    printAll(root);
}

void Trie::printAll(Node* tmp) {
    Node* t = tmp;
    auto m = t->children;
    if(!m.empty()){
        for(auto p : m) {
            cout << p.first << " ";
            printAll(p.second); 
        }
    }
}

测试用例:

int main() {
    Trie* t = new Trie();
    string arr[] = {"abc", "abcd", "lmn", "edf"};
    for(string s : arr) 
        t->insert(s);
    t->printAll();
    return 0;
}

Answer 1

感谢@Hitobat 和@Code-Apprentice，我知道我做错了什么。在我的 insert它应该是:

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto &m = p->children; //m -> &m
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        p = m[c]; //remove else
    }
    p->completeWord = true;
}

m之前只是指向映射对的指针，没有 &它只会更改这些对的拷贝，而不是这些对本身。所以我需要通过引用传递它们。
和p插入新节点时未更新。