I've started to implement a dictionary using a trie. Basically, i have a root node which has a definition (pointer to T that represents de value associated to the key) and childs (pointer to array that contains pointers to 256 nodes, one for each letter). check the definitions out:
template<typename T>
class DiccString {
public:
DiccString() : root(NULL);
DiccString(const DiccString<T>&);
~DiccString() {delete root;}
void define(const string& key, const T& value);
bool isDefined(const string& key) const;
const T& getDefinition(const string& key) const;
T& getDefinition(const string& key);
void remove(const string& key);
const Set<string>& keys() const;
private:
struct Node{
Node** childs;
T* definition;
Node(){
std::cout << "Node has been created " << this << std::endl;
childs = new Node*[256];
definition = NULL;
}
~Node(){
std::cout << "Node has been deleted " << this << std::endl;
delete definition;
delete [] childs;
}
};
Node* root;
};
So if i want to store "John" with the value 14 (T would be int so), assuming there is no other key, then i would create a root, then at root->childs[(int)'j'] i would create another node "nodeJ", and then nodeJ->childs[(int)'o'], and so on until reaching the last node "nodeN", which will contain the value (nodeN->definition = 14).
The problem is when i do:
int main() {
DiccString<int> d;
d.define("john",20);
d.define("jane",25);
return 0;
}
Then i expect all nodes created to be destroyed but take a look at the output:
Node created 0x61fc20 // root
Node created 0x620860 // for letter 'j'
Node created 0x621090 // for letter 'o' (child of 'j' 0x620860)
Node created 0x6218c0 // for letter 'h' (child of 'o' 0x621090)
Node created 0x6220f0 // for letter 'n' (child of 'h' 0x6218c0), value: 20
Node created 0x622990 // for letter 'a' (child of 'j' 0x620860)
Node created 0x6231c0 // for letter 'n' (child of 'a' 0x622990)
Node created 0x6239f0 // for letter 'e' (child of 'n' 0x6231c0), value: 25
Node deleted 0x61fc20 // root
Just the root is being deleted. So apparently when it comes to execute delete [] childs in the destructor of Node, it's not deleting all the elements of the array, which i'm sure that exist: for instance, in the case of the call to the destructor of root (which is the only one actually being called), i evaluated childs[(int)'j'] and it's certainly 0x620860, so i know it should call the destructor of this element (at least) when it executes delete [] childs, right?
What i am doing wrong?
childs has type Node**, it is a pointer to a pointer. You allocate for it an array of Node* pointers.
delete[] childs deletes this allocation, i.e. only the memory for the pointers, not the objects the pointers point to.
We don't see the code where you actually allocate Nodes, but you must store somewhere somehow which of the 256 allocated Node* actually point to a valid Node object. Maybe you do it via marking the pointers with a NULL pointer? In that case you probably want to do something like:
for(int i=0; i<256; ++i) {
delete childs[i];
}
I should also note, that you should use a static array if the number of Node pointers is fixed and an std::vector otherwise.