error by move assignment of map with non-copyable (but movable) key

Question

Why does this doesn't work:

#include <memory>
#include <map>

std::map<std::unique_ptr<char>, std::unique_ptr<int>> foo();
std::map<std::unique_ptr<char>, std::unique_ptr<int>> barmap;

int main(){
  barmap=foo();
  return 0;
}

while this does:

#include <memory>
#include <map>

std::map<std::unique_ptr<char>, std::unique_ptr<int>> foo();
std::map<std::unique_ptr<char>, std::unique_ptr<int>> barmap;

int main(){

  std::map<std::unique_ptr<char>, std::unique_ptr<int>> tmp(foo());
  using std::swap;
  swap(barmap, tmp);
  return 0;
}

This has to do with the fact that key type in the map is not copyable (does std::map require that?). Relevant error lines when compiling with g++ -std=c++14:

/usr/include/c++/4.9/ext/new_allocator.h:120:4: error: use of deleted function ‘constexpr std::pair<_T1, _T2>::pair(std::pair<_T1, _T2>&&) [with _T1 = const std::unique_ptr<char>; _T2 = std::unique_ptr<int>]’
  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
    ^
In file included from /usr/include/c++/4.9/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/4.9/memory:62,
                 from pairMove.cpp:1:
/usr/include/c++/4.9/bits/stl_pair.h:128:17: note: ‘constexpr std::pair<_T1, _T2>::pair(std::pair<_T1, _T2>&&) [with _T1 = const std::unique_ptr<char>; _T2 = std::unique_ptr<int>]’ is implicitly deleted because the default definition would be ill-formed:
       constexpr pair(pair&&) = default;
                 ^
/usr/include/c++/4.9/bits/stl_pair.h:128:17: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = char; _Dp = std::default_delete<char>]’
In file included from /usr/include/c++/4.9/memory:81:0,
                 from pairMove.cpp:1:
/usr/include/c++/4.9/bits/unique_ptr.h:356:7: note: declared here
       unique_ptr(const unique_ptr&) = delete;

Entire error message to be seen at ideone.

It seems to me that defaulted move constructor of std::pair attempts to use a copy constructor of std::unique_ptr. I presume that map assignment operator uses move assignments of new map contents over the old ones, and std::swap cannot do this since it needs to keep old contents intact, so it just swaps internal data pointers, so it avoids problems.

The necessity to (at least be able to) move assign might come from problems with allocator_traits<M::allocator_type>::propagate_on_container_move_assignment in C++11, but I was under impression that in C++14 the whole thing was fixed. I am not sure why STL would choose to move-assign elements instead of just exchanging data pointers between containers in move-assignment operator.

And all of the above doesn't explain why move-assignment of pairs contained in moved map fails - IMHO it shouldn't.

Btw: g++ -v:

gcc version 4.9.2 (Ubuntu 4.9.2-0ubuntu1~14.04) 

Answer 1

To me this looks like a fundamental failure of the specification in the C++ standard. The specification goes too far in "do not repeat yourself", as to become unreadable and ambiguous (imho).

If you read further to the table Allocator-aware container requirements this same row says (for a = rv):

Requires: If allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is false, T is MoveInsertable into X and MoveAssignable. All existing elements of a are either move assigned to or destroyed. post: a shall be equal to the value that rv had before this assignment.

I think everyone can agree that std::map<std::unique_ptr<char>, std::unique_ptr<int>> is an allocator-aware container. Then the question becomes: What are the requirements on its move assignment operator?

If we look only at the Allocator-aware container requirements, then MoveInsertable and MoveAssignable are only required if allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is false. And this is a weaker requirement than stated by the Container requirements table which states that all elements must be MoveAssignable regardless of the properties of the allocator. So must allocator-aware containers also meet the stricter requirements of containers?

Let's unwind this to what the standard should say if it wasn't trying so hard to not repeat itself.

What does the implementation require?

If allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true then all ownership of memory resources can be transferred from the rhs to the lhs during move assignment. This means that map move assignment can do nothing but O(1) pointer twiddling to accomplish move assignment (when memory ownership can be transferred). Pointer twiddling does not require any operations on the objects that the pointers point to.

Here is the libc++ implementation of map assignment when allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true:

https://github.com/llvm-mirror/libcxx/blob/master/include/__tree#L1531-L1551

One can see that absolutely no requirements need to be placed on the key_type or value_type.

Should we artificially place requirements on these types?

What purpose would that serve? Would it help or hurt clients of std::map?

My personal opinion is that making requirements on client types that aren't needed will only serve to frustrate the clients.

I also believe that the current style of specification of the C++ standard is so convoluted that even experts can't agree on what the specification says. This isn't because the experts are idiots. It is because making a correct, unambiguous specification (on this scale) is truly a very difficult problem.

Finally I believe that the intent is (or should be) that the Allocator-aware container requirements supersede the Container requirements when a specification conflict arises.

One final complication: In C++11:

allocator_traits<allocator<T>>::propagate_on_container_move_assignment{} is false_type

where as in C++14:

allocator_traits<allocator<T>>::propagate_on_container_move_assignment{} is true_type

So the libstdc++ behavior is conforming in C++11, and the libc++ behavior is conforming in C++14. LWG issue 2103 made this change.

Answer 2

I believe this is a bug quality of implementation issue in libstdc++. If we look in the container requirements table (now table 100), one of the requirements is:

a = rv

where a is a value of type X (the container class) and rv denotes a non-const rvalue of type X. The operational semantics are described as:

All existing elements of a are either move assigned to or destroyed

It is stated in [map.overview] that:

A map satisfies all of the requirements of a container

One of those requirements is move assignment. Now apparently libstdc++'s approach is to move assign elements even in the case where Key is non-copyable (which would make pair<const Key, T> non-moveable - note that it's only Key's noncopyability that is relevant here). But there is no mandate that move assignment happens, it is merely an option. Note that the code compiles fine with libc++.

Answer 3

barmap=foo();

is allowed to require a move-assignment into the map's value_type.

Reasoning:

from §23.4.4.1

For a map<Key,T> the key_type is Key and the value_type is pair<const Key,T>.

§ 23.2.3

5 For set and multiset the value type is the same as the key type. For map and multimap it is equal to pair<const Key, T>.

7 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 95 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, is not CopyAssignable. — end note ]

From Table 95:

Expression :

a = rv

Return type :

X&

Operational semantics:

All existing elements of a are either move assigned to or destroyed

Assertion/note pre-/post-condition:

a shall be equal to the value that rv had before this assignment

Complexity:

linear

so you would need to provide a const Key&& move-assignment to make it portable.

like this:

#include <memory>
#include <map>

struct key {

  key(key&&);
  key(const key&&);
  key& operator=(key&&);
  key& operator=(const key&&);
};
bool operator<(const key& l, const key& r);

struct value {

};

using map_type = std::map<key, value>;

map_type foo();
map_type foo2();

int main(){
  auto barmap=foo();
  barmap = foo2();
  return 0;
}

see it compile here: https://godbolt.org/g/XAQxjt

link to 2015 draft standard I have used (I know there is a later one, but the line remains in the most recent draft, now in table 100)

http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/n4527.pdf

My apologies to anyone who finds the answer unacceptable, but the words really are there.