c++ - 避免在 unordered_map 插入中进行额外处理

Question

我有一个 std::unordered_map，我希望两者都递增 std::pair 中的第一个值，通过 key 散列>，并创建对 key 的引用。例如:

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

我非常倾向于使用第一个选项，但我似乎无法决定哪个是最好的。对此有更好的解决方案吗？

P.S.:对我来说，一个理想的解决方案是不需要初始的、可能无用的值分配的插入。

Answer 1

正如其他人所指出的，一个“分配”一个std::pair<int,int>实际上无非是复制两个整数(在堆栈上)。对于 map<int,pair<int,int>>::value_type ，即 pair<int const, pair<int, int>>你三岁int s，因此使用第二种方法不会产生重大开销。您可以使用 emplace 稍微优化一下而不是 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)必然会更昂贵，因为元素搜索肯定会比迭代器取消引用更昂贵。

在构造 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);