Accès au premier caractère d'une chaîne sans caractères

Question

J'implémente un suffixe trie en C++. La mise en œuvre du contructeur Trie peut être vue ci-dessous.

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

J'utilise deux structures de données, et NodeEdge qui ont des accesseurs et des propriétés que vous attendez. La méthode childLoc() renvoie l'emplacement d'une arête (si elle existe) représentant un caractère donné.

Le code compile très bien, mais pour une raison quelconque je reçois cette erreur lors de l'exécution:

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) 

On m'a dit que cette erreur signifie que j'accède le premier caractère d'une chaîne vide, mais je ne peut pas voir où cela se passe dans le code.

Answer 1

Je vois deux parties de code qui sont potentiellement responsables de std::out_of_range:

Première: L'expression suivante peut accéder à une chaîne vide à la position 0. Cela peut se produire que (comme indiqué dans la deuxième partie), vous réduisez les chaînes contenues dans le suffix -vector:

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

Deuxièmement, vous opérez sur les entrées dans suffix -vector avec le risque que les chaînes sont à court :

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

opération substr sera également donné std::out_of_range si le premier opérande (par exemple pos -argument) dépasse la longueur du tableau (cf. string::substr):

pos: Position du premier caractère à copier en tant que sous-chaîne. Si est égale à la longueur de la chaîne, la fonction renvoie une chaîne vide. Si cette valeur est supérieure à la longueur de la chaîne, elle renvoie out_of_range. Remarque: Le premier caractère est indiqué par une valeur de 0 (pas 1).

Pour savoir laquelle de ces expressions est réellement responsable de l'exception, je vous suggère de consulter votre débogueur :-)