C++

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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [Résolu] Problème lors du tri d'un vecteur d'itérateurs

Arry

Bonsoir,

Voilà je planche depuis quelques temps sur ce problème

Voici mes définitions de classes :

Code :

class indice {
int cf;
[...]
};
struct SortByCf
{
bool operator ()(const vector<indice>::iterator& a1, const vector<indice>::iterator& a2) const
{
return a1->cf > a2->cf;
}
};

Et voici le bout de code posant problème :

Code :

vector<indice> l_indices;
vector<indice>::iterator it = l_indices.begin();
vector<vector<indice>::iterator> l_iIndices;
[...] // On remplit l_indices ici, tout se passe bien
for (; it != l_indices.end(); it++) l_iIndices.push_back(it);
// On tri le vecteur d'itérateurs
std::sort(l_iIndices.begin(), l_iIndices.end(), SortByCf());
// Maintenant on veut effacer l_indices en ne gardant que les deux plus grand "cf"
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 :

void SortIterByCf(vector<vector<indice>::iterator>& l_iIndices) {
bool done = false;
while ( !done ) {
unsigned int nbChanges = 0;
vector<vector<indice>::iterator>::iterator iMit = l_iIndices.begin();
while ( (iMit+1) != l_iIndices.end() ) {
if ( (*iMit)->cf < (*(iMit+1))->cf ) {
vector<indice>::iterator temp;
temp = *(iMit+1);
*(iMit+1) = *iMit;
*iMit = temp;
nbChanges++;
}
iMit++;
}
if ( nbChanges > 0 ) done = true;
}
}

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

Publicité

Un Programmeur

Code :

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

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

Arry

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

Tarabiscote

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

Arry

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

Arry

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

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

Tarabiscote

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

Arry

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

FORUM HardWare.fr

Programmation

C++

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

Sujets relatifs
[Résolu][Perl][PostgreSQL] Problème d'installation DBI	Problème de UnsatisfiedLinkError avec une DLL
Probleme avec formulaire de contact	[PHP/XML] Problème pour trouver le code PHP à partir du code VBS
[VBA Excel 2007] erreur Nombre d'arguments incorrects [RESOLU]	[XML/php/Mysql] Caractere chinois
Problème du connexion à BD Mysql dans un programme C	Problème Template matching matlab
Plus de sujets relatifs à : [Résolu] Problème lors du tri d'un vecteur d'itérateurs

Page générée en 0.060 secondes