3

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?

Community
  • 1
  • 1
Sam
  • 19,708
  • 4
  • 59
  • 82
  • 1
    Are you sure he spec requires this? Could a conformant implementation be more efficient? – templatetypedef Oct 26 '13 at 07:31
  • 1
    Well, this is what I ask. Code example is from gcc's libstdc++ – Sam Oct 26 '13 at 07:32
  • One naive hypothesis might be that whoever wrote that code did not consider the possibility that the default ctor may incur a non-trivial cost. – NPE Oct 26 '13 at 07:41
  • What you proposed is done (depending on compiler version). However it doesn't address the problem of `data[non_existing_key] = some_new_value` which requires the creation of the default value so it can be assigned to. – Michael Burr Oct 26 '13 at 07:49

1 Answers1

5

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.

Zeta
  • 103,620
  • 13
  • 194
  • 236