结构转发列表项目消失？

Question

这段代码让我很紧张。已经调试了一段时间，不能相信我在C++上有多生锈。

我想模拟一个图运行一些简单的算法，但似乎并没有这么好。每个顶点都包含一个前向列表给他的邻居，但是当插入这些元素时，他们明显存在。直到我到达打印函数;那时候的转发名单是空的。

我试图用new分配的藏汉修饰符Modifiers，因为作用域可能是它的一个解释..没有运气..任何

#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 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 s为空。

旁注：

• 这是你不得不在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){ 
  

  它不会在这里做一个区别，但如果你改变了在某些时候的类型，begin()可能会返回一个迭代器value_type而不是const value_type

Answer 2

修改图表，以保持现有的顶点引用。我仍然不确定为什么这样修复它 - 但是感觉就像是单挑一样。