Discussion :

[thomas41]

Bonjour à tous!

Je rencontre des problèmes en manipulant des conteneurs avec des itérateurs.

J'utilise un conteneur de type deque stockant des objets. Lorsque je supprime un élément du conteneur, les itérateurs pointant vers des objets de ce même conteneur ne sont plus valide: ils pointent vers l'objet suivant dans celui-ci.

Les itérateurs conservent-ils une position fixe par rapport au début du conteneur?

Voici un peu de code pour décrire mon problème:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
class UnObjet
{
public:
    int valeur;
};
 
deque<UnObjet> monConteneur;

J'ai donc un ensemble d'objets stockés, puis je déclare deux itérateurs.
Le premier pointe vers le 7eme objet avec une valeur de 1112, le second pointe vers le 37eme objet du conteneur ayant une valeur égale à 1244.
En résumé:

monConteneur[6] = 1112;
monConteneur[7] = 1116;
...
monConteneur[37] = 1244;
monConteneur[38] = 1248;

On a alors:
it6->valeur: 1112 et
it37->valeur: 1244

Je souhaite maintenant supprimer le 37eme élément. Je déplace donc le 37eme élément à la fin puis je le supprime. Le problème apparait lors du remove:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
struct predicate  
{  
	predicate(UnObjet val): val_(val) {}  
	bool operator()(UnObjet i) { return i == val_; }  // == opérateur surchargé, compare les deux 'valeur'.
private:  
	UnObjet val_;  
};
 
remove_if(monConteneur.begin(), monConteneur.end(), predicate(*it6) );

La valeur 1112 (anciennement 6eme position) se retrouve bien à la fin du conteneur, mais l'itérateur it36 ne pointe plus vers 1244 mais vers 1248, qui est la valeur de l'objet suivant.

J'imagine qu'il s'agit d'un fonctionnement normal, mais j'aurais aimé l'avis d'un expert pour m'aider à supprimer facilement un objet de mon conteneur sans toucher aux autres références.

Merci par avance pour toute aide apportée.

[Invité]

Lorsque l'on supprime ou deplace les objets d'un conteneur standard (il y a des exceptions mais je ne me souviens plus lesquelles) toutes les références et les iterateurs sont invalidés.

D'autre part remove_if ne supprime rien : il ne fait que déplacer vers la fin du conteneur les éléments à 'supprimer' puis renvoie un iterateur vers le premier élément à 'supprimer' :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
deque<UnObjet>::iterator newEnd = remove_if(monConteneur.begin(), monConteneur.end(), predicate(*it6) );
monConteneur.erase(newEnd, monConteneur.end());

[thomas41]

Merci de t'être penché sur mon problème.

J'utilise en fait l'Idioms Erase/remove. J'ai été un peu vague dans mes explication car mon problème survient lors de l'utilisation de remove_if.

Les itérateurs sont effectivement invalidés: les itérateurs référençant les objets contenant une valeur supérieure à celle déplacée par remove_if pointent maintenant vers l'objet suivant dans le conteneur.

Je pourrais les décrémenter:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
if (it37->valeur > it6->valeur)
  it37--;
 
// suivi de erase(remove_if...it6...)

pour les rétablir, mais je ne pense pas que ce soit la solution.

Pour le moment, mon code s'adapte à cette contrainte et fonctionne très bien, mais j'aurais aimé pourvoir initialiser mes itérateurs au départ sans avoir à les redéfinir pas la suite.

Je recherche donc un moyen de supprimer une référence dans mon conteneur sans invalider les autres références, ou tout simplement un conteneur plus simple à utiliser avec les itérateurs.

Des suggestions?

[r0d]

Ben en fait, le problème c'est qu'une deque (acronyme pour double-ended queue) est un conteneur qui n'est pas pensé ni implémenté pour insérer/supprimer des éléments au milieu.

Pourquoi une simple list ne te convient pas?

Sinon, ce diagramme pourrait aider.

[thomas41]

Merci. Le schéma résume bien les spécificités de chaque conteneurs.

"list" résout en effet ce problème d'invalidation, mais ne me convient pas non plus, car on ne peut accéder directement à un élément par son indice. Il faut automatiquement passer par les itérateurs.

Supprimer un élément d'une "deque" invalide les itérateurs de la partie supérieur, mais conserve leur ordre. D'autre part, les éléments sont accessibles directement par leur position. Cela m'était utile par exemple pour rechercher un élément par dichotomie dans un conteneur d'une grande taille trié selon une variable par ordre croissant.

Ce que je recherche, si cela existe, c'est un conteneur qui n'invalide pas les itérateurs et dont l'accès peut se faire par indice (= monConteneur[10]).

[poukill]

Implémente l'équivalent de l'opérateur [] toi même.
-> std::advance

[jblecanard]

Ce que tu cherches en fait, c'est le conteneur parfait qui n'a pas besoin de compromis .

L'idée d'implémenter soi même [] est bonne, surtout qu'il y a moyen de l'optimiser facilement pour que le parcours par boucle ne pourrisse pas trop tes perfos. Mais ça les pourrira un peu quand même

[thomas41]

Effectivement, c'est ce que je recherche :p.

J'avais implémenté l'opérateur[], mais pour une recherche par dico sur 1000 objets par exemple, on parcourt de nombreuses fois les mêmes objets avec "advance" et je me suis demandé si du coup, on ne perdait pas l'avantage d'utiliser cette fonction de recherche.

En tout cas, merci pour vos réponses.