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.

Your code is not complete (eg. Struct node is not here), and we don't have the error message... — hivert
– hivert, Commented May 14, 2017 at 9:41
what is node? My guess would be that copying the map elements causes the problem (in for (auto x:tr)) — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented May 14, 2017 at 9:41

Daouda · Accepted Answer · 2017-05-14 15:38:07Z

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;    
}

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related