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

Question

首先有人可以澄清一下在 C++ 中使用 [] 运算符和 unordered_map 进行查找是否包含对 find() 方法的调用，或者使用 [] 运算符是否比 find() 更快？

其次，在下面的代码中，我怀疑在键不在 unordered_map 中的情况下，我正在通过 map[key] = value 行进行第二次查找当键不存在时，使用 [] 运算符替换此处创建的默认值。

这是真的吗，如果是这样的话，有没有办法(可能通过使用指针或其他东西)我可能在任何情况下都只执行一次查找(可能通过存储放置值/读取值的地址from) 并且仍然实现相同的功能？如果是这样，显然这将是一个有用的效率改进。

这里是修改后的代码摘录:

    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;

Answer 1

operator[]将为您插入一个具有默认构造值的条目(如果尚不存在)。它等效于，但可能会比以下更有效地实现:

iterator iter = map.find(key);

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

return *iter;

operator[] 可以比使用 find() 手动完成工作更快。和 insert() ，因为它可以省去重新散列 key 的麻烦。

您可以解决在代码中进行多次查找的一种方法是引用该值:

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;

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

虽然 int 廉价地默认构造为 0，但您也许可以将 0 视为表示空的魔数(Magic Number)。您的示例中可能就是这种情况。

如果你没有这样的魔数(Magic Number)，你有两个选择。您应该使用什么取决于您计算该值的成本。

首先，当散列键很便宜但计算值很昂贵时，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;

但如果你已经获得了值(value)，你可以非常有效地做到这一点——也许比使用上面的引用 + 魔数(Magic Number)更有效:

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

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