pour insérer() ou pour faire du nouveau

Question

J'écris du code qui a beaucoup de substitution.

Il ya une liste <char> productions qui a un tas de caractères dedans.

J'ai besoin à plusieurs reprises pour remplacer tous les caractères de productions avec les règles correspondant dans une carte < omble chevalier, char * > productionRules. Ainsi, tous les caractères des productions peuvent être remplacés par zéro ou plusieurs caractères, comme indiqué par productionRules.

Je pense qu'il ya 2 façons de le faire:

1. itérer sur productions et .insert() tous les caractères de remplacement dans productions avant .erase()'ing chaque élément

2. Créer une NOUVEAU liste <char> nouvellesProductions puis réaffecter les productions pour faire référence à nouvellesProductions.

Quel est le meilleur? Pour .insert() et .erase() beaucoup ou juste pour en créer un nouveau?

Answer 1

Cela dépend de la probabilité que chaque caractère soit remplacé par zéro ou> 2 caractères. S'il est peu probable qu'un tel remplacement aura lieu, alors vous gagnerez probablement en itérant. Mais s'il est probable que vous effectuerez souvent cette opération, vous devrez probablement créer une nouvelle liste.

Vous pouvez faire en sorte que votre algorithme tente de parcourir la liste, et si vous trouvez que vous devez effectuer un remplacement de zéro ou> 2, créez une nouvelle liste. Que cela vienne ou non dépend à nouveau de la probabilité que vous soyez confronté à un cas où vous devez faire un tel remplacement.

Answer 2

Créer un est toujours ajouter à la fin qui est plus efficace et moins compliquée à mettre en œuvre.

Answer 3

Je ne vois pas comment faire une copie pourrait être plus rapide. Juste gérer chaque cas de la taille du remplacement.

list<char>::iterator q; 

for (list<char>::iterator p = productions.begin(); p != productions.end(); p = q) 
{ 
    // save the next position since we might be deleting p 
    q = p; 
    ++q; 

    char* p_rule = productionRules[*p]; 

    // if points to empty string, nuke 
    if (!*p_rule) 
     productions.erase(p); 
    else 
    { 
     // if single char, replace 
     *p = *p_rule; 

     // insert all other chars 
     ++p_rule; 
     while (*p_rule) 
     { 
      // check me on this 
      // I want to insert before q 
      productions.insert(q, *p_rule); 
      ++p_rule; 
     } 
    } 
}