Using pointers in trie implementation

help
1

Please keep in mind that this is the first time I’m using a pointer in my 6 months of CP, and I don’t know the names of most of what I’m using.

I want this code 1 to do what code 2 does.

Code 1 
const int AL = 26 + 1;
const int MAXN = 100'000;
struct trienode{
    vector<trienode*> nodes;
    int count = 0;
    trienode(){
        nodes.resize(AL, NULL);
    }
    trienode*& operator[](int ch){
        return nodes[ch];
    }
};
int dp[MAXN][AL][AL];
struct trie{
    trienode begin;
    void get(const string &s, int idx){
        trienode &currnode = begin;
        for(int i=0;i<s.size();i++){
            int ch = s[i] - 'a' + 1;
            if(currnode[ch] == NULL){
                currnode[ch] = new trienode();
            }
            for(int i=0;i<AL;i++){
                if(currnode[i] == NULL) continue;
                dp[idx][ch][i]+=currnode[i]->count;
            }
            currnode = currnode[ch];
        }
    }
    void add(const string &s){
        trienode &currnode = begin;
        ++currnode.count;
        for(int i=0;i<s.size();i++){
            int ch = s[i] - 'a' + 1;
            if(currnode[ch] == NULL){
                currnode[ch] = new trienode();
            }
            currnode = currnode[ch]; //Problematic line, I don't know how to fix
            ++currnode.count;
        }
    }
};
Code 2 
const int AL = 26 + 1;
const int MAXN = 100'000;
struct trienode{
    vector<trienode*> nodes;
    int count = 0;
    trienode(){
        nodes.resize(AL, NULL);
    }
    trienode*& operator[](int ch){
        return nodes[ch];
    }
};
int dp[MAXN][AL][AL];
struct trie{
    trienode begin;
    void get(const string &s, int idx){
        trienode* currnode = &begin;
        for(int i=0;i<s.size();i++){
            int ch = s[i] - 'a' + 1;
            if((*currnode)[ch] == NULL){
                (*currnode)[ch] = new trienode();
            }
            for(int i=0;i<AL;i++){
                if((*currnode)[i] == NULL) continue;
                dp[idx][ch][i]+=(*currnode)[i]->count;
            }
            currnode = (*currnode)[ch];
        }
    }
    void add(const string &s){
        trienode* currnode = &begin;
        ++currnode->count;
        for(int i=0;i<s.size();i++){
            int ch = s[i] - 'a' + 1;
            if((*currnode)[ch] == NULL){
                (*currnode)[ch] = new trienode();
            }
            currnode = (*currnode)[ch];
            ++currnode->count;
        }
    }
};

Honestly, I’m not completely sure how this works, but I’ve marked the line that is causing problems.

2

You can’t make a reference refer to a different object than the one it was initialised with, so I’d probably stick with pointers.

2 Likes