Eliminations de doublons non-consécutifs

Bonjour,

J'ai un :

Code:

---

vector< pair<int, int> > paires;

---

dont je cherche à conserver l'unicité de l'attribut second des pairs.

Mettons que j'ai :

Code:

---

1 2 3 4 5 6

paires.push_back( make_pair(5, 6) ); // paire n°0 paires.push_back( make_pair(0, 5) ); // paire n°1 paires.push_back( make_pair(6, 7) ); // paire n°2 paires.push_back( make_pair(2, 5) ); // paire n°3 paires.push_back( make_pair(1, 5) ); // paire n°4 paires.push_back( make_pair(1, 8) ); // paire n°5

---

je souhaite supprimer 2 des paires n°1, 3 et 4, peu importe lesquelles et n'en conserver donc qu'une seule sur les 3.

Au final, j'ai réussi à le faire :

Code:

---

1 2 3 4 5

sort(paires.begin(), paires.end(), &trie_les_paires);   vector< pair<int, int> >::iterator newIteratorOfEnd = unique(paires.begin(), paires.end(), &supprime_les_doublons);   paires.erase(newIteratorOfEnd, paires.end()) ;

---

Avec les fonctions :

Code:

---

1 2 3 4 5 6 7 8 9

bool trie_les_paires(const pair<int, int> & a, const pair<int, int> & b) { return (a.second < b.second); }   bool supprime_les_doublons(const pair<int, int> & a, const pair<int, int> & b) { return (a.second == b.second); }

---

Je trie mes paires dans l'ordre croissant des attributs "second". Je supprime les copies consécutives qui possèdent le même élément "second". Puis ensuite je supprime les dernières entrées "inutiles".

Y-a-t-il une fonction de la stl spécifique à cette opération ? Ou peut-on faire mieux ?

Je précise que j'ai simplifié le problème : je compare en fait des objets plus complexes ...

Merci.

Flo.

Je ne connais pas franchement mieux. Une alternative parfois intéressante est de changer la structure de tes données (par exemple, ici, tout mettre dans un map<int /*le deuxième...*/, int /*le premier*/ >.

Utilise un hash_map.

http://www.sgi.com/tech/stl/hash_map.html

Quelqu'un peut m'expliquer le newIteratorOfEnd?? C'est la première fois je vois ca.

Effacer un élément d'un conteneur demande de connaître ce conteneur. Avoir juste un itérateur sur l'élément est insuffisant. Or les algorithmes de la STL n'on que des itéreurs comme argument. Comment faire ?

Pour les algorithmes qui enlèvent (unique, mais aussi remove_if), on fonctionne en deux parties : L'algorithme lui même se débrouille que les éléments à garder soient placés au début de la séquence, et retourne un itérateur sur le premier élément qui n'est pas à garder. On appelle ensuite la fonction erase du conteneur pour lui faire enlever les éléments en trop.

Woah pardonner ma lecture fautive, javais cru lire que newIteratorOfEnd() était le type et non le nom de l'itérateur ;).


Ca va #1 la.

Ok,

merci.

Finalement, j'ai fait ma propre fonction qui utilise 2 type de foncteurs pour le tri, un foncteur pour comparer 2 éléments entre eux (cette comparaison pouvant être différente suivant les besoins) et un foncteur pour faire une suppression conditionnelle (là encore dans certains cas la suppression est systématique et dans d'autre cas conditionnelles).

Par ailleurs, je n'ai pas réussi à adapter l'exemple sur les pair<int, int> à mon besoin ... puisque j'ai pas de relation d'ordre croissant ou décroissant pour le sort.

Enfin, c'est dommage qu'une telle fonction n'existe pas pour supprimer des doublons non-consécutifs à partir d'un foncteur.

Peut-être dans la prochaine version du C++ :D

A+

Flo.

Tu peux aussi simplement utiliser un set en fournissant une fonction de comparaison ( qui travaille uniquement sur la partie que tu souhaite ). De cette manière, tu es assuré de ne pas avoir de doublon ( doublon d'apres ta fonction de comparaison ).

Pour Mast3rMind, hash_map ne fait pas partie du standard C++, il me semble. Seul map fait partie du standard.

Il ne me parait pas vraiment envisageable de fournir une telle fonction. Quelle devrat être sa complexité ?
(D'autant que la copie dans un std::set remplit très bien ce rôle.)

Eliminer des doublons d'une liste est tout de même un élément essentiel en tant que phase de post-traitement de cette liste.

L'exemple sur mon 1er post est simpliste et aisément solvable. Cependant, comme je l'ai dit, je n'ai pas de relation d'ordre de croissance ou décroissance dans l'attribut de classe qui me sert d'élimination des doublons.

Je pense définitivement que dans le cas de list, de vector, etc ... l'élimination des doublons non-consécutifs à partir d'un foncteur est indispensable.

Je suis loin d'être un expert en c++ et encore moins de la stl.

Voila le code que j'ai fait pour combler ce manque dans mes besoins :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

typedef bool comparator(vector< TMyObject >::iterator & a, vector< TMyObject >::iterator & b); typedef vector< TMyObject >::iterator eliminator(vector< TMyObject >::iterator & a, vector< TMyObject >::iterator & b);   void SortMyObjects(vector< TMyObject > & list, comparator * ptrSortingFunc, eliminator * ptrEliminatingFunc) { vector< TMyObject >::iterator element1 = list.begin();   while(element1 != list.end()) { vector< TMyObject >::iterator element2 = element1 + 1;   while(element2 != list.end()) { // on a trouvé 1 doublons, on quitte la boucle while if(ptrSortingFunc(element1, element2)) break;   // on passe à l'élément suivant element2++; }   // si on a trouvé un doublon if(element2 != list.end()) { // on efface le doublon en trop et on garde l'élément d'intérêt list.erase( ptrEliminatingFunc(element1, element2) );   // on reboucle en début de liste element1 = list.begin(); continue; }   // on passe à l'élément suivant element1++; } }

---

La fonction cherche les doublons à partir d'une fonction de comparaison d'éléments fournie en argument. Quant au choix de l'élément à supprimer (le 1er ou le 2eme), il dépend d'une 2eme fonction de comparaison entre les 2 éléments trouvés.

Je pense qu'une telle fonction est aisément adaptable à différents conteneurs ... etc, etc, ... , dans le style de la stl.

Cependant, je ne connais pas du tout std::set.

De quelle façon peut-on l'utiliser pour l'élimination de doublons non-consécutifs à partir d'une fonction de comparaison ?

Est-ce que ça peut remplacer plus ou moins le code précédent ?

Merci.

A+

Flo.

Tu dis que tu n'as pas de relation d'ordre, mais ne peux tu en introduire une, même si elle n'est pas naturelle ? Par exemple, les complexes n'ont pas de relation d'ordre courrament admise (naturelle) en math. Mais rien n'empêche de définir quand même une relation d'ordre dessus :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

bool operator< (Complex c1, Complex c2) { if (c1.real() < c2.real()) { return true; } else { return c1.imag() < c2.imag(); } }

---

Avec une telle relation d'ordre, il te suffit de placer les éléments sans un set pour que les doublons soient supprimés. Et ça le ferait probablement plus rapidement que ta solution (O(n²) pour toi, à première vue, et si l'on remplace vector par un conteneur supportant l'effacement en temps constant comme list, O(n^3) tel que je le vois actuellement avec un vector, qui serait remplacé par un algorithme en O(n log(n)) ).

Autrement, pour ton code, il n'est pas très dans l'esprit STL, car il ne marche qu'avec des vecteurs, bien qu'il puisse s'adapter à n'importe quelle séquence. La mode STL pour faire ça serait de faire prendre à ton algorithme des itérateur en argument (en templatisant selon le type d'itérateur).

Oui c'est que j'ai dit :

Citation:

---

Je suis loin d'être un expert en c++ et encore moins de la stl.

---

Citation:

---

Je pense qu'une telle fonction est aisément adaptable à différents conteneurs ... etc, etc, ... , dans le style de la stl.

---

Flo.