I have a class that has this kind of structure:

class myClass(){
  public:
    myClass(){//empty constructor}
    
    void insertRecursively(string word) {
        myClass* node = this;
        for (int i = 0; i < word.length(); i  ) {
            if (node->map.find(word.at(i)) == node->map.end()) {
                node->map[word.at(i)] = new myClass();
            }
            node = node->map[word.at(i)];
        }
        node->isEnd = true;
    }

  
  private:
    unordered_map<char, myClass*> map = {};
    bool isEnd = false;
}

I tried write destructor in this way but it gives me error 'std::bad_alloc':

~myClass() {
    clear(map);
}

void clear(unordered_map<char, myClass*> map) {
    for (auto& pair : map) {
        if (pair.second != nullptr) {
            clear(pair.second->map);
        }
        delete pair.second;
    }
}

From what I known so far, I allocated memory on heap by using new keyword, so I should create destructor for myClass. I need to do this recursively because map contains pointers to other myClass pointers.

I've researched several hours and still cannot figure it out. Can anyone help me to spot the problem that will cause 'std::bad_alloc' ?

My entire code:

class Trie {
public:
    Trie() {
    }

    void insert(string word) {
        Trie* node = this;
        for (int i = 0; i < word.length(); i  ) {
            if (node->map.find(word.at(i)) == node->map.end()) {
                node->map[word.at(i)] = new Trie();
            }
            node = node->map[word.at(i)];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this;
        for (int i = 0; i < word.length(); i  ) {
            if (node->map.find(word.at(i)) == node->map.end()) {
                return false;
            } else {
                node = node->map[word.at(i)];
            }
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        Trie* node = this;
        for (int i = 0; i < prefix.length(); i  ) {
            if (node->map.find(prefix.at(i)) == node->map.end()) {
                return false;
            } else {
                node = node->map[prefix.at(i)];
            }
        }
        return true;
    }

    ~Trie() {
        clear(map);
    }

    void clear(unordered_map<char, Trie*> map) {
        for (auto& pair : map) {
            if (pair.second != nullptr) {
                clear(pair.second->map);
            }
            delete pair.second;
        }
    }

private:
    unordered_map<char, Trie*> map = {};
    bool isEnd = false;
};

CodePudding user response：

I draw your attention to the following lines of code.

unordered_map<char, myClass*> map = {};
void clear(unordered_map<char, myClass> map)

Trimming a few characters...

unordered_map<char, myClass*> map
void clear(unordered_map<char, myClass> map)

Observe that you declared the local item map over char and myClass*, but you declared clear() as operating on a map over char and myClass, as opposed to a map over char and myClass*.

The * makes a difference.

CodePudding user response：

Either you start to use smart pointers or you need to bring up a concept of ownership for your myClass instances created with new.

The latter could be:

• Instances aof myClass are owned by another instance of myClass (lets call it owner) where &a appears in owner.map (You are doing this already).
• Whenever an instance owner becomes destroyed, it has to free all instances it (directly) owns:

~myClass() {
  for(const auto& pair : map){
    delete pair.second;
  }
}

CodePudding user response：

Your Trie::clear() method deletes the same Trie twice.

~Trie() {
    clear(map);
}

void clear(unordered_map<char, Trie*> map) {
    for (auto& pair : map) {
        if (pair.second != nullptr) {
            clear(pair.second->map);
        }
        delete pair.second;
    }
}

The destructor ~Trie calls clear(pair.second->map) and then calls delete pair.second which is the same as clear(pair.second->map) again since delete calls the destructor of the pointed-at data. Calling clear() twice on the same map means that the second call is trying to delete already deleted data, which causes the crash. Calling delete on a pointer does not change the value of the pointer, which is why the nullptr check does nothing.

Since the destructor calls clear(), the clear() method does not need to explicitly call itself recursively. Just delete the map pointers.

~Trie() {
    clear(map);
}

void clear(unordered_map<char, Trie*> map) {
    for (auto& pair : map) {
        delete pair.second;
    }
}

By the way, calling delete nullptr is fine since it is required to do nothing.