2354. Unnecessary copying when inserting into maps with braced-init syntax

Section: 26.4.4.1 [map.overview], 26.4.5.1 [multimap.overview], 26.5.4.1 [unord.map.overview], 26.5.5.1 [unord.multimap.overview] Status: C++17 Submitter: Geoffrey Romer Opened: 2014-01-08 Last modified: 2017-10-15

Priority: 2

View all other issues in [map.overview].

View all issues with C++17 status.

Discussion:

The rvalue-reference insert() members of map, multimap, unordered_map, and unordered_multimap are specified as function templates, where the rvalue-reference parameter type depends on the template parameter. As a consequence, these overloads cannot be invoked via braced-initializer syntax (e.g. my_map.insert({key, value})), because the template argument cannot be deduced from a braced-init-list. Such calls instead resolve to the const lvalue reference overload, which forces a non-elidable copy of the argument, despite the fact that the argument is an rvalue, and so should be eligible for moving and copy elision.

This leads to sub-optimal performance for copyable values, and makes this syntax unusable with noncopyable values. This is particularly problematic because sources such as Josuttis's "C++ Standard Library" recommend this syntax as the preferred way to insert into a map in C++11.

I think this can be fixed by adding an equivalent non-template value_type&& overload for each affected member template. Simply declaring these members in the class synopses should be sufficient; their semantics are already dictated by the container concepts (c.f. the corresponding lvalue-reference overloads, which have no additional discussion beyond being listed in the synopsis).

[2014-02-13 Issaquah]

AJM: Is this not better solved by emplace?

Nico: emplace was a mistake, it breaks a uniform pattern designed into the STL. Hence, this fix is important, it should be the preferred way to do this.

JonW: emplace is still more efficient, as this form must make a non-elidable copy.

GeoffR: Also, cannot move from a const key, must always make a copy.

Poll for adopting the proposed wording:

SF: 1 WF: 4 N: 4 WA: 1 SA: 0

Move to Ready, pending implementation experience.

Proposed resolution:

This wording is relative to N3797.

  1. Change 26.4.4.1 [map.overview], class template map synopsis, as indicated:

    […]
    pair<iterator, bool> insert(const value_type& x);
    pair<iterator, bool> insert(value_type&& x);
    template <class P> pair<iterator, bool> insert(P&& x);
    iterator insert(const_iterator position, const value_type& x);
    iterator insert(const_iterator position, value_type&& x);
    template <class P>
      iterator insert(const_iterator position, P&&);
    […]
    
  2. Change 26.4.5.1 [multimap.overview], class template multimap synopsis, as indicated:

    […]
    iterator insert(const value_type& x);
    iterator insert(value_type&& x);
    template <class P> iterator insert(P&& x);
    iterator insert(const_iterator position, const value_type& x);
    iterator insert(const_iterator position, value_type&& x);
    template <class P> iterator insert(const_iterator position, P&& x);
    […]
    
  3. Change 26.5.4.1 [unord.map.overview], class template unordered_map synopsis, as indicated:

    […]
    pair<iterator, bool> insert(const value_type& obj);
    pair<iterator, bool> insert(value_type&& obj);
    template <class P> pair<iterator, bool> insert(P&& obj);
    iterator insert(const_iterator hint, const value_type& obj);
    iterator insert(const_iterator hint, value_type&& obj);
    template <class P> iterator insert(const_iterator hint, P&& obj);
    […]
    
  4. Change 26.5.5.1 [unord.multimap.overview], class template unordered_multimap synopsis, as indicated:

    […]
    iterator insert(const value_type& obj);
    iterator insert(value_type&& obj);
    template <class P> iterator insert(P&& obj);
    iterator insert(const_iterator hint, const value_type& obj);
    iterator insert(const_iterator hint, value_type&& obj);
    template <class P> iterator insert(const_iterator hint, P&& obj);
    […]