La fonction end() doit-elle être constante dans une carte/un ensemble STL ?

Question

Le §23.1.2.8 de la norme stipule que les opérations d'insertion/suppression sur un ensemble/map n'invalideront pas les itérateurs vers ces objets (sauf les itérateurs pointant vers un élément supprimé).

Considérons maintenant la situation suivante : vous voulez mettre en œuvre un graphe avec des nœuds à numérotation unique, où chaque nœud a un nombre fixe (disons 4) de voisins. En tirant parti de la règle ci-dessus, vous procédez comme suit :

class Node {
    private:
        // iterators to neighboring nodes
        std::map<int, Node>::iterator neighbors[4];
        friend class Graph;
};

class Graph {
    private:
        std::map<int, Node> nodes;
};

( EDIT : Pas littéralement comme cela en raison de l'incomplétude des Node à la ligne 4 (voir réponses/commentaires), mais dans ce sens quand même)

C'est une bonne chose, car de cette façon, vous pouvez insérer et supprimer des nœuds sans invalider la cohérence de la structure (en supposant que vous gardez la trace des suppressions et que vous supprimez l'itérateur supprimé du tableau de chaque nœud).

Mais supposons que vous souhaitiez également être en mesure de stocker une valeur de voisin "invalide" ou "inexistante". Pas d'inquiétude, nous pouvons simplement utiliser nodes.end() ... ou le pouvons-nous ? Y a-t-il une sorte de garantie que nodes.end() à 8 heures du matin sera le même que nodes.end() à 22 heures après un million d'insertions/d'effacements ? C'est-à-dire, est-ce que je peux en toute sécurité == compare un itérateur reçu en tant que paramètre de la fonction nodes.end() dans une méthode de Graph ?

Et si non, est-ce que ça marcherait ?

class Graph {
    private:
        std::map<int, Node> nodes;
        std::map<int, Node>::iterator _INVALID;
    public:
        Graph() { _INVALID = nodes.end(); }
};

C'est-à-dire, est-ce que je peux stocker nodes.end() dans une variable lors de la construction, et ensuite utiliser cette variable chaque fois que je veux mettre un voisin dans un état invalide, ou le comparer à un paramètre dans une méthode ? Ou est-il possible qu'à un moment donné, un itérateur valide pointant vers un objet existant compare égal à _INVALID ?

Et si ça ne marche pas non plus, que peut Je fais en sorte de laisser de la place pour une valeur voisine invalide ?

Answer 1

Vous écrivez (c'est moi qui souligne) :

Le §23.1.2.8 de la norme stipule que les opérations d'insertion/suppression sur un ensemble/map n'invalideront pas les itérateurs. à ces objets (sauf les itérateurs pointant sur un élément supprimé).

En fait, le texte de 23.1.2/8 est un peu différent (encore une fois, c'est moi qui souligne) :

Les membres d'insertion n'affectent pas la validité des itérateurs et des références. au conteneur et les membres d'effacement ne doivent invalider que les itérateurs et les références aux éléments effacés.

J'ai lu ça comme : Si vous avez une carte, et que vous obtenez d'une manière ou d'une autre un itérateur dans cette carte (encore une fois, cela ne dit pas à un objet dans la carte), cet itérateur restera valide malgré l'insertion et la suppression d'éléments. En supposant que std::map<K,V>::end() obtient un "itérateur dans la carte", il ne devrait pas être invalidé par l'insertion/le retrait.

Cela laisse bien sûr la question de savoir si "non invalidé" signifie qu'il aura toujours la même valeur. Mon hypothèse personnelle est que cela n'est pas spécifié. Cependant, pour que la phrase "non invalidé" ait un sens, tous les résultats de la fonction std::map<K,V>::end() pour une même carte doivent toujours se comparer de manière égale, même en cas d'insertions/suppressions :

my_map_t::iterator old_end = my_map.end();
// wildly change my_map
assert( old_end == my_map.end() ); 

Mon interprétation est que, si old_end reste "valide" tout au long des modifications apportées à la carte (comme le promet la norme), alors cette assertion devrait passer.

Avis de non-responsabilité : Je ne suis pas un locuteur natif et j'ai un très J'ai du mal à digérer le redoutable legaleze du Saint PDF. En fait, en général, je l'évite comme la peste.

Oh, et ma première pensée a aussi été : La question est intéressante d'un point de vue académique, mais pourquoi ne stocke-t-il pas simplement des clés au lieu d'itérateurs ?

Answer 2

23.1/7 dit que end() retourne un itérateur qui

est la valeur de fin de vie du conteneur.

Premièrement, cela confirme que ce end() retourne l'itérateur. Deuxièmement, il est dit que l'itérateur ne pointe pas vers un élément particulier. Puisque la suppression ne peut invalider que les itérateurs qui pointent quelque part (vers l'élément supprimé), les suppressions ne peuvent pas invalider les éléments suivants end() .

Answer 3

Rien n'empêche une mise en œuvre particulière de la collection d'avoir end() dépendent de l'instance de collecte et de l'heure de la journée, pour autant que les comparaisons et autres fonctionnent. Ce qui signifie, que, peut-être, _end() peut changer, mais old_end == end() la comparaison devrait toujours donner un résultat vrai_ . (edit : bien qu'après avoir lu le commentaire de j_random_hacker, je doute que ce paragraphe lui-même évalue à vrai ;-), pas universellement - voir la discussion ci-dessous ;)

Je doute également que vous puissiez utiliser std::map<int,Node>::iterator dans le Node en raison du fait que le type est incomplet, encore (pas sûr, cependant).

De plus, puisque vos nœuds sont numérotés de façon unique, vous pouvez utiliser int pour les clouer et réserver une certaine valeur pour les invalides.

Answer 4

En supposant que (1) la carte est implémentée avec l'arbre rouge-noir (2) vous utilisez la même instance "après un zillion d'insertions/délétions"- réponse "Oui".

Implantation relative Je peux dire que toutes les incarnations de stl que je connais utilisent l'algorithme de l'arbre.

Answer 5

Quelques points :

1) end() fait référence à un élément qui a dépassé la fin du conteneur. Elle ne change pas lorsque des insertions ou des suppressions modifient le conteneur, car elle ne pointe pas vers un élément.

2) Je pense que votre idée de stocker un tableau de 4 itérateurs dans le Node pourrait être modifiée pour rendre l'ensemble du problème plus logique. Ce que vous voulez, c'est ajouter un nouveau type d'itérateur à l'objet Graph, capable d'itérer sur les voisins d'un seul nœud. L'implémentation de cet itérateur devra accéder aux membres de la carte, ce qui pourrait vous amener à faire en sorte que la classe Graph étende la collection de cartes. Si la classe Graph est une extension de std::map, le langage change et il n'est plus nécessaire de stocker un itérateur invalide, mais simplement d'écrire l'algorithme permettant de déterminer qui est le "prochain voisin" dans la carte.