Ajouter des éléments à un vecteur (mais pas de doublons)

Ajouter des éléments à un vecteur (mais pas de doublons) - C++ - Programmation

Marsh Posté le 28-12-2003 à 22:26:56    

Salut à tous,
 
je voulais savoir si il n'y avait pas plus simple que le code suivant pour ajouter des éléments à un vecteur (std::vector<Possessions> liste_poss; ) sans qu'il n'y ait de doublons:
 

Code :
  1. void Complete_Vecteur(const std::vector<Possessions> & new_poss)
  2. {
  3. std::vector<Possessions> temp;
  4. std::copy(liste_poss.begin(),liste_poss.end(),back_inserter(temp));
  5. std::copy(new_poss.begin(),new_poss.end(),back_inserter(temp));
  6. std::sort(temp.begin(),temp.end());
  7. std::vector<Possessions>::iterator new_end = std::unique(temp.begin(),temp.end());
  8. liste_poss.clear();
  9. std::copy(temp.begin(),new_end,back_inserter(liste_poss));
  10. }


 
Merci d'avance...


Message édité par haazheel le 28-12-2003 à 22:27:15
Reply

Marsh Posté le 28-12-2003 à 22:26:56   

Reply

Marsh Posté le 29-12-2003 à 09:24:31    

peut-être avec std::unique_copy ?
http://www.sgi.com/tech/stl/unique_copy.html


---------------
-( BlackGoddess )-
Reply

Marsh Posté le 29-12-2003 à 12:10:11    

Si ton vecteur n'a aucune propriete particuliere (non trié ou non haché) alors lorsque tu ajoutes un élément tu n'as pas d'autres solutions que de parcourir la liste des éléments un à un pour vérifier qu'il n'est pas présent ce qui peut etre très long mais est intéressant pour un petit nombre d'éléments à stocker.
 
Maintenant tu as des solutions meilleures. Tu peux ajouter tes éléments dans ton vector de maniere a maintenir un ordre particulier, ainsi grace à cet ordre déterminé qu'il n'y a pas de doublon reviendra a faire une recherche dichotomique de cet élément dans le tableau.
De meme si l'emplacement dans ton tableau est determiné par un calcul de hachage, alors il suffit de calculer la valeur de hachage de ton élément et du meme coup l'emplacement qu'il devrait occuper dans le tableau et de vérifier qu'aucun élément n'occupe cet emplacement ou que l'élément qui l'occupe n'est pas égal à celui que tu veux ajouter.
 
Si tu ne veux pas avoir à gerer cela toi meme tu as l'ensemble de la STL std::set qui te garantit que deux elements inseres ne seront pas égaux.
 
Reste à definir l'égalité. En general un set utilise l'égalité par défaut qui n'est pas forcément celle que tu veux (notamment si tu stockes des pointeurs plutot que les objets qui ont été alloués séparément). Tu peux avoir à définir un prédicat qui va définir la notion d'égalité entre deux éléments. (deuxiéme argument du template std::set<key, compare, alloc> ). l'égalité est définie indirectement via le prédicat "compare" qui va définir un ordre absolu entre tous tes éléments.
 
Le deuxième type à base de calcul de hachage n'est pas standard (n'existe pas dans la STL de VC6 par ex) mais est définie dans celle de SGI std::hash_set.
 
LeGreg

Reply

Marsh Posté le 29-12-2003 à 21:08:57    

J'avais complètement oublié le std::set sur ce coup là, et c'est vrai que ça me conviendrait à merveille...
 
Merci du rappel!

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed