在不创建新节点的情况下使用 map 实现 trie

Question

我正在尝试实现 trie 数据结构并编写了以下代码

#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';
  }
}

请关注lex_insert() 代码执行无误，但当我尝试取消引用地图时 - baap，出现分段错误。我想这是因为我没有像在某些代码中看到的那样在 lex_insert 中的每个级别构建新节点。但是， map 应该进行动态分配。有人可以解释一下，为什么我无法访问地图的元素 - baap ?

注意 - 它不是一个精确的 trie 实现，而是派生自它

Answer 1

您的问题的一个可能原因：

trie_node t = baap[s[0]];

此处 t 将是 baap[s[0]] 的副本。您对 t 所做的任何更改都不会反映在原始文件中。

由于您稍后在循环中重新分配给 t（再次制作副本），因此您不能使用引用（不能重新引用引用）。相反，您必须使用 pointers。要么在映射中存储指针，要么使用 address-of 运算符获取指针：

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

至于崩溃，如果上述方法不能解决问题，那么您应该learn how to debug your programs。尤其是对于崩溃，您应该学习如何使用调试器来捕获正在发生的崩溃，以及如何在代码中找到它发生的位置。

在不创建新节点的情况下使用 map 实现 trie

Implementation of trie with map without creating new nodes

c++

dictionary

trie