2017-03-04 82 views
0

这段代码让我很紧张。已经调试了一段时间,不能相信我在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); 
} 

回答

1

这又是一个和昨天一样的问题。

让我们尝试概括了std::set

  • 由于C++ 11 std::setiterator始终是一个迭代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

+0

再次感谢您的努力。我错过了这个集合复制元素的事实,与矢量相反。因此,为什么插入参考文件使整个工作成功。在我的工作版本中也使用了const_iterator提示。 – Iso

+0

我建议使用矢量作为您的索引,为邻居设置为图和forward_list 。 – overseas

0

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