c++ - 特里树。无法访问内存

Question

我是 C++ 的初学者，我有一些问题，有 2 个独立的错误。无法访问内存和堆栈溢出。

这是我对包含字符 a-z 的单词使用指针的 Trie 树的实现。运行测试时，我可以毫无问题地成功添加数百甚至数千个节点，直到它最终崩溃。错误:无法访问内存。当我尝试运行查询并使用“isAWord”函数时，我经常会遇到此错误。当我尝试运行解构函数时，我也会遇到堆栈溢出。感谢任何帮助，因为我花了 2 天时间尝试调试但收效甚微。

#include "Trie.h"
#include <iostream>
#include <iterator>
#include <sstream>

using namespace std;    

//sets up tree
Trie::Trie()
{
    for (int i = 0; i < ALPH; i++)
        this->childs[i] = nullptr;

    endNode = false;
}

//add 'userInput' string to trie

void Trie::addAWord(std::string userInput)
{
    Trie* start = this;

    for (int i = 0; i < userInput.length(); i++)
    {
        int index = userInput[i] - 'a';

        if (start->childs[index] == nullptr)
            start->childs[index] = new Trie();

        start = start->childs[index];
    }

    start->endNode = true;
}

//returns true if 'wordFind' is in tree

bool Trie::isAWord(std::string wordFind)
{
    if (this == nullptr)
        return false;

    Trie* start = this;

    for (int i = 0; i < wordFind.length(); i++)
    {
        int index = wordFind[i] - 'a';
        start = start->childs[index];

        if (start == nullptr)
            return false;
    }

    return start->endNode;
}

//returns a vector containing the words in tree with prefix 'prefFind'

vector<std::string> Trie::allWordsStartingWithPrefix(std::string prefFind)
{
    string pres = PrefixRec(prefFind,*this);
    stringstream preStream(pres);
    istream_iterator<std::string> begin(preStream), end;
    vector<std::string> stringSet(begin, end);
    copy(stringSet.begin(), stringSet.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    return stringSet;
}

//helper method for AllWordsStartingWithPrefix

std::string Trie::PrefixRec(std::string& key, Trie const temp)
{
    if (temp.endNode)
        return(key + " ");

    for (char index = 0; index < ALPH; ++index)
    {
        index = key[index] - 'a';

        Trie const* curChild = temp.childs[index];
        if (curChild)
        {
            key.push_back(index);
            PrefixRec(key, *curChild);
            key.pop_back();
        }
    }
}

//copy cons and assignment op

Trie& Trie::operator=(const Trie& other)
{
    Trie* newPtr = new Trie(other);
    other.~Trie();
    return *newPtr;
}

//deconstructor

Trie::~Trie()
{
    if (this == nullptr)
        return;

        for (int i = 0; i < ALPH; i++)
        {
            if (childs[i] != nullptr)
                childs[i]->~Trie();
        }
        delete this;
        return;
}


#include <iostream>
#include <vector>
#include <string>

#define ALPH 26

class Trie
{
public:
    bool endNode;
    Trie* childs[ALPH];

    Trie();
    void addAWord(std::string key);
    bool isAWord(std::string key);
    std::vector<std::string> allWordsStartingWithPrefix(std::string key);
    Trie& operator=(const Trie& other);
    std::vector<std::string> wordsWithWildcardPrefix(std::string);
    std::string PrefixRec(std::string& key, Trie const temp);
    ~Trie();
};

Answer 1

I also get a stack overflow when I try to run the deconstructor.

这是因为这一行:

delete this;

这是一个delete做

The delete expression invokes the destructor (if any) for the object that's being destroyed,

您可以想象为什么从析构函数中调用 delete 会出现问题。 (提示:Infinite recursion)

您不希望在您的代码中有任何delete this。

一旦你摆脱了这个，就会有其他问题。(尽管你可能仅仅通过解决这个问题就可以生存)。例如，在这一行(以及其他几行)中显式调用析构函数

other.~Trie();

来自 iso cpp :

Should I explicitly call a destructor on a local variable?

No!

The destructor will get called again at the close } of the block in which the local was created. This is a guarantee of the language; it happens automagically; there’s no way to stop it from happening. But you can get really bad results from calling a destructor on the same object a second time! Bang! You’re dead!

将显式析构函数调用替换为delete，让它正确调用析构函数。

我建议用 smart pointer 替换所有原始指针和 new 和 delete .从 shared_ptr 开始首先。 (raw_pointers 是 2010 年的样子 ;))

脚注:去掉这些检查。它们是非惯用语。在 nullptr

上调用成员函数时，调用者可以燃烧

if (this == nullptr)
    return false;