Why is map::operator[] slow by design?

Question

The problem:

Peope complain about this: In STL maps, is it better to use map::insert than []?

When accessing

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

The implementation is simple and elegant, but completely inefficient (well, taken from unordered_map).

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

The obvious solution

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

Where find_or_insert_default would call _Tp() only if needed (i.e. the element does not exist)

Why not?

Is it some other problem that may be caused by this pessimistic approach in building a new element before knowing you need it?

This is standard library, they should go to great lengths to optimize it. Why not use this simple approach?

Answer 1

There hasn't been such issue with std::map at least since 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;
}

The snippet you posted isn't from std::map, but from hash_map, which was a GCC extension to the library:

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  */

Since it's an extension the maintainers are not really obligated to follow any complexity/performance rules (even though your proposed function would be faster). Note that hash_map has been replaced by an implementation for std::unordered_map, which doesn't use the constructor if the element exists.