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

Question

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

其次,在下面的一段代码中,我怀疑在unordered_map中没有键的情况下,我正在通过该行执行第二次查找map[key] = value,以便在使用[]运算符时替换在那里创建的默认值钥匙不存在.

这是真的,如果是这样的话(可能通过使用指针或其他东西)我可能只在任何情况下执行一次查找(可能通过存储放置值的位置/从中读取值)和仍然实现相同的功能？显然,如果是这样,这将是一项有用的效率改进.

以下是修改后的代码摘录:

    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(),因为它可以节省必须重新散列密钥.

在代码中进行多次查找的一种方法是获取对值的引用:

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;

请注意,如果地图中不存在该值,operator[]则将默认构造并插入一个.因此,虽然这将避免多次查找,但如果使用default-construct + assign较慢的类型而不是copy-或move-construct,则实际上可能会更慢.

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

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

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

但是如果你已经获得了价值,那么你可以非常高效地完成它 - 比使用上面的参考+幻数更有效率:

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

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

Answer 2

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

<'z',200>如果该对不存在,则此处将该对插入到映射中.如果返回的对的第二个元素的值为true,则返回插入它的迭代器,或者,如果该对的第二个元素为false,则返回元素实际所在的迭代器.