AksLolCoding's blog

How Not to Code a Trie
By AksLolCoding, 83 minutes ago, In English

Below is a snippet from a trie implementation (the trie is stored in the 1-indexed vector t):

int get(int &u) {
    if (!u) {
        t.emplace_back();
        u = size(t)-1;
    }
    return u;
}
int insert(string s) {
    int u = 1;
    for (char c : s) {
        u = get(t[u].child[c-'a']);
    }
    return u;
}

This code is incorrect; can you figure out why?

Answer
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
65 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A simple fix is to avoid passing a reference into t across emplace_back(). For example, make get take the child index by value and return the new index:

int get(int u) {
    if (!u) {
        t.emplace_back();
        u = t.size() - 1;
    }
    return u;
}

Then the original u = get(t[u].child[c - 'a']); is safe.

→ Reply
  • »
    »
    57 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This is also wrong: it doesn't update t[u].child[c-'a'] when a node is created

    → Reply
    • »
      »
      »
      51 minute(s) ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      How about changing get to take the parent/index instead of the child reference

      int get(int u, int c) {
    if (!t[u].child[c]) {
        t.emplace_back();
        t[u].child[c] = t.size() - 1;
    }
    return t[u].child[c];
}

      Then:

      u = get(u, c - 'a');

      This keeps the write-back behavior, while no reference into t survives the emplace_back().

      → Reply