Comment insérer dans un vecteur imbriqué sans invalider l'itérateur (s)

Question

J'ai quelques expressions booléennes à évaluer et à traiter. Peut-être que tout cela aurait été mieux avec Boost, mais j'apprends encore le STL et je ne suis pas allé comme ça. J'apprends maintenant sur la validation d'itérateur, ou l'INvalidation selon le cas. Y at-il un moyen d'insérer un nouvel élément dans ce vecteur imbriqué ci-dessous en toute sécurité? Si vous ne voulez pas voir un homme pleurer, ne pas suggérer que je réécris tout :) En toute sincérité, je serais également heureux de suggestions pour la façon de réécrire cela d'une manière plus élégante après Je fixe mon plus immédiat problème, qui je soupçonne est un itérateur invalidé ...

... Je ne suis pas terriblement préoccupé par la performance. Basé sur cela et en lisant à travers d'autres messages, peut-être un std::List à la place de std::vector serait mieux, mais aurais-je besoin de cela à tous les niveaux de l'imbrication?

----nested.h

#include <vector> 

struct Term { 
    uint32_t termNumber; 
    std::string content; 
    uint32_t importance; 
    uint32_t numAppearances; 
    uint32_t ContextFlags; 
}; 

struct SubClause { 
    std::string typeName; 
    std::vector<Term> terms; 
    std::string clauseExpression; 
}; 

struct Clause { 
    std::vector<SubClause> subClauses; 
}; 

-----nested.cpp

#include <iostream> 
#include "nested_container.h" 

int main (int argc, char * const argv[]) { 
    std::vector<Clause> expression; 

    std::vector<Clause>::iterator clauseIter = expression.begin(); 
    std::vector<Clause>::iterator clauseEnd = expression.end(); 
    for(; clauseIter != clauseEnd ; clauseIter++) 
    { 
     std::vector<SubClause>::iterator subIter = clauseIter->subClauses.begin(); 
     std::vector<SubClause>::iterator subEnd = clauseIter->subClauses.end(); 
     for(; subIter != subEnd ; subIter++) 
     { 
      std::vector<Term>::iterator termIter = subIter->terms.begin(); 
      std::vector<Term>::iterator termEnd = subIter->terms.end(); 

      for(; termIter != termEnd ; termIter++) 
      { 

       /* Evaluate SubClause Terms based on some criteria 
       */ 
       /* if criteria true */ 
       if(true/* criteria true? */) 
       { 
        Term newTerm = { }; 
        /* fillOutTerm(newTerm) */ 
        /* Invalidates the subIter pointer, pretty sure. Anything else???? */ 
        subIter->terms.push_back(newTerm); //BAD? 
       } 
      } 

     } 
    } 

    return 0; 
} 

Answer 1

Il y a trois choses qui invalident vecteur itérateurs:

• détruire le vecteur: P
• push_back provoquant une réallocation (inv alidates tous les itérateurs)
  • invalident fin() même sans une nouvelle répartition
• insert ou effacer
  • seulement invalide itérateurs après que les articles concernés, à l'exception d'un insert qui provoque une redistribution, ce qui annule tous les iterator

d'autres opérations qui sont définies en termes de ceux-ci, tels que assign (effacer + insérer) ou effacer (effacer), se comportent de la même manière.

Réallocation de vecteur lorsque size() doit dépasser capacity(), vous pouvez appeler reserve() pour vous assurer que capacity() a une certaine valeur.

Parce que vous ajoutez dans votre boucle interne, il faut regarder plus comme:

std::vector<Term>::iterator termIter = subIter->terms.begin(); 
for (; termIter != terms.end(); ++termIter) { 
    if (true/* criteria true? */) { 
    Term newTerm = { }; 
    std::vector<Term>::size_type cur_pos = termIter - subIter->terms.begin(); 
    subIter->terms.push_back(newTerm); 
    termIter = subIter->terms.begin() + cur_pos; 
    } 
} 

Il utilise une propriété de itérateurs d'accès aléatoire pour enregistrer la position et la restaurer, pour termIter, que vecteur avait réallouer pour push_back. Et puisque l'itérateur final est toujours obtenu à partir du vecteur, il est toujours valide.

Même si tout ne s'applique pas au site stdlib, SGI a un good reference sur la STL (ce n'est pas la même chose que le stdlib, ou les modèles dans stdlib) et les concepts qu'il utilise.

Answer 2

Une option consiste à créer une copie du vecteur intérieur, effectuer toutes les mises à jour à ce sujet, puis échanger la copie.

A la fin de la journée, il est juste de structurer votre code afin que vous ne N'utilisez pas d'itérateurs après que le conteneur (vecteur dans ce cas) a été modifié.

Answer 3

Lorsque vous push_back dans un vecteur, vous (potentiellement) itérateurs dans invalidez que vecteur, mais si ce vecteur se trouve être l'un des éléments dans un autre vecteur, itérateurs dans cet autre vecteur ne sont pas affectés.

D'autre part, dans ce cas, les indices semblent (au moins pour moi) pour produire du code qui est considérablement plus court, plus simple et plus propre que itérateurs:

for (i=0; i<clause.size(); i++) { 
    std::vector<term> &terms = clause[i].terms; 
    for (j=0; j<terms.size(); j++) 
     if (criteria) 
      terms.push_back(term(x, y, z)); 
} 

Dans les circonstances, l'utilisation d'itérateurs me frappe comme une perte nette. Avec suffisamment de soin, ils vous laisseraient stocker les données dans une liste std :: list (par exemple), mais cela ne semble pas (dans ce cas) compenser la longueur supplémentaire et la difficulté de lecture. Les itérateurs sont très utiles pour les algorithmes généraux qui peuvent raisonnablement s'appliquer à une grande variété de conteneurs, mais sinon, ils accomplissent souvent peu ou rien.

En tant que mineur à part, vector::size()peut (au moins théoriquement) ont la complexité linéaire, donc pour le code réel, vous pouvez soulever les appels à la taille() sur des boucles respectives.

Answer 4

Je pense que vous prenez trop loin l'infirmation:

/* fillOutTerm(newTerm) */ 
/* Invalidates the subIter pointer, pretty sure. Anything else???? */ 
subIter->terms.push_back(newTerm); //BAD? 

Dans ce push_back() seulement itérateurs qui sont liés trop subIter-> termes sont addected. (ie subIter) n'est pas affecté car vous ne changez pas le vecteur dont subIter est membre. En regardant votre code, cela peut invalider 'termIter' et 'termEnd'.