使用C++ unordered_map的[]运算符的高效方法

Question

使用C++ unordered_map的[]运算符的高效方法

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;

- Darius

3个回答

10

你可以使用特殊的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;
  }

如果这个键值对在map中不存在，以下代码会将<'z',200>插入到map中。如果返回的pair的第二个元素为true，则返回插入的迭代器，否则返回实际上该元素所在位置的迭代器。

- Diego Sevilla

这是一个有用的答案，所以感谢您的贡献。我想我会选择其中一个利用存储引用的方案，因为从可读性上看它更加清晰（我当然不确定效率上的差异！），但还是非常感谢您的帮助。 - Darius

通常情况下，如果计算值的成本很高，则无法始终进行插入。在这种情况下，使用映射以避免重新计算该值 - 这是您的代码完全缺乏的优势。 - Sjoerd

@Sjoerd，根据问题描述，似乎计算该过程的值并不是一个耗时的任务。如果不是这样，请问为什么要试图优化对（哈希）映射的一两次访问，这通常只会是O(1)？ - Diego Sevilla

@Diego 很好的观点，尽管计算哈希值也可能是耗时的。 - Sjoerd

@Diego 注意，耗时的计算也是O(1)，因为它很可能不依赖于unordered_map的大小。因此，即使重新计算需要很长时间，始终重新计算都是O(1)。 - Sjoerd

2

首先，有人能否澄清一下，在C++中，使用[]运算符与unordered_map进行查找是否会调用Find()方法，或者使用[]运算符比Find()更快？

没有规定。[]的实现可以使用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;

- Ferdinand Beyer

这看起来正是我想要的，非常感谢。只是出于兴趣，如果&代表着“地址”，那为什么不能说stored_val=value; 其中表示“存储在其中的值”？请纠正我对语法的可能误解！ - Darius

1

在C++中，“&”既用于“取地址”（获取指针），也用于引用（隐式指针）。在这里，“int&”是一个引用，而不是指针（这将是“int”）。您不必解引用引用，因此无需编写“stored_value = ...”。 - Ferdinand Beyer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cory Nelson · Accepted Answer

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;

请注意，如果map中不存在该值，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)返回的bool值为true，则表示该项已插入成功。否则，该项已存在且未进行任何修改。返回的迭代器指向映射中已插入或存在的值。对于您的简单示例，这可能是最佳选项。