c++ - 访问没有字符的字符串的第一个字符

Question

我正在用 C++ 实现一个后缀 trie。 Trie 构造函数的实现如下所示。

#include <iostream>
#include <cstring>
#include "Trie.hpp"
using namespace std;

Trie::Trie(string T){   
    T += "#";                           //terminating character     
    this->T = T;

    nodes.reserve(T.length() * (T.length() + 1) / 2);   //The number of nodes is bounded above by n(n+1)/2. The reserve prevents reallocation (http://stackoverflow.com/questions/41557421/vectors-and-pointers/41557463) 

    vector<string> suffix;              //vector of suffixes
    for(unsigned int i = 0; i < T.length(); i++)
        suffix.push_back(T.substr(i, T.length()-i));

    //Create the Root, and start from it
    nodes.push_back(Node(""));          //root has blank label
    Node* currentNode = &nodes[0];

    //While there are words in the array of suffixes
    while(!suffix.empty()){

        //If the character under consideration already has an edge, then this will be its index. Otherwise, it's -1.
        int edgeIndex = currentNode->childLoc(suffix[0].at(0));     

        //If there is no such edge, add the rest of the word
        if(edgeIndex == -1){
            addWord(currentNode, suffix[0]);                //add rest of word
            suffix.erase(suffix.begin());                   //erase the suffix from the suffix vector
        }

        //if there is
        else{
            currentNode = (currentNode->getEdge(edgeIndex))->getTo();       //current Node is the next Node
            suffix[0] = suffix[0].substr(1, suffix[0].length());            //remove first character
        }           
    }   
}

//This function adds the rest of a word
void Trie::addWord(Node* parent, string word){  
    for(unsigned int i = 0; i < word.length(); i++){                //For each remaining letter
        nodes.push_back(Node(parent->getLabel()+word.at(i)));       //Add a node with label of parent + label of edge
        Edge e(word.at(i), parent, &nodes.back());                  //Create an edge joining the parent to the node we just added
        parent->addEdge(e);                                         //Join the two with this edge   
    }
}

我正在使用两种数据结构，Node 和 Edge，它们具有您期望的一些 getter 和 setter 以及属性。 childLoc() 方法返回表示给定字符的边(如果存在)的位置。

代码编译得很好，但出于某种原因，我在运行时遇到了这个错误:

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 0) >= this->size() (which is 0)
Aborted (core dumped)

有人告诉我这个错误意味着我正在访问一个空字符串的第一个字符，但我看不到代码中发生了什么。

Answer 1

我看到两个代码部分可能对 std::out_of_range 负责:

首先:以下表达式可能访问位置 0 处的空字符串。这可能会发生(如第二部分所示)，您收缩包含在 suffix-vector 中的字符串:

int edgeIndex = currentNode->childLoc(suffix[0].at(0));

其次，您对 suffix-vector 中的条目进行操作，但存在字符串变短的风险:

suffix[0] = suffix[0].substr(1, suffix[0].length()); 

操作 substr 也将产生 std::out_of_range 如果第一个操作数(即 pos-argument)超过数组长度(参见 string::substr ):

pos: Position of the first character to be copied as a substring. If this is equal to the string length, the function returns an empty string. If this is greater than the string length, it throws out_of_range. Note: The first character is denoted by a value of 0 (not 1).

为了找出这些表达式中的哪一个实际上是导致异常的原因，我建议咨询您的调试器:-)