Could someone explain the behavior of this program to me?
Difference between en1 and en2, changed 82 character(s)
Hello, ↵

I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger
. I commented in the code above the part where the issue seems to be, 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?  

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)