Структурировать пункты списка форвардов исчезают?

Question

Этот кусок кода действует мне на нервы. Некоторое время я отлаживал его, не могу поверить, насколько я ржавый на C++.

Я пытаюсь смоделировать график для запуска некоторых простых алгоритмов, но, похоже, это не очень хорошо работает. Каждая вершина содержит прямой список своих соседей, однако при вставке элементов они явно присутствуют. До тех пор, пока я не достигну функции печати; в это время список пересылки пуст.

Я попытался выделить forward_list, используя new aswell, так как определение области видимости может быть объяснением для этого.. Там тоже не повезло..

#include <iostream>
#include <vector>
#include <set>
#include <forward_list>
#include <fstream>

using namespace std;

typedef struct Vertex Vertex;

struct Vertex {
    unsigned id;
    forward_list<Vertex*>_next;

    bool operator < (const Vertex &other) const { return id < other.id; };
};

typedef set<Vertex> Graph;
typedef vector<Vertex*> Index;
typedef pair<unsigned, unsigned> Edge;
typedef forward_list<Vertex*> Neighbors;


// Function:    process_line()
// Purpose:     process a specific line from the file.
// Params:      line to process
Edge process_line(string line){
    unsigned vertex_from;
    unsigned vertex_to;

    int idx = line.find(" ");

    vertex_from = (unsigned)stoul(line.substr(0, idx));
    vertex_to = (unsigned)stoul(line.substr(idx+1, line.length()));

    return make_pair(vertex_from, vertex_to);
}


// Function:    load_graph()
// Purpose:     load graph from file in relation
// Params:      path, and reference to graph and index
bool load_graph(string file_path, Graph &graph, Index &index){
    string line;
    ifstream file(file_path);
    bool foundEmptyLine = false;

    if(file.is_open()){
        while(getline(file, line)){
            if(line.empty()){
                foundEmptyLine = true;
                continue;
            }

            if(!foundEmptyLine){
                // processing vertexes
                Vertex *vertex = new Vertex;

                vertex->id = stoul(line);
                graph.insert(*vertex);
                index.emplace_back(vertex);
            }else{
                //Processing relations
                Edge edge = process_line(line);

                Vertex* neighbor = index.at(edge.second);
                Vertex* source = index.at(edge.first);

                // Lookup edge in index
                source->_next.emplace_front(neighbor);

                // ITEMS PRESENT! <----------------------
            }
        }
        file.close();
    }else{
        cout << "Unable to open " << file_path;
        return false;
    }

    return true;
}


void print_graph(Graph &graph){
    for(Graph::iterator it = graph.begin(); it != graph.end(); ++it){
        Neighbors neighs = it->_next;

        cout << "Node: " << it->id << " neighbors: " neighs.empty();

        cout << endl;
    }
}


// Entry point.
int main() {
    Graph graph;
    Index index;

    load_graph("graph_1.txt", graph, index);
    print_graph(graph);
}

Answer 1

Это опять та же проблема, что и вчера.

Попробуем повторить std::set

• Начиная с C++11 iterator из std::set всегда итератор const value_type, Это потому, что когда мы меняем запись std::set эта запись должна быть размещена где-то еще в структуре данных.

• Когда мы вставляем что-то в std::setпредоставляются две подписи:

  pair<iterator,bool> insert (const value_type& val);
  pair<iterator,bool> insert (value_type&& val);
  

  Но в любом случае вставка копирует или перемещает элемент в контейнер.

Так что в вашем случае, когда вы делаете

Vertex *vertex = new Vertex;
vertex->id = stoul(line);
graph.insert(*vertex);
index.emplace_back(vertex);

Сначала вы выделяете память (которую, кстати, вы никогда не удаляете! У вас будет много утечки памяти, которую вы можете проверить с помощью valgrind). Затем вы вставляете копию своей вершины в std::set и вставьте указатель вашей выделенной памяти в std::vector,

Когда вы потом делаете

Vertex* neighbor = index.at(edge.second);
Vertex* source = index.at(edge.first);

// Lookup edge in index
source->_next.emplace_front(neighbor);

Вы берете вершину из своего вектора (помните, это вершина, которую вы наделили new). И вставить другую вершину (также динамически размещенную) в ее std::forward_list, Но: они не имеют ничего общего с вершиной, которая находится в вашем std::set,

Поэтому, когда вы потом пройдете через std::set:

for (Graph::iterator it = graph.begin(); it != graph.end(); ++it)

Это совершенно не связано с тем, что вы делали, когда вставляли края - и все std::forward_listс пустыми.

Примечания стороны:

• Это то, что вы должны были использовать в C, но не в C++!

  typedef struct Vertex Vertex;
  

• Этот вы должны разместить выше:

  typedef forward_list<Vertex*> Neighbors;
  

  Не имеет смысла объявлять тип Neighbors после того как вы объявили _next, так как _next имеет этот тип.

• использование const везде, где вы можете, и cbegin / cend где вы можете (я уже говорил вам это вчера), например:

  for(Graph::iterator it = graph.cbegin(); it != graph.cend(); ++it){
  

  Это не имеет значения здесь, но если вы измените тип graph в какой-то момент, begin() может вернуть итератор value_type вместо const value_type

Answer 2

Изменен график, чтобы сохранить ссылки на существующие вершины. Я все еще не уверен, почему это исправило это - но чувствовал, что хотел дать хедз-ап.