Impossible d'insérer l'élément dans std :: set d'itérateur à std :: list

Question

Avant d'afficher le code qui me donne l'erreur du compilateur, je veux expliquer brièvement pourquoi j'ai besoin d'un ensemble d'itérateurs à une liste, juste pour éviter des commentaires comme " As-tu réellement besoin de cela?" ou peut-être pour les transformer en commentaires "Votre code peut être résolu de cette façon ... Cependant, j'aurais dû aborder le problème original comme ça". Vous pouvez donc ignorer la lecture et aller directement à la dernière section ("Le code qui ne compile pas").

La raison derrière

Je construis un graphe orienté biparti pesé. Chaque arc est stocké dans une structure

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

Je stocke des informations sur le graphique en utilisant une liste de ces structures.

list<edge> all_edges; 

Après cela, je trie les arcs en poids et le cycle I eux dans une boucle, du plus léger au plus lourd. Comme je veux supprimer certains éléments de all_edges dans la boucle, au début de chaque étape de la boucle que j'appelle

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

Dans chaque étape de cette boucle, après avoir fait des choses avec le poids de l'arc, je vouloir supprimer du graphique tous les nœuds partant de src ou se terminant par des. Pour ce faire, lors de la construction du graphe, j'ai créé deux vecteurs, un pour chaque composante du graphe bipartite, indexés par leurs éléments, et à chaque position de chaque vecteur je stocke une liste de tous les itérateurs à un bord de all_edges qui part du noeud correspondant à la position du vecteur considéré. Le code est le suivant (« petits » et « grands » sont la façon dont j'identifie les deux composantes du graphe biparti)

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

Et voici le code que j'utilise pour remplir les vecteurs ci-dessus

//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())); 

Dire que je veux supprimer le bord e

Je serais tenté de cycler tous les éléments de edges_from_small[e.src] et pour chacun d'eux d'appeler all_edges.erase(iterator), mais ce faisant, comme un bord peut être répertorié à la fois edges_from_small et edges_from_big, je finirais d'essayer de supprimer un élément en utilisant un itérateur déréférencé!

L'ensemble serait une solution! Je voudrais juste créer un ensemble de list<edge>::iterator et de le remplir avec les éléments de edges_from_small[e.src] et edges_from_big[e.des] puis, puisque les doublons sont supprimés, de supprimer tous les éléments de la liste all_edges.

Mais mon code ne compile pas, il me donne une erreur que je ne comprends pas, à l'une des lignes suivantes:

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

Le compilateur me donne une très grande production (tous visés à la ligne ci-dessus), pour l'instant je ne mets que la première ligne et la dernière ligne, que je pense être les plus indicatives.

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 

Une idée de ce qui ne va pas avec cette ligne?

Le code ne compilant

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

std::list::iterator s ne peut pas être commandé car il n'y a pas de fonction ou d'opérateur pour les comparer (par rapport à moins/plus grand).

Utilisez à la place un std::unordered_set, cela n'a pas besoin de commander les éléments, il utilise un hachage des éléments pour les placer dans des seaux. Vous devez probablement fournir une fonction de hachage, il suffit de placer une surcharge de std::hash dans le namespace std pour le std::unordered_set pour le trouver et l'utiliser.
Notez également que std::unordered_set a une complexité en temps constant moyenne des insertions par rapport à la complexité temporelle logarithmique de std::set

Answer 2

Le problème que vous êtes confronté est que std::set requires elements to implement operator<(a,b) (la déclaration où vous ne spécifiez pas ou, en fait, comparateur utilise std :: moins). Maintenant, std::list's iterator est BidirectionalIterator qui manque dudit opeator.

Answer 3

réponses déjà existantes sont correctes sur les causes de vos problèmes, mais vous pouvez envisager boost::bimap et voir si cela correspond à votre problème (difficile pour moi de comprendre l'algorithme que vous faites sans voir le code entier que vous avez écrit).