38

首先，有人可以澄清在 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;
4

3 回答 3

48

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

iterator iter = map.find(key);

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

return *iter;

operator[]find()可以比使用and手动完成工作更快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[]将默认构造并插入一个。因此，虽然这将避免多次查找，但如果与默认构造 + 分配比复制或移动构造更慢的类型一起使用，它实际上可能会更慢。

虽然，它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;

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

于 2011-08-01T11:38:21.407 回答
10

您可以检查一个元素是否存在，如果不存在则插入一个新元素，使用insert返回 a 的特殊函数，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>如果该对不存在，则此处的代码将其插入到映射中。如果返回的对的第二个元素的值为真，则返回插入它的迭代器；如果对的第二个元素为假，则返回元素实际所在的迭代器。

于 2011-08-01T11:40:07.643 回答
2

首先，有人可以澄清在 C++ 中使用 [] 运算符与 unordered_map 一起进行查找是否包装了对 Find() 方法的调用，还是使用 [] 运算符比 Find() 更快？

没有规则。[]can use的实现find()，它可以自己执行查找，也可以将查找委托给内部也使用的某个私有方法find()。

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

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

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

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;
于 2011-08-01T11:39:15.300 回答