を挿入（）または新規作成する

Question

私は大量のコードを書いています。

リスト<チャイルド>のプロダクションがあり、その中には一連の文字が含まれています。

私は繰り返しマップ<のchar、char型でそれに対応するルールを持つ制作 * > productionRulesのすべての文字を交換する必要があります。したがって、プロダクションの各文字は、productionRulesで示されるように、0文字以上に置き換えられます。

私はそれを行うには2通りの方法があります考えている：

1. 反復以上の制作と.insert（）制作中のすべての置換文字が.erase()'ing前各要素

2. を作成します。 NEW リスト<char> newProductionsnewProductionsを参照するようにプロダクションを再割り当てします。。

どちらが良いですか？ .insert（）と.erase（）をたくさん使ったり、新しいものを作成したりするには？

Answer 1

各文字がゼロまたは2文字以上で置き換えられる可能性があります。そのような置換が起こる可能性が低い場合、おそらくそれを反復することで勝つでしょう。しかし、あなたがその操作をしばしば実行する可能性が高い場合は、ほぼ確実に新しいリストを作成する必要があります。

アルゴリズムがリストを反復しようとする可能性があります。ゼロまたは2を置き換えなければならない場合は、新しいリストを作成してください。これが成功するかどうかは、あなたがそのような置き換えを行う必要があるケースに遭遇する可能性に依存します。

Answer 2

作成には、常に効率的で実装が簡単でない方が最後に追加されます。

Answer 3

コピーを作成する方が高速になる可能性はありますか？交換のサイズの各ケースを処理するだけです。

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; 
     } 
    } 
}