[Bug libstdc++/78595] New: Unnecessary copies in _Rb_tree

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78595

            Bug ID: 78595
           Summary: Unnecessary copies in _Rb_tree
           Product: gcc
           Version: 7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org
  Target Milestone: ---

#include <map>
#include <stdio.h>

struct X {
  operator std::pair<const int, int>() const { puts("conv"); return {}; }
};

int main()
{
  std::map<int, int> m;
  m.insert(X());
}

This prints "conv" twice, because we create a temporary to get the key here:

      pair<_Base_ptr, _Base_ptr> __res
        = _M_get_insert_unique_pos(_KeyOfValue()(__v));

and then again when we insert the node:

          return _Res(_M_insert_(__res.first, __res.second,
                                 _GLIBCXX_FORWARD(_Arg, __v), __an),
                      true);

This is bad.

Either we should have separate _Rb_tree::_M_insert_unique() functions that take
value_type arguments, to avoid unnecessary temporaries, and the generic one
taking _Arg&& should create a local value_type object, get the key from that,
and then move from it if insertion happens.

Alternatively, we could constrain the map::insert(_Pair&&) function that calls
it so it's only used when !is_same<decay_t<_Pair>, value_type> and create the
copy there, and ensure _M_insert_unique(_Arg&&) is only ever called with
value_type arguments.

There's a similar problem for multimap:

#include <map>
#include <stdio.h>

struct X {
  operator std::pair<const int, int>() const { puts("conv"); return {}; }
};

int main()
{
  std::multimap<int, int> m;
  m.insert(X());
}

This also prints "conv" twice, and here we *definitely* don't need the
temporary in order to get the key, because we know that insertion always
succeeds. This is bad too.