Struct forward list items disapearing?

This piece of code is getting quite on my nerves. Been debugging it for a while, cant believe how rusty i've got on c++.

I'm trying to model a graph to run some simple algorithms on, but that doesn't seem to work out so well. Every vertex contains a forward list to his neighbors, however when inserting the elements their obviously present.. Until I reach the print function; at that time the forward list is empty.

I've tried to allocate the forward_list using new aswell, as scoping could be an explication for it.. No luck there either..

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

Solution

This is once again the same problem as yesterday.

Let's try to recapitulate the std::set

Since C++11 the iterator of a std::set is always an iterator to const value_type. This is because when we change an entry of a std::set this entry would need to be placed somewhere else in the data structure.
When we insert something into a std::set, two signatures are provided:
```
pair<iterator,bool> insert (const value_type& val);
pair<iterator,bool> insert (value_type&& val);
```
But in any case the insertion copies or moves the element into the container.

So in your case when you do

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

First you allocate memory (which by the way you never delete! You will leak much memory, which you can check using valgrind). Then you insert a copy of your vertex into the std::set and insert the pointer of your allocated memory into the std::vector.

When you then later do

Vertex* neighbor = index.at(edge.second);
Vertex* source = index.at(edge.first);

// Lookup edge in index
source->_next.emplace_front(neighbor);

You take the Vertex from your vector (remember, this is the vertex which you allocated with new). And insert another vertex (also dynamically allocated) into its std::forward_list. But: They have nothing to do with the vertex which are in your std::set.

So when you then later go through your std::set:

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

This is completely unrelated to what you did when when inserting the edges - and all std::forward_lists are empty.

Side notes:

This is something you had to use in C, but not in C++!
```
typedef struct Vertex Vertex;
```
This one you should place above:
```
typedef forward_list<Vertex*> Neighbors;
```
It doesn't make sense to declare the type of Neighbors after you declared _next, because _next has this type.
Use const whereever you can, and cbegin / cend whereever you can (I already told you this yesterday), e.g.:
```
for(Graph::iterator it = graph.cbegin(); it != graph.cend(); ++it){
```
It doesn't make a difference here, but if you change the type of graph at some point, begin() may return a iterator to value_type instead of const value_type