4

があり、ハッシュされstd::unordered_mapたの最初の値をインクリメントすることと、への参照を作成することの両方が必要です。例えば：std::pairkeykey

std::unordered_map<int, std::pair<int, int> > hash;
hash[key].first++;

auto it(hash.find(key));
int& my_ref(it->first);

[]演算子を使用する代わりに、を使用してデータを挿入するinsert()こともできますが、後で割り当てを解除する場合でも、hashすでにあるようにペアを割り当てkeyます。ただし、確かではありません。明確にする：

// If "key" is already inserted, the pair(s) will be allocated
// and then deallocated, right?
auto it(hash.insert(std::make_pair(key, std::make_pair(0, 0))));
it->second.first++;

// Here I can have my reference, with extra memory operations,
// but without an extra search in `hash`
int& my_ref(it->first);

私は最初のオプションを使用する傾向がありますが、どちらが最適かを判断できないようです。これに対するより良い解決策はありますか？

PS：私にとって理想的な解決策は、最初の、おそらく役に立たない値の割り当てを必要としない挿入のようなものです。

4

3 に答える 3

4

他の人が指摘しているように、aの「割り当て」std::pair<int,int>は、実際には（スタック上の）2つの整数をコピーすることに他なりません。の場合map<int,pair<int,int>>::value_type、つまりpair<int const, pair<int, int>>3int秒であるため、2番目のアプローチを使用しても大きなオーバーヘッドはありません。ieemplaceの代わりにを使用してわずかに最適化できます。insert

// Here an `int` and a struct containing two `int`s are passed as arguments (by value)
auto it(hash.emplace(key, std::make_pair(0, 0)).first);
it->second.first++;

// You get your reference, without an extra search in `hash`
// Not sure what "extra memory operations" you worry about
int const& my_ref(it->first);

両方を使用する最初のアプローチはhash[key]、hash.find(key)要素検索がイテレータの間接参照よりも確かに高価になるため、より高価になるはずです。

すべての引数がsである場合、の構築に向かう途中の引数の時期尚早なコピーはunordered_map<...>::value_type無視できる問題intです。ただし、代わりに、としてヘビーウェイトkey_typeまたはpairヘビーウェイトタイプがmapped_typeある場合は、上記の次のバリアントを使用して、参照によってすべてを可能な限り転送できます（そして、右辺値に移動セマンティクスを使用します）。

// Here key and arguments to construct mapped_type 
// are forwarded as tuples of universal references
// There is no copying of key or value nor construction of a pair 
// unless a new map element is needed.
auto it(hash.emplace(std::piecewise_construct, 
                        std::forward_as_tuple(key), // one-element tuple
                        std::forward_as_tuple(0, 0) // args to construct mapped_type
                     ).first);
it->second.first++;

// As in all solutions, get your reference from the iterator we already have
int const& my_ref(it->first);
于 2013-02-15T22:23:41.847 に答える
1

私が正しく理解していれば、あなたが望むのは、ではなく、operator[]を返すことです。の現在のインターフェイスはそのような機能を提供せず、実装はプライベートメンバーに依存しています（少なくともブースト実装では、私の環境ではC ++ 11 stdファイルにアクセスできません）。iteratormapped_typeunordered_mapoperator[]

JoergBの答えはより速く、KerrekSBの答えはメモリフットプリントが小さくなると思います。プロジェクトにとって何がより重要かを決めるのはあなた次第です。

于 2013-02-19T16:47:39.950 に答える
1

これはどう：

auto it = hash.find(key);

if (it == hash.end()) { it = hash.emplace(key, std::make_pair(0, 0)).first; }

++it->second.first;

int const & my_ref = it->first;   // must be const

（それが順序付けられたマップである場合lower_bound、ツリーウォークをリサイクルするために挿入を使用してヒントを与えます。）

于 2013-02-11T23:02:04.237 に答える