C ++ изменение объекта в векторе не работает

Question

Я хочу реализовать tr ie, используя вектор для хранения узлов, но каким-то образом мой метод вставки не работает. Мне удалось построить структуру данных tr ie, используя другую реализацию, но я хотел бы понять, почему моя текущая реализация не работает.

Работает (не на основе индекса хранения дочерних элементов / ссылок):

struct Trie {
   struct Trie *references[26];
   bool end; //It is true if node represents end of word.
};

НЕ РАБОТАЕТ (на основе индекса хранения дочерних элементов / ссылок):

struct node {
    int references[26] = {0};
    bool end; 
};

Это не работает из-за неисправной функции вставки.

void insert_word(string s){
    node *current_node = &trie[0];
    // current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
    for(int i=0;i<s.size();i++){
        print_trie();
        int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
        int next_index = current_node->references[letter_num];
        cout << "letter num: " << letter_num << " next index: " << next_index << endl;
        if(next_index == 0){
            node new_node;
            trie.push_back(new_node);
            current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
            cout << "new value: ";
            for(auto c:current_node->references)
                cout << c << " ";
            cout << endl;
            cout << "in for" << endl;
            print_trie();
            current_node = &trie.back();
        } else{
            current_node = &trie[next_index];
        }
    }
    current_node->end = true;
}

Проблема в том, что, когда я обращаюсь к current_node как к ссылке на объект с вектором tr ie, и я меняю его значение. Объект / узел в векторе tr ie не всегда обновляется. Он работает во второй строке, но дальше как-то перестает работать. Я хотел бы понять, почему.

Вот небольшая отладочная программа, которую я написал, чтобы упростить проблему. Здесь все работает нормально.

    n1.references[0] = 1;
    n2.references[0] = 2;
    n3.references[0] = 3;

    trie.push_back(n1);
    trie.push_back(n2);
    trie.push_back(n3);

    node *n = &trie[0];
    n->references[0] = 10; // Tree is updated properly
    n = &trie[1];
    n->references[0] = 11; // Tree is updated properly

Можете ли вы помочь мне понять, почему функция вставки не работает должным образом?

РЕДАКТИРОВАТЬ: минимальный рабочий пример

#include <vector>
#include <string>
#include <iostream>

using namespace std;

struct node
{
    int num_words;
    int references [26] = {0};
    bool end; 
};

vector<node> trie;
int n;


void print_trie(){
    cout << "#### NEW PRINT TRIE ##### " << endl;
    for(int i=0;i<trie.size();i++){
        cout << "node " << i << ": ";
        for(int j=0;j<26;j++)
            cout << trie[i].references[j] << " ";
        cout << endl;
    }
}

void insert_word(string s){
    node *current_node = &trie[0];
    // current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
    for(int i=0;i<s.size();i++){
        print_trie();
        int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
        int next_index = current_node->references[letter_num];
        cout << "letter num: " << letter_num << " next index: " << next_index << endl;
        if(next_index == 0){
            node new_node;
            trie.push_back(new_node);
            current_node->references[letter_num] = trie.size()-1; // DOESN'T WORK! Node in Trie is NOT UPDATED
            cout << "new reference value of node: ";
            for(auto c:current_node->references)
                cout << c << " ";
            cout << endl;
            current_node = &(trie[trie.size()-1]);
        } else{
            current_node = &trie[next_index];
        }
    }
    current_node->end = true;
}



int main()
{
    node root;
    trie.push_back(root);
    insert_word("hallohallo");
    return 0;
}

Answer 1

Каждый раз, когда std::vector<T> подвергается операции изменения размера, все итераторы и указатели на элементы становятся недействительными . Используя ваш mcve в качестве примера того, где это сходит с рельсов, рассмотрите отмеченные линии:

void insert_word(string s){
    node *current_node = &trie[0];  // **HERE
    for(int i=0;i<s.size();i++){
        print_trie();
        int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
        int next_index = current_node->references[letter_num];
        cout << "letter num: " << letter_num << " next index: " << next_index << endl;
        if(next_index == 0){
            node new_node;
            trie.push_back(new_node); //** RESIZE
            current_node->references[letter_num] = trie.size()-1;
            cout << "new reference value of node: ";
            for(auto c:current_node->references)
                cout << c << " ";
            cout << endl;
            current_node = &(trie[trie.size()-1]); // **HERE
        } else{
            current_node = &trie[next_index]; // **HERE
        }
    }
    current_node->end = true;
}

В каждом месте, отмеченном // **HERE, вы храните указатель на объект, размещенный в вашем векторе , но строка, помеченная // **RESIZE, может (и будет) изменять размер с помощью копирования / перемещения / et c всего вектора после достижения емкости. Это означает, что current_node больше не указывает на действительный объект, является висящим указателем, но ваш код не имеет смысла и переходит в неопределенное поведение .

Есть пара способов решения этой проблемы. Вы можете reserve определить емкость с самого начала, если знаете ее заранее, но для более надежного решения не используйте указатели для начала. если вы перечислите с помощью index вместо указателя, ваше решение станет следующим:

void insert_word(std::string s)
{
    size_t idx = 0;

    for(int i=0;i<s.size();i++){
        print_trie();
        int letter_num = static_cast<int>(tolower(s[i])) - static_cast<int>('a');
        size_t next_index = trie[idx].references[letter_num];
        std::cout << "letter num: " << letter_num << " next index: " << next_index << std::endl;
        if(next_index == 0){
            trie.emplace_back();
            trie[idx].references[letter_num] = trie.size()-1;
            std::cout << "new reference value of node: ";
            for(auto c : trie[idx].references)
                std::cout << c << ' ';
            std::cout << std::endl;
            idx = trie.size()-1;
        } else{
            idx = next_index;
        }
    }
    trie[idx].end = true;
}

Обратите внимание, как все экземпляры current_node были заменены на trie[idx]. А изменение «текущего узла» теперь просто вопрос изменения значения idx, что актуально даже при изменении размера базового вектора.

Answer 2

, которое может быть вызвано несоответствием типов int назначено size_t
try ... = (int)trie.size()-1

#include <vector>
#include <iostream>
using namespace std;

struct node{
    int num_words;
    int references [26] = {};   //........... int
    bool end; 
};

vector<node> trie;
int n;

void print_trie(){
    cout << "#### NEW PRINT TRIE ##### " << endl;
    for(int i=0;i<trie.size();i++){
        cout << "node " << i << ": ";
        for(int j=0;j<26;j++)
                cout << trie[i].references[j] << " ";
        cout << endl;
    }
}

void insert_word(const string& s){
    node *current_node = &trie[0];
    // current_node->references[4] = 9999 WORKS! Node in Trie is UPDATED
    for(int i=0;i<s.size();i++){
        print_trie();
        int letter_num = int(tolower(s[i]) - 'a');
        int next_index = current_node->references[letter_num];
        cout << "letter num: " << letter_num << " next index: " << next_index << endl;
        if(next_index == 0){
                node new_node;
                trie.push_back(new_node);
                current_node->references[letter_num] = (int)trie.size()-1; //....size_t  DOESN'T WORK! Node in Trie is NOT UPDATED
                cout << "new reference value of node: ";
                for(auto c:current_node->references)
                    cout << c << " ";
                cout << endl;
                current_node = &(trie[trie.size()-1]);
        } else{
                current_node = &trie[next_index];
        }
    }
    current_node->end = true;
}



int main()
{
    node root;
    trie.push_back(root);
    insert_word("hallohallo");
    return 0;
}