Why doesn't C++ std::map::operator[] use inplace new?

Question

If you use the C++ std::map (and other containers) with value types, you'll notice that inserting into the map calls the destructor for your element type. This is because the implementation of operator [] is required by the C++ spec to be equivalent to this:

(*((std::map<>::insert(std::make_pair(x, T()))).first)).second

It calls the default constructor of your type in order to build that pair. That temporary value is then copied into the map, and then destructed. Confirmation of this can be found in this stackoverflow post and here on codeguru.

What I find odd is that this could be implemented without the need for the temporary variable and still be equivalent. There is a feature of C++ called "inplace new". The std::map and other containers could allocate empty space for the object to live and then explicitly call the element's default constructor on the allocated space.

My question: Why do none of the implementations of std::map that I've seen use inplace new to optimize this operation? It seems to me that it would considerably improve the performance of this low-level operation. But many eyes have studied the STL code base, so I figure there must be some reason it is done this way.

Answer 1

In general, you specifying a higher level operation like [] in terms of lower level ones is a good idea.

Prior to C++11, doing so with [] would be difficult without using insert.

In C++11, the addition of std::map<?>::emplace and similar stuff for std::pair gives us the ability to avoid that problem. If you redefined it so use such in-place construction, the extra (hopefully elided) object creation would go away.

I cannot think of a reason not do this. I would encourage you to propose it for standardization.

To demonstrate copy-less insertion into a std::map, we can do the following:

#include <map>
#include <iostream>

struct no_copy_type {
  no_copy_type(no_copy_type const&)=delete;
  no_copy_type(double) {}
  ~no_copy_type() { std::cout << "destroyed\n"; }
};
int main() {
  std::map< int, no_copy_type > m;
  m.emplace(
    std::piecewise_construct,
    std::forward_as_tuple(1),
    std::forward_as_tuple(3.14)
  );
  std::cout << "destroy happens next:\n";
}

live example -- as you can see, no temporary is generated.

So if we replace

(*((std::map<>::insert(std::make_pair(x, T()))).first)).second

with

(*
  (
    (
      std::map<>::emplace(
        std::piecewise_construct,
        std::forward_as_tuple(std::forward<X>(x)),
        std::forward_as_tuple()
    )
  ).first
).second

no temporary would be created (whitespace added so I could keep track of ()s).