尝试将单词插入 trie 时出现分段错误

Question

您好 :) 谁能告诉我为什么以下代码不起作用？程序在 'B' 对应节点的 if(children[word[letter_no] - 'A'] == nullptr) 行崩溃。但是节点是创建的，当我尝试在构造函数中调用 children[1] 时，它起作用了。但是当它在 insert() 函数中调用时，它不会...

包括

#include <memory> //shared_ptr
#include <string>    
using namespace std;    
const int ALPHABET = 26;

class Node {
public:
    shared_ptr<Node> children[ALPHABET];
    
    Node() { for (int i = 0; i < ALPHABET; ++i) children[i] = nullptr;}
    void insert(const string &word, unsigned letter_no) {
        if (letter_no < word.length()) {
            if (children[word[letter_no] - 'A'] == nullptr) 
                children[word[letter_no] - 'A'] = make_shared<Node>();
            children[word[letter_no] - 'A']->insert(word, letter_no+1);
        }
    }
};

int main() {
    Node trie{};
    trie.insert("ABC", 0);
    return 0;
}

Answer 1

启用编译器警告！

由于未指定的评估顺序，您得到了未定义的行为：
```
children[word[letter_no] - 'A']->insert(word, ++letter_no);
```
warning: unsequenced modification and access to letter_no [-Wunsequenced]
你这里也有潜在危险的比较：
```
letter_no < word.length
```
warning: comparison between signed and unsigned integer expressions

on wandbox

此外，您不应在现代 C++ 代码中使用 new 和 delete。根据您需要的所有权语义使用 std::unique_ptr 或 std::shared_ptr。

来自评论：

Jecke: That's all true, but none of it is what's causing the problem. I simplified my code so it would be more readable in a question. In my original code, I'm trying to use shared_ptr, but the result is the same. Look, pastebin.com/MFZdrp22 doesn't work any better (still segmentation fault)

仔细查看这些行：

if (letter_no < word.length()) 
{
    if (children[word[letter_no] - 'A'] == nullptr)
    {
        children[word[letter_no] - 'A'] = make_shared<Node>();
    }

    ++letter_no;                                              // (0)
    children[word[letter_no] - 'A']->insert(word, letter_no); // (1)
}

word 是 "ABC".
word[letter_no] - 'A' 是 0.
在 (0)，你递增 letter_no。
在(1)，word[letter_no] - 'A'是1。
children[1] 是 nullptr。轰！

同样，编译器是您的朋友。使用 -fsanitize=undefined 编译，您将收到以下错误消息：

runtime error: member call on null pointer of type 'Node'
runtime error: member access within null pointer of type 'Node'

on wandbox

Answer 2

Vittorio 已经回答了关于样式的几句话的原因：

你只能有一种方法：

void insert(const string &word, size_t letter_no = 0);

那么你不需要覆盖，你可以使用std::unique_ptr并且你不需要在你的ctor中循环，如果你消除代码重复：

    if (letter_no < word.length()) {
        auto &child = children[word[letter_no] - 'A'];
        if ( !child ) 
            child = std::make_unique<Node>();
        child->insert(word, ++letter_no);
    }

这不仅会使您的代码更具可读性，而且会使您的问题消失

Answer 3

是正确的。您应该始终清理警告。

但为了给你一个完整的解释：

考虑当你的第 1^st 递归时，letter_no 是 0。 word 包含 'A'、'B'、'C' 和 '[=16=]'。所以 letter_no 索引 'A'.

验证 letter_no 是 word 的有效索引后：letter_no < word.length() 你 increment letter_no: children[word[letter_no] - 'A']->insert(word, ++letter_no);

letter_no 作为第 1^st 操作递增，因此它实际上具有值 1，索引 'B'。然后你减去 'A' 得到 1 的索引，这是一个未分配的元素。

就解决方案而言，您不关心维护 letter_no 的值，所以只需这样做：children[word[letter_no] - 'A']->insert(word, letter_no + 1);

尝试将单词插入 trie 时出现分段错误

Segmentation fault while trying to insert a word into trie

c++

pointers

trie

包括