Could someone explain the behavior of this program to me?

Revision en2, by Bekh, 2020-10-01 04:01:33

Hello,

I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger, the issue seems to be in the insert function. I explained the issue in code comments.

struct Trie{
    struct Node{
        int id, nxt[26];
        Node(int id) : id(id)
        {
            memset(nxt, -1, sizeof(nxt));
        }
    };
    vector<Node> v;
    vector<bool> leaf;
    void init()
    {
        v.clear();
        leaf.clear();
        addNode();
    }

    int addNode()
    {
        v.push_back(v.size());
        leaf.push_back(false);
        return (int)(v.size()) - 1;
    }

    int getSizeMinusOne()
    {
        return (int)(v.size()) - 1;
    }

    void insert(const string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            c -= 'a';
            if (v[cur].nxt[c] == -1)
            {
                // Note I only use one of the following NOT both at the same time
                
                // Approach (1)
                // v[cur].nxt[c] doesn't get updated. Stays -1 and RTEs later on due to out of boundary access
                v[cur].nxt[c] = addNode();

                // Approach (2)
                // works fine
                addNode();
                v[cur].nxt[c] = getSizeMinusOne();
            }
            cur = v[cur].nxt[c];
        }
        leaf[cur] = true;
    }
};

I also found out that both approaches seem to work find when changing the array nxt to a vector instead of an array. Could someone explain why this happens when nxt is an array? And why approach (2) works fine even if nxt is an array?

Tags undefined behavior, c++

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Bekh 2020-10-01 04:01:33 82
en1 English Bekh 2020-10-01 03:59:40 1752 Initial revision (published)