Modification d'un conteneur lors de l'utilisation de Visitor

Question

J'ai implémenté le modèle Visitor en C++ à l'aide d'un itérateur de type STL pour stocker la position actuelle du visiteur dans le conteneur. Maintenant, je voudrais changer le conteneur pendant que je le parcourir, et je suis particulièrement intéressé par la suppression d'éléments du conteneur, même celui que je suis en train de visiter.

Maintenant, évidemment, cela invalidera l'itérateur interne des visiteurs, car il indiquait exactement cet élément. Actuellement, je stocke une liste de tous les itérateurs dans le conteneur et les met à jour, dès que quelque chose est ajouté ou supprimé de la liste. Donc, d'une certaine manière, ceci est similaire au modèle Observer appliqué à l'itérateur (en tant qu'Observateur) et à la liste (en tant qu'Observable). Alternativement, j'ai considéré que les méthodes visitor() renvoyaient un indice au Visiteur sur ce qui arrivait à l'item courant et comment procéder à l'itération, mais cela ne semble pas non plus une bonne idée, parce que la visite() la mise en œuvre ne devrait pas vraiment se soucier de trouver l'article suivant. Donc, ma question est la suivante: Quelle est la meilleure façon de garder un visiteur au travail, même lorsque des éléments sont ajoutés ou retirés du conteneur.

Cordialement, Florian

Mise à jour: Il y a un visiteur en cours d'exécution sur le conteneur, mais à l'intérieur de la méthode visite() un certain nombre de itérateurs supplémentaires pourraient être utilisés sur le même récipient. Je souhaite que le visiteur continue avec les éléments restants dans le conteneur, même après le retour d'un appel à visit() dans lequel l'un des éléments du conteneur a été supprimé.

Answer 1

Lors de la mutation du conteneur pendant la traversée, les itérateurs sont dangereux, au mieux. Il est plus sûr d'utiliser un index et de revenir en arrière.

Answer 2

Je pense que votre (première) implémentation est plutôt bonne s'il n'y a pas tellement d'itérateurs et d'opérations de suppression. Si c'était le cas, j'utiliserais une marque et un balayage comme l'algorithme recommandé par Eddy. Aussi, je pense que ce dernier est plus facile et donc moins sujette aux erreurs. N'oubliez pas d'ignorer les nœuds marqués pour suppression. D'autre part, s'il y a des cas autres que 'delete' où vos itérateurs doivent être mis à jour, respectez votre implémentation actuelle.

Answer 3

Dans ces cas, si copier mon conteneur n'est pas cher, je le copie et je le répète sur la copie. Le conteneur d'origine contient des objets par shared_ptr tandis que la copie contient uniquement weak_ptr.