c++ - 为什么 map::operator[] 设计缓慢？

Question

问题:

人们提示这个: In STL maps, is it better to use map::insert than []?

访问时

std::map<Key, ExpensiveDefaultConstructorValue> data;
data[key1] // <-- Calls default constructor each time it is called, 
           // even when the element is there

实现简单而优雅，但效率很低(好吧，取自 unordered_map)。

_Tp& operator[](const key_type& __key)
   { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }

显而易见的解决方案

_Tp& operator[](const key_type& __key)
   { return _M_ht.find_or_insert_default(key_type(__key)).second; }

find_or_insert_default 仅在需要时调用 _Tp()(即元素不存在)

为什么不呢？

这种在知道自己需要之前就构建新元素的悲观做法是否可能导致其他问题？

这是标准库，他们应该竭尽全力优化它。为什么不使用这种简单的方法？

Answer 1

至少从g++ 4.5 开始，std::map 就没有这样的问题了。 :

// stripped comments and requirements
mapped_type&
operator[](const key_type& __k)
{    
    iterator __i = lower_bound(__k);

    if (__i == end() || key_comp()(__k, (*__i).first))
        __i = insert(__i, value_type(__k, mapped_type()));
    return (*__i).second;
}

您发布的代码段不是来自 std::map，而是来自 hash_map，这是一个 GCC extension去图书馆:

00052 /** @file backward/hash_map
00053  *  This file is a GNU extension to the Standard C++ Library (possibly
00054  *  containing extensions from the HP/SGI STL subset).
00055  */

因为它是一个扩展，所以维护者实际上没有义务遵循任何复杂性/性能规则(即使您提议的功能会更快)。请注意，hash_map 已替换为 std::unordered_map 的实现，如果元素存在，则不使用构造函数。