在 C++ unordered_map 中有效地使用 [] 运算符

Using The [] Operator Efficiently With C++ unordered_map

提问by Darius

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()?

首先，有人可以澄清一下，在 C++ 中，将 [] 运算符与 unordered_map 结合使用是否包含对 find() 方法的调用，还是使用 [] 运算符比 find() 更快？

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] = valuein order to replace the default value created there by using the [] operator when a key is not present.

其次，在下面的一段代码中，我怀疑如果键不在 unordered_map 中，我将通过该行执行第二次查找map[key] = value，以便替换使用 [] 运算符在那里创建的默认值，当 a键不存在。

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;

回答by Cory Nelson

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:

operator[]将为您插入一个具有默认构造值的条目（如果尚未存在）。它等效于，但可能比以下内容更有效地实施：

iterator iter = map.find(key);

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

return *iter;

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

operator[]可以比使用find()and手动完成工作更快insert()，因为它可以节省重新散列密钥的时间。

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;

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.

请注意，如果该值在地图中不存在，operator[]则将默认构造并插入一个。因此，虽然这将避免多次查找，但如果与默认构造 + 分配比复制或移动构造慢的类型一起使用，它实际上可能会更慢。

With intthough, 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.

随着int虽然，这便宜的默认构造为0，你也许能够把0作为一个神奇的数字意味着空。在您的示例中可能就是这种情况。

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.

如果你没有这样的神奇数字，你有两个选择。您应该使用什么取决于您计算价值的成本。

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:

首先，当散列密钥很便宜但计算值很昂贵时，find()可能是最好的选择。这将散列两次，但仅在需要时计算值：

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;

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.first;

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.

如果返回的 boolmap.insert(value_type)为 true，则该项目已插入。否则，它已经存在并且没有进行任何修改。迭代器返回指向地图中插入或现有值的点。对于您的简单示例，这可能是最佳选择。

回答by Diego Sevilla

You can both check if an element exists, andinsert a new element if it does not exist, with the special insertfunction that returns a pair<iterator, bool>in which the boolean value tells you if the value has been actually inserted. For example, the code here:

你既可以检查元素是否存在，并插入一个新的元素，如果不存在的话，可使用特殊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;
  }

The code here inserts the pair <'z',200>into the map if it does not exist. It returns the iterator where it is inserted if the value of the second element of the pair returned is true, or, it returns the iterator where the element actually was, if the second element of the pair is false.

<'z',200>如果它不存在，这里的代码将把该对插入到地图中。如果返回的元素对的第二个元素的值为真，则返回它插入的迭代器，或者，如果元素对的第二个元素为假，则返回元素实际所在的迭代器。

回答by Ferdinand Beyer

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()?

首先，有人可以澄清一下，在 C++ 中，将 [] 运算符与 unordered_map 结合使用是否包含对 Find() 方法的调用，还是使用 [] 运算符比 Find() 更快？

There is no rule for that. An implementation of []could use find(), it could perform the lookup by itself or it could delegate the lookup to some private method that is also used by find()internally.

对此没有规定。的实现[]可以使用find()，它可以自己执行查找，也可以将查找委托给一些find()内部也使用的私有方法。

There is also no guarantee on which one is faster. find()involves an overhead in constructing and returning an iterator, whereas []will probably be slower if the key does not exist, as it inserts a new value in this case.

也不能保证哪个更快。 find()涉及构建和返回迭代器的开销，而[]如果键不存在，则可能会更慢，因为在这种情况下它会插入一个新值。

(...) is there a way (perhaps by use of pointers or something) that I might only perform one look up in any case (...)

(...) 有没有一种方法（也许通过使用指针或其他东西），我可能只在任何情况下执行一次查找（...）

If the key is not in the map, []will insert a new default-constructed value, and return a reference. Therefore, you could store that reference to save the second lookup:

如果键不在地图中，[]将插入一个新的默认构造值，并返回一个引用。因此，您可以存储该引用以保存第二次查找：

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;