구조 전달 목록 항목이 사라지고 있습니까?

Question

이 코드 조각은 내 신경을 상당히 고갈시키고 있습니다. 잠시 동안 디버깅을 해본 적이 있는데, C++에 녹슬 었는지 믿을 수 없습니다.

몇 가지 간단한 알고리즘을 실행하기 위해 그래프를 모델링하려고하지만 잘 작동하지 않는 것 같습니다. 모든 정점에는 자신의 이웃에 대한 전달 목록이 포함되어 있지만 요소를 삽입 할 때 분명히 존재합니다. 인쇄 기능에 도달 할 때까지는; 이때 전달 목록은 비어 있습니다. 범위 지정이 .. 어떤 행운 중 하나 .. 기존 정점에 대한 참조를 유지하기 위해 그래프를 수정

#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

어제와 같은 문제입니다.

는 이제 C++ 11 std::set의 iterator 항상 const value_type에 대한 반복자이기 때문에 std::set

• 요점을 되풀이 해보자. 이는 std::set의 항목을 변경할 때이 항목을 데이터 구조의 다른 위치에 배치해야하기 때문입니다.

• 우리가 std::set에 무언가를 삽입

는 두 개의 서명이 제공됩니다

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

그러나 어떤 경우 삽입을 복사 또는 이동 컨테이너에 요소

.

그래서 귀하의 경우 당신은 당신이 (당신이 삭제되지 않습니다 그런데! 당신은 Valgrind의를 사용하여 확인 할 수있는, 많은 메모리를 누출) 메모리를 할당

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

먼저 수행 할 때. 그런 다음 정점 복사본을 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; 
  

• 이 하나 _next이 유형이 있기 때문에, 당신은 _next을 선언 한 후 감각 Neighbors의 유형을 선언하지 않습니다

  typedef forward_list<Vertex*> Neighbors; 
  

  .

• 사용 const whereever을 수행 할 수 있습니다, 그리고 당신이 할 수있는 (나는 이미 당신이 어제 말했다) whereever cbegin/cend는, 예를 들면 :

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

  이 여기에 차이를하지 않습니다,하지만 당신은을 변경하는 경우 어떤 점에서 의 유형은 begin()는

Answer 2

그것에 대한 해설있을 수 있기 때문에

나는 새로운 aswell를 사용하여 forward_list를 할당하려고했습니다. 나는 아직도 이것을 고쳐야하는 이유를 모르지만 헤드 업을주는 느낌을 주었다.