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

Question

我是 C++ 的初学者，并且遇到了 2 个单独的错误。无法访问内存和堆栈溢出。

这是我使用指针对包含字符 az 的单词的 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();
};

标签： c++memory-leaksstack-overflow

Answer 1

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

This is because of this line:

delete this;

This is what a delete does

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

You can imagine why calling delete from within the destructor would be problematic. (Hint: Infinite recursion)

You don't want any delete this in your code.

Once you get rid of this, there are other issues.(Although you may live just by fixing this). For instance calling the destructor explicitly as you are doing in this line(and several other lines)

other.~Trie();

From 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!

Replace the explicit destructor calls with delete and let it call the destructor correctly.

I would recommend replace any raw pointers and new and delete with smart pointer. Start with shared_ptr to begin with. (raw_pointers are so 2010 ;))

Footnote: Get rid of these checks. They are non-idiomatic. It's ok and desirable for the caller to burn when calling a member function on a nullptr

if (this == nullptr)
    return false;