Runtime error when using struct as value in std::map?

Question

I am using a map with int value -> trie, trie is the struct. So why am I getting runtime error when I print all keys value in my map? But if I don't print anything then there is no error(the insert() part don't cause any error).

struct trie{
    node *root;
    trie(){
        root = new node();
    }
    void insert(int x){
        node *cur = root;
        for(int i = 31; i >= 0; i--){
            int b = (x >> i) & 1;
            if (cur->child[b] == NULL) cur->child[b] = new node();
            cur = cur->child[b];
        }
        cur->isleaf = true;
    }
    int maxxor(int x){
        node *cur = root;
        int res = 0;
        for(int i = 31; i >= 0; i--){
            int b = (x >> i) & 1;
            if (cur->child[b ^ 1] != NULL){
                res |= (1ll << i);
                cur = cur->child[b ^ 1];
            } 
            else cur = cur->child[b];
        }
        return res;
    }
    int minxor(int x){
        node *cur = root;
        int res = 0;
        for(int i = 31; i >= 0; i--){
            int b = (x >> i) & 1;
            if (cur->child[b] != NULL) cur = cur->child[b];
            else{
                res |= (1ll << i);
                cur = cur->child[b ^ 1];
            }
        }
        return res;
    }
    ~trie(){
        delete root;
    }
};
map<int, trie> tr;
int32_t main(){
    ios::sync_with_stdio(false);
    tr[3].insert(1);// no error
    for(auto x: tr) cout << x.first << ' '; //RUNTIME ERROR?
}

I have tried to debug and read various questions/answers but I still not be able to debug this code. Any help are appreciated.

Answer 1

You have implemented a "complex" tree if i may say, using linked list. And in order to avoid trouble, you need to make sure that your destructors do their work propoerly and are coherent i.e destroy all allocated memory and don't "try" to "destroy" unallocated space or already destroyed space.

That said, your trie destructor destroys root data member, which calls node destructor. And node destructor destroys both two child which were not necessarily allocated. This is the origin of your Segmentation Error.

To correct this you should only destroy allocated child. Here is a simplified version of your code

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
struct node{
    node* child[2];
    bool isleaf;

    node(){
        child[0] = child[1] = NULL;
        isleaf = false;
    }

    ~node(){            
    }
};
struct trie{
    node *root;
    trie(){
        cout << " in trie ctor" << endl;
        root = new node();
    }

    void insert(int x){
        cout << "in insert trie methode " << endl;

        node *cur = root;

        cur->child[0] = new node();
        cur->child[1] = new node();

    }

    ~trie(){
        delete root->child[0]; // i'm sure it has been allocated
        delete root->child[1]; // i'm sure it has been allocated
        // delete root, would be like doing int *p; delete p;
    }
};

map<int, trie> tr;
int32_t main(){

    ios::sync_with_stdio(false);
    tr[3].insert(1);
    for(auto x: tr) 
        cout << x.first << endl << endl;    
}