Implementation of trie with map without creating new nodes

Question

I was trying to implement the trie data structure & wrote the foll code

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

struct trie_node{
  map<char, trie_node> child;
  int pos=-1;
};

map<char, trie_node> baap;

void lex_insert(string s, int pos){ // lexiographically insert into map
  trie_node t = baap[s[0]];
  for(int i=1; i<s.size(); i++){
    t = t.child[s[i]];
  }
  t.pos = pos;
}

int find(string s, int r){  // find in trie structure
  trie_node t = baap[s[0]];
  int pos = t.pos;
  for(int i=1; i<s.size(); i++){
    if(t.child.find(s[i])!=t.child.end()){
      t = t.child[s[i]];
      if(t.pos<=r)
        pos = t.pos;
    }
    else
      return pos;
  }
  return pos;
}

void ans(int &found, string s){ // find lexiographically matching prefix
  trie_node t = baap[s[0]];
  if(found<0){
    while(t.pos<0){
      auto x = t.child.begin();
      t = x->second;
    }
    found = t.pos;
  }
}

int main(){
  int n;  cin>>n;
  vector<string> vs(n);
  for(int i=0; i<n; i++){
    cin>>vs[i];
    lex_insert(vs[i],i);
  }
  int found = 0;
  int q;  cin>>q;
  for(int i=0; i<q; i++){
    int r; string p;
    cin>>r>>p;
    found = find(p,r);
    ans(found, p);
    cout<<vs[found]<<'\n';
  }
}

Please focus on lex_insert() The code executes without errors, though when I try to dereference the map - baap, there are segmentation fault showing up. I guess this is because I didnt construct new nodes at each level in lex_insert as I have seen in some codes. But then, map is supposed to do dynamic allocation. Can someone please explain, why I am not able to access the elements of map - baap ?

Note - Its not an exact trie implementation but derives from it

Answer 1

One possible cause of your problem:

trie_node t = baap[s[0]];

Here t will be a copy of baap[s[0]]. Whatever changes you make to t will not be reflected in the original.

Since you later in a loop reassign to t (again making copies) you can't use references (a reference can not be rebound). Instead you have to use pointers. Either store pointers in the maps, or use the address-of operator to get a pointer:

trie_node* t = &baap[s[0]];  // Get a pointer to the node

---

As for the crash, if the above doesn't solve it, then you should learn how to debug your programs. Especially with crashes you should learn how to use a debugger to catch the crash in action and how to locate where in your code it happens.