Кажется, вставка базового узла со списком односвязных списков нарушает мой код на C ++?

Question

Классы односвязных списков и узлов и начало функции main, где я написал краткое описание функциональности кода. Проблема в конце функции main. Я написал «...» вместо того, что я считаю нерелевантным кодом, потому что он просто анализирует строки и присваивает их массиву string temp_hold[3].

#include <bits/stdc++.h>
using namespace std;

class Node {
  public:
    string value;
    string attr;
    string tagname;
    Node *next;

    Node(string c_tagname, string c_attr, string c_value) {
        this->attr = c_attr;
        this->value = c_value;
        this->tagname = c_tagname;
        this->next = nullptr;
    }
};

class SinglyLinkedList {
  public:
    Node *head;
    Node *tail;

    SinglyLinkedList() {
        this->head = nullptr;
        this->tail = nullptr;
    }

    void insert_node(string c_tagname, string c_attr,string c_value) {
        Node *node = new Node(c_tagname,c_attr, c_value);

        if (!this->head) {
            this->head = node;
        } else {
            this->tail->next = node;
        }
        this->tail = node;
    }
};

int main(int argc, char **argv) {
    /* storage is a vector holding pointers to the linked lists
       linked lists are created and the linked list iterator sll_itr is incremented when
       previous line begins with '</' and the currentline begins with '<'
       linked lists have nodes, which have strings corresponding to tagname, value, and attribute
    */
    SinglyLinkedList *llist = new SinglyLinkedList();
    vector<SinglyLinkedList*> sllVect;
    sllVect.push_back(llist);
    auto sll_itr = sllVect.begin();

    string temp_hold[3];

    // to determine new sll creation
    bool prev = false;
    bool now = false;


    //input
    int num1, num2;

    cin >> num1; cin >> num2;

    //read input in 
    for (int i = 0; i <= num1; ++i) {
        string line1, test1;
        getline(cin, line1);
        test1 = line1.substr(line1.find("<") + 1);

        //determine to create a new linked list or wait
        if (test1[0] == '/') {  
            prev = now;
            now = true; 
        } else {
            //make a node for the data and add to current linked list
            if (i > 0) {    
                prev = now;
                now = false;

                //if last statement starts with '</' and current statment starts with '<' 
                // then start a new sll and increment pointer to vector<SinglyLinkedList*>
                if (prev && !now) { 
                    SinglyLinkedList *llisttemp = new SinglyLinkedList();
                    sllVect.push_back(llisttemp);
                    sll_itr++;
                }
            }   

            //parse strings from line
            int j = 0;
            vector<string> datastr;
            vector<char> data;
            char test = test1[j];

            while (test) {  
                if (isspace(test) || test == '>') {
                    string temp_for_vect(data.begin(),data.end());
                    if (!temp_for_vect.empty()) {
                        datastr.push_back(temp_for_vect);
                    }
                    data.clear();
                } else
                if (!isalnum(test)) {
                } else {
                    data.push_back(test);
                }
                j++;
                test = test1[j];
            } 

            //each node has 3 strings to fill
            int count = 0;
            for (auto itrs = datastr.begin(); itrs!=datastr.end(); ++itrs) {
                switch (count) {
                  case 0:
                    temp_hold[count]=(*itrs);
                    break;
                  case 1:
                    temp_hold[count]=(*itrs);
                    break;
                  case 2:
                    temp_hold[count]=(*itrs);
                    break;
                  default:
                    break;
                }
                count++;
            }
        }

        cout << "before storing node" << endl;
        (*sll_itr)->insert_node(temp_hold[0], temp_hold[1], temp_hold[2]);

        cout << "after" << endl;
    } 
    cout << "AFTER ELSE" << endl;
    return 0;
}

А вот строка, которая нарушает код , auto sll_itr разыменовывается, что означает, что *sll_itr теперь является SinglyLinkedList*, и мы можем вызвать insert_node(string, string, string), чтобы добавить узел в текущий связанный список. Однако, когда я сохраняю строку, что-либо после скобки оператора else не запускается, что означает, что cout<<"AFTER ELSE"<< endl; не срабатывает. Если я удалю строку insert_node, то программа запустит cout<<"AFTER ELSE"<< endl; Я не уверен, в чем проблема.

        (*sll_itr)->insert_node(temp_hold[0],temp_hold[1],temp_hold[2]);

        cout << "after" << endl;
    } //NOT HANGING. This closes an else statement.

    cout << "AFTER ELSE" << endl;
    return 0;
} 

Скомпилировано как g++ -o myll mylinkedlist.cpp, а затем myll.exe < input.txt И input.txt содержит

8 3
<tag1 value = "HelloWorld">
<tag2 name = "Name2">
</tag2>
</tag1>
<tag5 name = "Name5">
</tag5>
<tag6 name = "Name6">
</tag6>

Answer 1

Ваш связанный список не проблема, по крайней мере, не проблема здесь .

Рецепт для создания катастрофы: сохранение, обращение и, возможно, манипулирование итератором в динамической коллекции c, которая потенциально делает недействительными итераторы при модификации контейнера. Ваш код делает именно это. Отбрасывая всю разницу между:

vector<SinglyLinkedList*> sllVect;
sllVect.push_back(llist);
auto sll_itr = sllVect.begin();

....

SinglyLinkedList *llisttemp = new SinglyLinkedList();
sllVect.push_back(llisttemp); // HERE: INVALIDATES sll_iter on internal resize
sll_itr++; // HERE: NO LONGER GUARANTEED VALID; operator++ CAN INVOKE UB

Чтобы решить эту проблему, у вас есть два варианта:

• Использовать контейнер, который не делает недействительными итераторы при push_back. На самом деле есть только два контейнера последовательности, которые соответствуют этому описанию: std::forward_list и std::list.
• Измените ваш алгоритм на ссылку с помощью index `, а не с помощью итератора. То есть, вы можете выполнить l oop, пока индексированный элемент не достигнет конца контейнера, а затем прервать его.

Отличное обсуждение контейнеров, которые делают / не делают недействительными указатели и итераторы можно найти здесь . Это стоит прочитать.