3

问题：

人们对此抱怨： 在 STL 地图中，使用 map::insert 比使用 [] 更好吗？

访问时

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; }

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

为什么不？

在知道您需要它之前构建新元素的这种悲观方法可能会导致其他问题吗？

这是标准库，他们应该不遗余力地对其进行优化。为什么不使用这种简单的方法？

4

1 回答 1

5

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

// 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;
}

您发布的代码片段不是 from std::map，而是 from hash_map，它是库的 GCC扩展：

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，如果元素存在，则不使用构造函数。

于 2013-10-26T07:41:14.460 回答