Discussion :

[ImmoTPA]

Bonjour, je remercie par avance tous ceux qui s'intéresseront à mon problème. J'ai cherché une solution au problème suivant, j'en ai trouvé, aucune n'a marché. Le voici : j'implémente un algorithme de clustering et j'aurai besoin de stocker mes arêtes dans un ensemble qui n'accepte pas les doublons. Pour ce faire j'ai décidé d'utiliser un "unordered_set" . D'après le prototype de la fonction j'ai vu que je devais fournir une fonction de hachage pour mon objet Edge et aussi d'une fonction qui permet de tester l'égalité.

Voici l'une des nombres choses que j'ai testé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename T>
struct MyEdgeHash : public std::unary_function<std::edge<T>, size_t> {
   size_t operator()(const std::edge<T>& e) const
   {
      return hash(e.cost);
   }
};
 
template<typename T>
struct MyedgeEqual : public std::unary_function<std::edge<T>, bool> {
 
   bool operator()(const std::edge<T>& left, const std::edge<T>& right) const
   {
      return (left.vertex1 == right.vertex1 and left.vertex2 == right.vertex2) or (left.vertex1 == right.vertex2 and left.vertex2 == right.vertex1);
   }
}; 
typedef unordered_set<edge<Edge>, MyEdgeHash<Edge>, MyedgeEqual<Edge>> Graph;

Je suis débutant en C++ j'ai essayé d'adapter à mon problème une solution que j'ai trouvé sur le net mais j'obtiens des erreurs du style "extra qualification 'Edge'::on member operator ==

Pourtant j'ai trouvé partout qu'il fallait redéfinir cet opérateur alors je perds un espoir. Merci de votre aide.

[ternel]

Tu as opté pour un set, bon choix.
Reste à savoir si tu veux une fonction de hashage ou un operateur de comparaison.
set et unordered-set sont tes deux choix.

Si tes ajouts ne sont pas fréquents, un set est aussi un bon choix.

Si ton problème est incapable d'avoir des doublons (garantie sur les données), un vector peut tout aussi bien faire l'affaire.

[ImmoTPA]

Bonjour l'éternel et merci de ta réponse, en fait je vais faire des centaines de milliers d'ajouts dans mon unordered_set mais toutes d'un coup ensuite je n'y touche plus. En revanche tu m'as demandé si je voulais une fonction de comparaison ou de hachage mais d'après le prototype de la classe unordered_set j'ai l'impression d'avoir besoin des deux nan ? Ce qui complexifie la chose je trouve c'est que ces templates (que je connais pas tellement en fait) ont l'air de ressembler à la programmation générique en JAVA. Or moi je n'ai pas besoin de pouvoir créer un set de tous les types possibles mais juste un set de Edge. Edge est définie comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
typedef struc {
       string vertex1;
       string vertex2;
       int cost;
};

Algorithmiquement je sais exactement ce que je veux, je voudrais créer un set dans lequel je ne puisse pas mettre 2 arêtes qui soient les mêmes (sinon mon clustering est faussé).

2 arêtes sont les mêmes si elles ont les mêmes sommets de départ et d'arrivée (quitte à faire un swap sur le sommet de départ et d'arrivée de l'une des deux arêtes).

Au point où j'en suis je sais (ou je crois savoir ) qu'il me faut une fonction de hashage pour mon type Edge (pourquoi pas hash en fonction du cost ? ) et une fonction de comparaison que je sais écrire.

Ce que je voudrais savoir c'est si quelqu'un pouvait m'aider à l'écrire avec la syntaxe c++11 car aucun de mes essais n'aboutissent. Merci encore

[JolyLoic]

Je vois pas mal de soucis qui indiquent du code écrit sans vraiment le comprendre...
C'est quoi std::edge ? Il n'y a pas de classe edge dans la bibliothèque standard.
Quand tu utilises MyEdgeHash<Edge>, tu instancie MyEdgeHash avec T valant Edge, donc l'opérateur () de cette classe prend en paramètre un std::edge<Edge>, alors qu'il devrait prendre un Edge pour marcher.
Pourquoi faire de MyEdgeHash un template ? Comme tu le dis, tu n'as pas besoin de généricité ici, tu connais exactement ton type.

Donc: (code non testé)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct MyEdgeHash : public std::unary_function<Edge, size_t> {
   size_t operator()(const Edge& e) const
   {
      return std::hash(e.cost);
   }
};

Sachant que plutôt que de passer un hasher spécifique, je préfère généralement spécialiser std::hash pour mon type (voir le dernier exemple sur http://en.cppreference.com/w/cpp/utility/hash). Comme ça, il sera pris pas défaut partout où il sera requis sans que tu aies besoin de spécifier les paramètres templates qui vont bien.