Cannot insert element in std::set of iterator to std::list

Question

Before showing the code which gives me the compiler error I want to explain briefly why I need a set of iterators to a list, just to avoid comments like "do you really need that?" or maybe to change them into comments "Your code can be solved in this way... However I should have approached the original problem like this". You can so skip the read and go directly to last section ("The not compiling code").

The reason behind

I build a directed bipartite weighed graph. Each arc is stored in a struct

typedef struct edge_ {
    int src;
    int des;
    double w; //weight of the arc
}edge;

I store information about the graph using a list of such structs.

list<edge> all_edges;

After that, I sort the arcs by weight and I cycle them in a loop, from the lightest to the heaviest. Since I want to remove some elements from all_edges within the loop, at the beginning of each loop step I call

list<edge>::iterator smallest = all_edges.begin();

In each step of that loop, after having done some things with the weight of the arc, I want to remove from the graph all the nodes departing from src or ending in des. For doing so, during the construction of the graph, I have created two vectors, one for each component of the bipartite graph, indexed by their elements, and at each position of each vector I store a list of all the iterators to an edge of all_edges which departs from the node corresponding to the position of the vector considered. The code is the following ("small" and "big" are the way I identifies the two components of the bipartite graph)

vector<list<list<edge>::iterator>> edges_from_small(small.size());
vector<list<list<edge>::iterator>> edges_from_big(big.size());

And this is the code which I use for filling the above vectors

//inside a loop...
    edge e;
    e.src = ...
    e.des = ...
    e.w = ...
    all_edges.push_back(e);                
    edges_from_small[e.src].push_back(--(all_edges.end()));
    edges_from_big[e.des].push_back(--(all_edges.end()));

Let say that I want to remove the edge e. I would be tempted to cycle all elements of edges_from_small[e.src] and for each of them to call all_edges.erase(iterator), but doing so, since an edge can be listed in both edges_from_small and edges_from_big, I would end trying to remove an element using a dereferenced iterator!

Set would be a solution! I would just need to create a set of list<edge>::iterator and to fill it with the elements of edges_from_small[e.src] and edges_from_big[e.des] and then, since duplicates gets removed, to delete all the elements from the list all_edges.

But my code does not compile, it gives me an error which I cannot understand, at one of the following lines:

set<list<edge>::iterator> to_remove;

for (auto it = edges_from_small[smallest->src].begin(); it != edges_from_small[smallest->src].end(); ++it) {
        to_remove.insert(*it); //error here! 
    }
for (auto it = edges_from_big[smallest->des].begin(); it != edges_from_big[smallest->des].end(); ++it) {
        //to_remove.insert(*it); //error here!
    }
for (auto it = to_remove.begin(); it != to_remove.end(); ++it) {
        all_edges.erase(*it);
    } 

The compiler gives me a quite big output (all referred to the line above), for the moment I put only the first line and the last line, that I think are the most indicative.

g++ -ggdb3 -g -O0 -std=c++14 -Wall -Werror -o compare main.cpp peaks.cpp common.cpp compare.cpp parameters.cpp 
In file included from compare.cpp:1:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iostream:38:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/ios:216:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__locale:15:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/string:439:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:628:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:606:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:344:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__functional_base:63:21: error: 
      invalid operands to binary expression ('const std::__1::__list_iterator<_edge,
      void *>' and 'const std::__1::__list_iterator<_edge, void *>')
        {return __x < __y;}
                ~~~ ^ ~~~
....................MUCH MORE OUTPUT....................
compare.cpp:226:23: note: in instantiation of member function
      'std::__1::set<std::__1::__list_iterator<_edge, void *>,
      std::__1::less<std::__1::__list_iterator<_edge, void *> >,
      std::__1::allocator<std::__1::__list_iterator<_edge, void *> > >::insert'
      requested here
            to_remove.insert(*it);
                      ^
1 error generated.
make: *** [compare] Error 1

Compilation exited abnormally with code 2 at Tue Sep  5 17:34:39

Any idea about what is wrong with that line?

The not compiling code

typedef struct _edge {
    int src;
    int des;
    double w; //weight of the arch
}edge;

list<edge> all_edges;
vector<list<const list<edge>::iterator>> edges_from_small(small.size());
vector<list<const list<edge>::iterator>> edges_from_big(big.size());

//graph construction    
//for loop ...
    edge e;
    e.src = ...
    e.des = ...
    e.w = ... 
    all_edges.push_back(e);
    edges_from_small[e.src].push_back(--(all_edges.end())); 
    edges_from_big[e.des].push_back(--(all_edges.end()));
//end of loop

list<edge>::iterator smallest = all_edges.begin();
set<list<edge>::iterator> to_remove;
for (auto it = edges_from_small[smallest->src].begin(); 
     it != edges_from_small[smallest->src].end(); ++it) {
    to_remove.insert(*it); //<--- COMPILER ERROR HERE, you can see the error description in the last lines of the previous paragraph
}    

Answer 1

Already existing answers are correct about causes of your problems, but you may want to consider boost::bimap and see if that fits your problem(hard for me to understand the algorithm you are doing without seeing the entire code you wrote).

Answer 2

std::list::iterators can't be ordered because there is no function or operator to compare them (wrt less/greater).

Use a std::unordered_set instead, this does not need to order the elements, it uses a hash of the elements to place them into buckets. You probably have to provide a hash function, just place an overload of std::hash in the namespace std for the std::unordered_set to find and use it.
Also note that std::unordered_set has an average constant-time complexity for insertions versus the logarithmic time complexity of std::set

Answer 3

The problem you're facing is that std::set requires elements to implement operator<(a,b) (or, in fact, the declaration where you don't specify comparator uses std::less). Now, std::list's iterator is BidirectionalIterator which lacks said opeator.