Floating point exception in C++ Trie

Question

The following code for Trie implementation is throwing Floating point exception upon call to function insert. The line inside for loop to check for existing node is where the problem is.

struct Node {
    char c;
    bool isend;
    unordered_map<int, struct Node*> map;
};

void insert(struct Node* root, string contact) {
    int size = contact.size();
    char ch;

    for (int i = 0; i < size; i++) {
        ch = contact[i];
        // this check is creating problem
        if (root->map.find(ch) == root->map.end()) {
            struct Node* tmp = (struct Node*) malloc(sizeof(struct Node));
            tmp->c = ch;

            if (i == (size - 1)) {
                tmp->isend = true;
            } else {
                tmp->isend = false;
            }

            root->map.insert(make_pair(ch, tmp));
            root = tmp;            
       } else {
          root = root->map[ch];   
        }         

    }
}

int main()
{
    struct Node* root = NULL;

    root = (struct Node*) malloc(sizeof(struct Node));

    insert(root, "text");
}

Any help?

Have you tried to use a debugger to catch the crash as it happens, and then locate the exact line in your code? Please do that first. — Some programmer dude, Jul 13 '18 at 11:18
Are you sure you got a floating point exception with this code ? There are no floating points used anywhere in it. — Sander De Dycker, Jul 13 '18 at 11:19
Oh and stop using old C code with C++ (like `malloc`). C++ is *not* "C with classes". Please [get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and learn C++ properly. — Some programmer dude, Jul 13 '18 at 11:19
Use of `malloc` in standard C++ is unusual. Unless you are a library implementer. — Ron, Jul 13 '18 at 11:20
Despite what the error popup said, this code is not throwing a floating-point exception. Something went wrong, and the OS is guessing at the problem. Memory corruption often ends up being reported as a "floating-point exception", even though it has nothing to do with floating-point and nothing was thrown. So treat that error message as "something is broken"; nothing more. — Pete Becker, Jul 13 '18 at 11:27
Just a guess, but maybe when the `unordered_map` needs to do a hash, some modulus operation gets all fouled up due to the map being bogus. — PaulMcKenzie, Jul 13 '18 at 11:31
I forgot that [SIGFPE actually covers all arithmetic errors](https://en.wikipedia.org/wiki/Signal_(IPC)#SIGFPE), so this could have been a simple division by 0 eg. — Sander De Dycker, Jul 13 '18 at 11:34

john · Answer 1 · 2018-07-13T11:21:59.473

6

Do not use malloc in C++ code (unless you really know what you are doing)

root = new Node;

and

tmp = new Node;

The problem is that because you use malloc the constructor for Node::map is not getting called. Using new will make sure that all necessary constructors are called.

edited Jul 13 '18 at 11:21

answered Jul 13 '18 at 11:20

john

85,011
4
57
81

1

The (implicit) constructor for Node calls the Node::map constructor. – john Jul 13 '18 at 11:32
Thanks John I appreciate your help. It solved the issue. – Sonu Patidar Jul 13 '18 at 13:23

Ron · Accepted Answer · 2018-07-13T11:34:47.460

When you use malloc you are not invoking your Node class constructor, you are just allocating memory.

Use new instead which will both allocate the memory and call a constructor. So:

struct Node* tmp = (struct Node*) malloc(sizeof(struct Node));

should be:

Node* tmp = new Node();

and:

struct Node* root = NULL;
root = (struct Node*) malloc(sizeof(struct Node));

should be:

Node* root = new Node();

Remember to delete where appropriate. Or even better, use smart pointers. And above all avoid using C with classes. Use proper standard C++.

Floating point exception in C++ Trie

2 Answers2