38

まず、C ++で[]演算子をunordered_mapと組み合わせてルックアップに使用すると、find（）メソッドの呼び出しがラップされるのか、それとも[]演算子をfind（）よりも速く使用するのかを明確にできますか？

次に、次のコードでは、キーがunordered_mapにまだ含まれていないmap[key] = value場合に、[]演算子を使用して作成されたデフォルト値を置き換えるために、行を介して2回目のルックアップを実行していると思われます。キーがありません。

それは本当です。もしそうなら、（おそらくポインタなどを使用して）どのような場合でも（おそらく値を配置する場所のアドレスを格納する/値を読み取ることによって）1回のルックアップのみを実行する方法があります。それでも同じ機能を実現しますか？もしそうなら、明らかにこれは有用な効率改善になるでしょう。

変更されたコードの抜粋は次のとおりです。

    int stored_val = map[key]; // first look up. Does this wrap ->find()??

    // return the corresponding value if we find the key in the map - ie != 0
    if (stored_val) return stored_val;

    // if not in map
    map[key] = value; 
       /* second (unnecessary?) look up here to find position for newly 
          added key entry */

   return value;
4

3 に答える 3

48

operator[]まだ存在しない場合は、デフォルトで作成された値を使用してエントリを挿入します。これは同等ですが、おそらく次のよりも効率的に実装されます。

iterator iter = map.find(key);

if(iter == map.end())
{
    iter = map.insert(value_type(key, int())).first;
}

return *iter;

operator[]キーを再ハッシュする手間を省くことができるため、とをfind()使用して手動で作業を行うよりも高速になります。insert()

コードで複数のルックアップを回避する1つの方法は、値への参照を取得することです。

int &stored_val = map[key];

// return the corresponding value if we find the key in the map - ie != 0
if (stored_val) return stored_val;

// if not in map
stored_val = value;

return value;

値がマップに存在しない場合は、operator[]デフォルトで作成して挿入することに注意してください。したがって、これにより複数のルックアップを回避できますが、コピーまたは移動-構成よりもデフォルト-構成+割り当ての方が遅いタイプで使用すると、実際には遅くなる可能性があります。

ただし、これintは安価にデフォルトで0に構成されますが、0を空を意味するマジックナンバーとして扱うことができる場合があります。これは、あなたの例の場合のように見えます。

そのようなマジックナンバーがない場合は、2つの選択肢があります。何を使用するかは、値を計算するのにどれだけの費用がかかるかによって異なります。

まず、キーのハッシュが安価であるが、値の計算が高価でfind()ある場合は、最良のオプションである可能性があります。これは2回ハッシュしますが、必要な場合にのみ値を計算します。

iterator iter = map.find(key);

// return the corresponding value if we find the key in the map
if(iter != map.end()) return *iter;

// if not in map
map.insert(value_type(key, value));

return value;

ただし、すでに値を取得している場合は、非常に効率的に実行できます。おそらく、上記のように参照+マジックナンバーを使用するよりもわずかに効率的です。

pair<iterator,bool> iter = map.insert(value_type(key, value));
return *iter.first;

によって返されたboolmap.insert(value_type)がtrueの場合、アイテムが挿入されました。それ以外の場合、それはすでに存在し、変更は行われませんでした。イテレータは、マップに挿入された値または既存の値を指すポイントを返しました。簡単な例では、これが最良のオプションかもしれません。

于 2011-08-01T11:38:21.407 に答える
10

要素が存在するかどうかを確認し、存在しない場合は新しい要素を挿入することができます。この関数は、値が実際に挿入されたかどうかをブール値で通知するinsertを返します。pair<iterator, bool>たとえば、ここのコード：

  unordered_map<char, int> mymap;
  pair<unordered_map<char,int>::iterator,bool> ret;

  // first insert function version (single parameter):;
  mymap.insert ( pair<char,int>('z',200) );
  ret=mymap.insert (pair<char,int>('z',500) ); 
  if (ret.second==false)
  {
    cout << "element 'z' already existed";
    cout << " with a value of " << ret.first->second << endl;
  }

ここのコードは、ペア<'z',200>が存在しない場合はマップに挿入します。返されたペアの2番目の要素の値がtrueの場合は挿入されたイテレータを返し、ペアの2番目の要素がfalseの場合は要素が実際にあった場所のイテレータを返します。

于 2011-08-01T11:40:07.643 に答える
2

まず、C ++でルックアップにunordered_mapと組み合わせて[]演算子を使用すると、Find（）メソッドの呼び出しがラップされるのか、それとも[]演算子をFind（）よりも速く使用するのかを明確にできますか？

そのための規則はありません。の実装では、[]を使用するか、それ自体でルックアップを実行するか、内部find()で使用されるプライベートメソッドにルックアップを委任することができます。find()

また、どちらが速いかについての保証もありません。 find()イテレータの構築と返却にはオーバーヘッドが伴います[]が、キーが存在しない場合は、この場合は新しい値が挿入されるため、おそらく遅くなります。

（...）どのような場合でも1回のルックアップのみを実行する方法があります（おそらくポインターなどを使用して）（...）

キーがマップにない場合は、[]デフォルトで作成された新しい値を挿入し、参照を返します。したがって、その参照を保存して2番目のルックアップを保存できます。

int& stored_val = map[key];  // Note the reference

if (stored_val) return stored_val;

// Use the reference to save a second lookup.
stored_val = value; 

return value;
于 2011-08-01T11:39:15.300 に答える