C ++はfind（）をinsert（）にマップする可能性があります：操作を最適化する方法は？

StackOverflow https://stackoverflow.com/questions/1409454

  •  05-07-2019
  •  | 
  •  

質問

STLマップデータ構造を使用しており、コードが最初に find（）を呼び出すとき：キーが以前マップになかった場合、 insert（）を呼び出しますそれ以外の場合は何もしません。

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

これよりも良い方法があるかどうか疑問に思っていました。私が知る限り、この場合、まだ存在しないキーを挿入したい場合、マップデータ構造で2つのルックアップを実行します。 find（）の場合、 insert（）の1つ（ operator [] に対応）。

ご意見をお寄せいただきありがとうございます。

役に立ちましたか？

解決

通常、検索を実行し、場合によっては挿入を実行する場合、古い値が既に存在する場合はそれを保持（および取得）します。古い値を単に上書きしたい場合、 map [foo_obj] =＆quot; some value＆quot; がそれを行います。

1回のマップルックアップで、古い値を取得する方法、または存在しない場合は新しい値を挿入する方法は次のとおりです。

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

これは、ヘルパー関数を使用するのに十分な一般的なイディオムです。

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

vの高価な計算が既に存在する場合はスキップしたい場合（メモ化など）、それも一般化できます：

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

例：

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

マップされた型がデフォルトで構築可能でない場合、Fにデフォルト値を提供させるか、get_else_computeに別の引数を追加します。

他のヒント

2つの主なアプローチがあります。 1つ目は、値型を受け取り、挿入が行われたかどうかを示すイテレータとブールを返すinsert関数を使用して、同じキーを持つ既存の要素または新しく挿入された要素のいずれかにイテレータを返すことです。

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

これの利点は、単純であることです。主な欠点は、挿入が必要かどうかに関係なく、常に2番目のパラメーターの新しい値を作成することです。文字列の場合、これはおそらく重要ではありません。構築する価値が高い場合、これは必要以上に無駄になる可能性があります。

これを回避する方法は、挿入の「ヒント」バージョンを使用することです。

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

insertgは、指定された反復子の直後に要素が挿入された場合にのみ、一定時間で償却されることが保証されます。したがって、可能であれば-です。

編集

これが-を必要とする場合は奇妙に思えますが、そうではありません。 map に適用される問題の説明は、重複する問題 246 。

例では、見つからない場合に挿入する必要があります。デフォルトの構築とその後の値の設定に費用がかからない場合は、1つのルックアップでよりシンプルなバージョンをお勧めします。

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn't in map), set value
                                // else existed already, do nothing

実際に必要なものが例に示されている場合は、代わりに str Foo :: s としてその値を追加することを検討してください。そのメンバーの値。そして、 std :: set にオブジェクトを保持します。 class FooWithValue2 を拡張しても、 map を使用するよりも安くなる可能性があります。

しかし、このようなマップを介してデータを結合することが本当に必要な場合、または存在する場合にのみ更新したい場合は、ジョナサンが答えを持っています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top