访问没有字符的字符串的第一个字符 [英] Accessing the first Character of a String with no Characters

问题描述

我正在C ++中实现后缀trie. Trie构造器的实现可以在下面看到.

I am implementing a suffix trie in C++. The implementation of the Trie contructor can be seen below.

#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()返回表示给定字符的边的位置(如果存在).

I am using two data structures, Node and Edge which have some getters and setters and properties you would expect. The method childLoc() returns the location of an edge (if it exists) representing a given character.

代码可以很好地编译，但是由于某种原因，我在运行时收到此错误:

The code compiles just fine, but for some reason I get this error at runtime:

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)

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

I've been told that this error means I am accessing the first character of an empty string, but I can't see where this is happening in the code.

推荐答案

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

I see two code parts that are potentially responsible for std::out_of_range:

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

First: The following expression might access an empty string at position 0. This might happen as (as shown in the second part), you shrink strings contained in the suffix-vector:

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

第二，对suffix -vector中的条目进行操作，可能会导致字符串变短:

Second, you operate on the entries in suffix-vector with the risk that the strings are to short:

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

如果第一个操作数(即pos参数)超过数组长度(参见

Operation substr will also yield std::out_of_range if first operand (i.e. pos-argument) exceeds the array length (cf. string::substr):

pos:要复制为子字符串的第一个字符的位置.如果 这等于字符串长度，该函数返回一个空 细绳.如果大于字符串长度，则抛出 超出范围.注意:第一个字符由值0表示 (不是1).

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).

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

For finding out which of these expressions is actually responsible for the exception, I'd suggest to consult your debugger :-)

这篇关于访问没有字符的字符串的第一个字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！