结构转发列表项消失了吗？

Question

这段代码让我很不安。已经调试了一段时间，无法相信我在 C++ 上的生疏程度。

我正在尝试根据运行一些简单的算法对图进行建模，但效果似乎不太好。每个顶点都包含一个到他的邻居的前向列表，但是当插入元素时它们显然存在......直到我到达打印功能;那时转发列表是空的。

我也尝试使用 new 分配 forward_list，因为范围界定可能是对它的一种解释。也没有运气......

#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

修改了图形以保留对现有顶点的引用。我仍然不确定为什么会修复它——但我想提醒一下。

Answer 2

这又是昨天的问题。

让我们试着概括一下 std::set

自 C++11 起，std::set 的 iterator 始终是 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;
```
声明_next后声明Neighbors的类型没有意义，因为_next有这个类型。
尽可能使用const，尽可能使用cbegin / cend（我昨天已经告诉过你），例如：
```
for(Graph::iterator it = graph.cbegin(); it != graph.cend(); ++it){
```
这里没有区别，但是如果你在某个时候改变了 graph 的类型，begin() 可能会 return 一个迭代器到 value_type共 const value_type

结构转发列表项消失了吗？

Struct forward list items disapearing?

c++

pointers

forward-list