Could someone explain the behavior of this program to me?

Правка en2, от 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?

Теги undefined behavior, c++

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Bekh 2020-10-01 04:01:33 82
en1 Английский Bekh 2020-10-01 03:59:40 1752 Initial revision (published)