Tri du set pour une POD structure

Bonjour,

Le conteneur <set> de la stl permet de collecter une liste d'objets uniques triée.

Lorsque je créé une structure contenant un string, un double, un autre string etc... quel critère est utilisé pour trier mes objets dans le set ? Je n'ai pas défini d'oprateur particulier de comparaison pour ma structure mais ça compile quand même ...

Il n'y a pas de critère défini par défaut.

Si ton code compile, c'est sans doute probablement parce que tu n'as pas utilisée encore ton set. Actuellement, le code suivant compile :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <set>   using namespace std;   class A { int i; };     int main() { set<A> s; A a; //s.insert(a); return 0; }

---

Mais dès qu'on enlève les commentaires, il cessera de compiler. Les templates ne sont compilés que lorsqu'on en a besoin, et dans mon exemple, avant que l'on veuille insérer un élément dans un set, l'opérateur< n'étais pas requis.

A noter que dans une prochaine version de le norme, ce genre d'erreur sera probablement détecté plus tôt (et avec de meilleurs messages) grâce aux concepts.

Je viens de m'apercevoir d'une chose que j'avais totalement zappé :

Je n'ai pas un set d'objets A mais plutôt de pointeurs vers des objets A.

Et j'ai bien des insertions déjà.

J'imagine que le tri de pointeurs vers n'importe quoi est une chose que le compilo arrive à gérer, mais à mon avis pas du tout comme je l'attends.

Je devrais pouvoir tenter de redéfinir l'opérateur < pour les pointeurs vers mon objet A, je vais faire le test.

Citation:

---

Envoyé par NiamorH

J'imagine que le tri de pointeurs vers n'importe quoi est une chose que le compilo arrive à gérer, mais à mon avis pas du tout comme je l'attends.

---

Il trie donc tes objets selon l'ordre dans lequel ils apparaissent en mémoire...

Tout à fait.

Mais je suis un peu bloqué... :

Citation:

---

Envoyé par msdn

Code:

---

1 2 3 4 5 6

// C2803.cpp // compile with: /c class A{}; bool operator< (const A *left, const A *right); // C2803 // try the following line instead // bool operator< (const A& left, const A& right);

---

---

Impossible de redéfinir le comportement de comparaison de pointeurs vers mes objets.
Et ça me gène de devoit faire mon set sur des données non pointeurs. La solution que je vois pour éviter de faire des copies de ma structure, c'est d'utiliser un objet rien que pour encapsuler un pointeur vers ma structure... Pas très beau. Y a-t-il d'autres possibilités ?

Donner un foncteur de comparaison en deuxième argument template de set?

Bonne idée,

je ne me rappellais même pas de son existence...

Je vais tester.

Ca marche bien :
http://cpp.developpez.com/faq/cpp/?p...TL_custom_sort

Merci beaucoup.

Je vois pas l'utilité en fait... C'est un avantage de ne pas avoir à définir d'opérateur de comparaison tu crois pas ?

Après tout, std::set<> est censé représenter un ensemble, où il n'y a pas de notion d'ordre. La relation d'ordre c'est juste pour permettre une implémentation sous forme d'arbre équilibré.

Citation:

---

Après tout, std::set<> est censé représenter un ensemble, où il n'y a pas de notion d'ordre.

---

Pourrais-tu me dire d'où tu tiens ça ? Le std::set est plus qu'un ensemble d'objets uniques, c'est un ensemble d'objets uniques trié.

Moi j'ai :

Citation:

---

Envoyé par cppreference.com

The C++ Set is an associative container that contains a sorted set of unique objects.

---

S'il ne l'avait pas été je ne le l'aurais en fait même pas choisi, vu que j'ai besoin d'avoir mes éléments triés selon leur code alphanum pour ensuite les traiter un par un dans le bon ordre, ce qui devrait répondre à ton interrogation :

Citation:

---

Je vois pas l'utilité en fait...

---

Citation:

---

C'est un avantage de ne pas avoir à définir d'opérateur de comparaison tu crois pas ?

---

C'est clair, mais il est aussi évident que si je ne le fait pas ici, je n'aurai plus le résultat attendu.

Citation:

---

La relation d'ordre c'est juste pour permettre une implémentation sous forme d'arbre équilibré.

---

Je crois que certains algos de la STL utilisent cette propriété pour plus de perfs : set_union/intersection/difference etc.
Dans mon cas elle m'est utile car elle m'évite de faire un std::sort sur un vector ou autre.

à plus.

OK pour l'utilisation.

Sinon je dis pas que la norme ne lui impose pas d'être trié mais que la norme lui imposait d'être trié pour des raisons de performances, parce que sans ça on n'aurait que des complexités linéaires... Juste pour dire que ça s'appelait pas 'set' pour rien ;).

Alors on est d'accord. :P