c++ - 从文件中读取并有效地将单词添加到树中

Question

我有一个文件作为命令参数的输入。我这样读每一行:

    vector<string> filewords;
     string line;
     while(getline(cin, line){
       filewords.push_back(line);
     }

我还没有找到任何其他方法来从文件中获取字符串，如果我能在一个巨大的字符串中获取全部内容那会很棒，但我还没有找到方法

我以这种方式将单词添加到 trie 中:

    for(const auto &word : *filewords){ 
      if(word.length() >= 3 && word.length() <= 17){
        root->addString(word.c_str());
      }
    }

在将每一行添加到 trie 之前，我需要检查它是否具有一定的长度。添加字符串是:

void Node::addString(const char* word)
{
  if(!mChildren[*word - 'a']) mChildren[*word - 'a'] = new Node(word);
  if(word[1]) mChildren[*word - 'a']->addString(word + 1);
  else mChildren[*word - 'a']->setMarker(true);
}

children 按字母顺序排列，所以 'a' 在位置 0 等等。

Node 是一个具有以下构造函数的类:

Node::Node(const char* a)
{
  mContent = *a;
  mChildren.resize(26);
}

最多有 26 个 child (字母表中的 26 个字母)

我不确定我所做的小优化(制作大小为 26 的 mChildren，将每一行添加到一个 vector ，然后遍历该 vector ...)是否真的值得，或者是否有更好的方法。

我应该让这部分程序持续约 80 毫秒，而现在它需要约 120 毫秒来处理包含约 180.000 个单词的文件。

关于如何优化/降低复杂性/改进代码的任何想法？谢谢!

Answer 1

您的问题没有提到您对该 vector 有任何其他用途。

首先将约 180,000 行读入一个 vector ，然后在该 vector 上迭代，这会浪费大量时间和内存，而且没有明显的增值。

作为阅读单词的一部分，您应该简单地将单词插入到 trie 中。

 string word;

 while(getline(cin, word){
  if(word.length() >= 3 && word.length() <= 17){
    root->addString(word.c_str());
  }
 }