有效地使用[]运算符使用C ++ unordered_map [英] Using The [] Operator Efficiently With C++ unordered_map

问题描述

首先有人可以澄清在C ++中使用[]运算符与unordered_map结合使用查找包装对find（）方法的调用，还是使用[]运算符比find（）快？

Firstly could someone clarify whether in C++ the use of the [] operator in conjunction with an unordered_map for lookups wraps a call to the find() method, or is using the [] operator quicker than find()?

其次，在下面的代码中，我怀疑在unordered_map中的键不存在的情况下，我通过 map [key] = value ，以便在不存在键时使用[]运算符替换那里创建的默认值。

Secondly, in the following piece of code I suspect in cases where the key is not already in the unordered_map I am performing a second look up by way of the line map[key] = value in order to replace the default value created there by using the [] operator when a key is not present.

这是真的，如果是这样，有一种方式（可能通过使用指针或某物），我可能只执行一次查找在任何情况下在哪里放置值/读取值的地址）并仍然实现相同的功能？

Is that true, and if so is there a way (perhaps by use of pointers or something) that I might only perform one look up in any case (perhaps by storing the address of where to place a value/read a value from) and still achieve the same functionality? Obviously this would be a useful efficiency improvement if so.

这是修改后的代码摘录：

Here is the modified code excerpt:

    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;

推荐答案

operator [] 将为您插入一个默认构造的值，如果有一个是不是已经在那里。它等效于，但是可能比以下实现更有效：

operator[] will insert an entry for you with a default-constructed value, if one isn't already there. It is equivalent to, but will probably be implemented more efficiently than:

iterator iter = map.find(key);

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

return iter;

operator [] 使用 find（） 手动执行工作和 insert（） ，因为它

operator[] can be quicker than doing the work manually with find() and insert(), because it can save having to re-hash the key.

您可以在代码中执行多次查找的方法之一是引用该值：

One way you can work around having multiple lookups in your code is to take a reference to the value:

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;

请注意，如果值在地图中不存在， ] 将默认构造并插入一个。因此，虽然这将避免多次查找，但如果使用比default-construct + assign更慢的类型，而不是copy或move-construct，它可能会更慢。

Note that if the value doesn't exist in the map, operator[] will default-construct and insert one. So while this will avoid multiple lookups, it might actually be slower if used with a type that is slower to default-construct + assign than to copy- or move-construct.

使用 int 虽然，这便宜的默认构造为0，你可能能够把0当作一个幻数，意味着空。这看起来像是你的例子中的情况。

With int though, which cheaply default-constructs to 0, you might be able to treat 0 as a magic number meaning empty. This looks like it might be the case in your example.

如果你没有这样的魔法数字，你有两个选择。

If you have no such magic number, you've got two options. What you should use depends on how expensive it is for you to compute the value.

首先，当散列密钥是便宜的，但是计算的价值是昂贵的， find（）可能是最好的选择。这将哈希两次，但只在需要时计算值：

First, when hashing the key is cheap but computing the value is expensive, find() may be the best option. This will hash twice but only compute the value when needed:

iterator iter = map.find(key);

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

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

return value;

但是如果你已经有了值，你可以非常有效地 - 有效地比使用如上所述的引用+幻数：

But if you've got the value already, you can do it very efficiently -- perhaps slighty more efficiently than using a reference + magic number as above:

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

如果 map.insert（value_type）为true，则说明该项已插入。否则，它已经存在并且没有进行修改。迭代器返回指向地图中的已插入或现有值的点。对于你的简单例子，这可能是最好的选择。

If the bool returned by map.insert(value_type) is true, the item was inserted. Otherwise, it already existed and no modifications were made. The iterator returned points to the inserted or existing value in the map. For your simple example, this may be the best option.

这篇关于有效地使用[]运算符使用C ++ unordered_map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！