[Résolu] Problème lors du tri d'un vecteur d'itérateurs

Problème lors du tri d'un vecteur d'itérateurs [Résolu] - C++ - Programmation

Marsh Posté le 15-07-2009 à 18:13:44    

Bonsoir,
 
Voilà je planche depuis quelques temps sur ce problème
 
Voici mes définitions de classes :

Code :
  1. class indice {
  2.     int cf;
  3.     [...]
  4. };
  6. struct SortByCf
  7. {
  8.    bool operator ()(const vector<indice>::iterator& a1, const vector<indice>::iterator& a2) const
  9.    {
  10.       return a1->cf > a2->cf;
  11.    }
  12. };


Et voici le bout de code posant problème :

Code :
  1. vector<indice> l_indices;
  2. vector<indice>::iterator it = l_indices.begin();
  3. vector<vector<indice>::iterator> l_iIndices;
  5. [...] // On remplit l_indices ici, tout se passe bien
  7. for (; it != l_indices.end(); it++) l_iIndices.push_back(it);
  9. // On tri le vecteur d'itérateurs
  10. std::sort(l_iIndices.begin(), l_iIndices.end(), SortByCf());
  12. // Maintenant on veut effacer l_indices en ne gardant que les deux plus grand "cf"
  13. for ( vector<vector<indice>::iterator>::iterator iMit = l_iIndices.begin() + 2; iMit != l_iIndices.end(); iMit ++ ) l_indices.erase(*iMit);


Au final j'ai une erreur mémoire.
En plaçant un point d'arrêt avant la dernière boucle for je me suis rendu compte que le vecteur l_iIndices est vide.
Après vérification, le vecteur l_iIndices est remplit convenablement avant le sort.
 
J'ai donc pensé à écrire une fonction sort simple moi même, même erreur...
Pour info voici son code :

Code :
  1. void SortIterByCf(vector<vector<indice>::iterator>& l_iIndices) {
  2. bool done = false;
  3. while ( !done ) {
  4.  unsigned int nbChanges = 0;
  5.  vector<vector<indice>::iterator>::iterator iMit = l_iIndices.begin();
  6.  while ( (iMit+1) != l_iIndices.end() ) {
  7.   if ( (*iMit)->cf < (*(iMit+1))->cf ) {
  8.    vector<indice>::iterator temp;
  9.    temp = *(iMit+1);
  10.    *(iMit+1) = *iMit;
  11.    *iMit = temp;
  12.    nbChanges++;
  13.   }
  14.   iMit++;
  15.  }
  16.  if ( nbChanges > 0 ) done = true;
  17. }
  18. }


 
J'espère avoir été assez clair, n'hésitez pas à me poser des questions.
Merci de m'avoir lu !


Message édité par Arry le 17-07-2009 à 15:22:46

---------------
Mon Feed-Back
Reply

Marsh Posté le 15-07-2009 à 18:13:44   

Reply

Marsh Posté le 15-07-2009 à 18:41:48    

Code :
  1. assert(l_indices.size() >= 2);
  2. l_indice.erase(l_indices.begin() + 2; l_iIndices.end());


---------------
The truth is rarely pure and never simple (Oscar Wilde)
Reply

Marsh Posté le 15-07-2009 à 20:53:36    

Merci pour ta réponse rapide :jap:
J'essaye ça dès que j'arrive au travail demain matin.

 

Par contre je ne comprends pas l'utilisation de "l_indices.begin() + 2" comme premier paramètre du erase.
En effet, il me semble que ceci aura pour effet d'effacer le vecteur du deuxième au dernier indice, sans se soucier du tri précédemment effectué sur le vecteur d'itérateurs.
Si c'est une faute de frappe par contre, il me semble que cela revient au même que ce que j'ai écrit plus haut...


Message édité par Arry le 15-07-2009 à 20:54:02

---------------
Mon Feed-Back
Reply

Marsh Posté le 15-07-2009 à 22:48:17    

Le problème c'est que lorsque tu fais

l_indices.erase(*iMit);


L'ensemble des itérateurs de ce vecteur sont invalidés donc l'erase suivant ne peut plus fonctionner.
D'où la réponse (erroné) de "Un programmeur" qui n'a pas remarqué la présence du 2e vecteur.
 
Sinon pourquoi ne pas trier directement sur le 1er vecteur et supprimer les éléments suivants ?
Ou alors au moins copier ces deux éléments dans un autre vecteur (pour ne pas invalider les itérateur).
 
PS : On fait généralement "++it" car sinon une copie temporaire inutile de l'itérateur est créée.


Message édité par Tarabiscote le 15-07-2009 à 22:52:16
Reply

Marsh Posté le 16-07-2009 à 09:08:53    

Impossible de trier directement le premier vecteur, car je ne dois trier qu'une partie de celui-ci ( il est vrai que le code fourni n'explicite pas ce point )
Quant à la copie, je voulais l'éviter car ce code doit être rapide ( très ) et le vecteur à trier est assez lourd

 

Merci pour ton indication sur l'incrémentation des itérateurs, je ne savais pas :jap:

Message cité 1 fois
Message édité par Arry le 16-07-2009 à 09:12:53

---------------
Mon Feed-Back
Reply

Marsh Posté le 16-07-2009 à 10:29:47    

Ne trouvant pas de solution, je me suis résigné à copier les éléments à trier dans un vecteur temporaire


---------------
Mon Feed-Back
Reply

Marsh Posté le 17-07-2009 à 13:39:46    

Arry a écrit :

Quant à la copie, je voulais l'éviter car ce code doit être rapide ( très ) et le vecteur à trier est assez lourd


 
Je voulais juste préciser que la suppression d'un élément d'un vecteur est très longue (copie de l'ensemble des éléments suivants l'élément à supprimer) donc je pense que 2 copies ce sera toujours plus rapide que de faire n-2 suppressions (* n/2 copies environ) ...
 
Si ça fonctionne, il ne te reste plus qu'à marquer ce sujet comme étant résolu.
 
PS : Sinon si tu n'as besoin que des 2 plus grands, pour aller plus vite, tu aurrais pu faire un parcourt de ton vecteur en vérifiant pour chaque élément si c'est un des deux plus grands au lieu de trier un vecteur.


Message édité par Tarabiscote le 17-07-2009 à 13:44:56
Reply

Marsh Posté le 17-07-2009 à 15:22:16    

Au final je me suis rabattu sur la solution de copie qui est en fait acceptable niveau performances (-1ms)
 
Merci pour les précisions quant à l'effacement d'un vecteur, j'en prend bonne note :jap:


---------------
Mon Feed-Back
Reply

Sujets relatifs:

Leave a Replay

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