結構轉發列表項目消失？

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

修改圖表，以保持現有的頂點引用。我仍然不確定爲什麼這樣修復它 - 但是感覺就像是單挑一樣。