What are the restrictions on std::map<K, V>::mapped_type?

Question

Consider this code:

#include <iostream>
#include <map>
#include <string>

using namespace std;

class Foo {
  public:
  Foo() {}
  virtual ~Foo() {}

  void DoFoo() { cout << "Foo" << endl; }

  Foo(const Foo&) = delete;
  void operator=(const Foo&) = delete;
};

int main() {
  map<string, Foo> m;
  m["Foo"].DoFoo();
}

Both g++ and clang++ fail compilation when they're using a libstdc++ version earlier than 4.8. The exact error message clang++ spits out is:

In file included from /usr/include/c++/4.6/iostream:39:

In file included from /usr/include/c++/4.6/ostream:39:

In file included from /usr/include/c++/4.6/ios:40:

In file included from /usr/include/c++/4.6/bits/char_traits.h:40:

In file included from /usr/include/c++/4.6/bits/stl_algobase.h:65:

/usr/include/c++/4.6/bits/stl_pair.h:121:35: error: call to deleted constructor of 'Foo'

: first(std::forward<_U1>(__x)), second(__y) { }

^ ~~~

/usr/include/c++/4.6/bits/stl_pair.h:267:14: note: in instantiation of function template specialization 'std::pair, Foo>::pair, void>' requested here

return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y));

^

/usr/include/c++/4.6/bits/stl_map.h:467:29: note: in instantiation of function template specialization 'std::make_pair, Foo>' requested here

__i = insert(__i, std::make_pair(std::move(__k), mapped_type()));

^

21 : note: in instantiation of member function 'std::map, Foo, std::less >, std::allocator, Foo> > >::operator[]' requested here

m["Foo"].DoFoo();

It seems like std::pair's constructor is trying to use Foo's copy-constructor, which I guess is fair enough since Foo doesn't declare a move constructor. As I would expect, providing a (default) move constructor fixes the issue.

However, compilation succeeds without a move constructor defined when the version of libstdc++ used is 4.8 or higher. I'm confident that the compiler is the same in both cases and only the libstdc++ version varies. Foo(Foo&&) = delete; also doesn't affect clang's ability to properly compile in this case.

My question has a few facets:

Why does the old version of libstdc++ require the move constructor to be user-provided in order to use it instead of the copy-constructor?

What's different in the newer version of the library that allows it to create the new element (as per operator[]'s contract) without any move/copy constructors or operator=?

Which of the implementation is conforming? What does the standard say about std::map<K, V>::mapped_type, if anything?

23.2.4.7 has The associative containers meet all the requirements of Allocator-aware containers (23.2.1), except that for map and multimap, the requirements placed on value_type in Table 96 apply instead to key_type and mapped_type. [ Note: For example, in some cases key_type and mapped_type are required to be CopyAssignable even though the associated value_type, pair<const key_type, mapped_type>, is not CopyAssignable. —end note ] could be what is causing the issue. — NathanOliver
@CoryKramer that seems to be using a recent libstdc++, which I know to be compiling fine. — anthonyvd
@NathanOliver Thanks, I'll try to look around there! The note kind of points towards the newer version of libstdc++ being less strict than the standard, doesn't it? — anthonyvd

Barry Barry · Accepted Answer · 2015-07-10T18:07:21

In C++11, [map.access] reads:

T& operator[](const key_type& x);

1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

2 Requires: key_type shall be CopyInsertable and mapped_type shall be DefaultInsertable into *this.

3 Returns: A reference to the mapped_type corresponding to x in *this.

4 Complexity: Logarithmic.

The only requirement on operator[] on mapped_type is that it is DefaultInsertable (basically, DefaultConstructible). If the library doesn't support a non-copyable mapped_type with operator[], then it's a bug.

What are the restrictions on std::map<K, V>::mapped_type?

1 Answers