结构与forward_list指针本身

Question

我正在实现一个图形的非常simpel模型，其中我有一个包含指向它的邻居的转发列表的结构。这些邻居依次是同一类型的结构。

#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; 
}; 

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; 
      } 

      if(!foundEmptyLine){ 
       // processing vertexes 
       Vertex *vertex = new Vertex; 

       vertex->id = stoul(line); 
       graph.emplace(*vertex); 
       index.emplace_back(vertex); 
      }else{ 
       // Processing relations 
       Edge edge = process_line(line); 
       Vertex* neighbor = index.at(edge.second); 

       // Lookup edge in index 
       index.at(edge.first)->_next.push_front(neighbor); 
      } 
     } 
     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){ 
     // Print item. 
     cout << "Node: " << it->id << endl << "Neighbors:"; 

     for(Neighbors::iterator neigh = it->_next.begin(); neigh != it->_next.end(); ++neigh){ 
      // Print item. 
      cout << (*neigh)->id; 
     } 
    } 
} 


// Entry point. 
int main() { 
    Graph graph; 
    Index index; 

    load_graph("graph_1.txt", graph, index); 


    print_graph(graph); 
} 

这一切都工作了，直到我尝试循环的顶点在图中，随后环顶点的所有邻居。 （print_graph函数）我得到这个错误：

error: no viable conversion from 'const_iterator' (aka '__forward_list_const_iterator *>') to 'Neighbors::iterator' (aka '__forward_list_iterator *>')

在此先感谢。

Answer 1

此错误的原因非常微妙。 std::set的iterator类型几乎与其const_iterator类型相同。这是有道理的;一个集合需要保证在任何时候每个元素都是独一无二的。如果您可以自由修改元素，它将无法提供保证。

考虑下面的行：

for(Graph::iterator it = graph.begin(); it != graph.end(); ++it){ 

it是iterator作用就像const_iterator。你不能修改迭代器指向的内容。

您可以验证这一点，如下所示：

it->id = 1; // will result in a compilation error 

然后就是这条线：

for(Neighbors::iterator neigh = it->_next.begin(); neigh != it->_next.end(); ++neigh){ 

it->_next是forward_list<Vertex*> const由于上述原因，并呼吁begin()因此它返回一个const_iterator 。

这是最终导致错误的原因：您无法将const_iterator转换为iterator。

的治疗很简单：只需使用const_iterator：

for(Neighbors::const_iterator neigh = it->_next.begin(); neigh != it->_next.end(); ++neigh){ 

甚至更​​好，使用auto：

for(auto neigh = it->_next.begin(); neigh != it->_next.end(); ++neigh){ 

或者更简单的，基于范围的for循环：

for (auto const& neigh : it->_next) { 
    // Print item. 
    cout << neigh->id; 
} 

---

请注意，一旦这个特定的错误得到解决，你会发现其他的。你也错过了一个必要的#include <string>，它使你的代码与平台相关（即它与GCC协同工作，但与Visual C++不兼容）。

Answer 2

问题是

Graph::iterator it = graph.begin() 

将返回Graph::iterator类型，其等于Graph::const_iterator的迭代器。请参阅http://en.cppreference.com/w/cpp/container/set（请注意，这随C++ 11而改变）。

所以，当你再调用

Neighbors::iterator neigh = it->_next.begin() 

这将返回一个std::forward_list::const_iterator（因为*it是const），当然你不能分配给std::forward_list::iterator。

无论如何，我会建议使用此auto的类型，并且，因为你不需要写访问，无论如何，你应该使用cbegin()，这在任何情况下返回const_iterator。