Deleted Function in std::pair when using a unique_ptr inside a map

The problem originates from the following post-condition of std::vector<T>::resize, [vector.capacity]:

Remarks: If an exception is thrown other than by the move constructor of a non-CopyInsertable T there are no effects.

That is, a vector must remain unchanged if relocation fails. One of the reasons relocation may fail is due to an exception, specifically, when a copy or move constructor, used for shifting elements from an old storage to a new one, throws an exception.

Does copying elements change the original storage in any way? No¹. Does moving elements change the original storage? Yes. Which operation is more efficient? Moving. Can a vector always prefer moving to copying? Not always.

If a move constructor can throw an exception, there's no possibility to restore the original content of the old storage, because an attempt to move the already shifted elements back to the old chunk may fail again. In such a case, a vector will use a move constructor to relocate its elements from the old storage to a new one only if that move constructor guarantees it will not throw an exception (or a move constructor is the only option when a copy constructor is not available). How does a function promise it will not throw an exception? One will be annotated with the noexcept specifier and tested with the noexcept operator.

Testing the below code with icc:

std::map<int, std::unique_ptr<int>> m;
static_assert(noexcept(std::map<int, std::unique_ptr<int>>(std::move(m))), "!");

fails on the assertion. This means that m is not nothrow-MoveConstructible.

Does the standard require it to be noexcept? [map.overview]:

// [map.cons], construct/copy/destroy:
map(const map& x);
map(map&& x);

std::map is both Move- and CopyConstructible. Neither is required not to throw an exception.

However, an implementation is allowed to provide this guarantee ^{{{citation needed}}}. Your code uses the following definition:

map(map&&) = default;

Is an implicitly generated move constructor required to be noexcept? [except.spec]:

An inheriting constructor ([class.inhctor]) and an implicitly declared special member function (Clause [special]) have an exception-specification. If f is an inheriting constructor or an implicitly declared default constructor, copy constructor, move constructor, destructor, copy assignment operator, or move assignment operator, its implicit exception-specification specifies the type-id T if and only if T is allowed by the exception-specification of a function directly invoked by f's implicit definition; f allows all exceptions if any function it directly invokes allows all exceptions, and f has the exception-specification noexcept(true) if every function it directly invokes allows no exceptions.

At this point, it's hard to say whether the implicitly generated by icc move constructor should be noexcept or not. Either way, std::map itself was not required to be nothrow-MoveConstructible, so it's more a quality of implementation issue (implementation of the library or implementation of implicit generation of constructors) and icc gets away with it regardless of this being an actual bug or not.

Eventually, std::vector will fall back to using the safer option which is a copy constructor to relocate its elements (maps of unique pointers), but since std::unique_ptr is not CopyConstructible, an error is reported.

On the other hand, std::unique_ptr's move constructor is required to be noexcept, [unique.ptr.single.ctor]:

unique_ptr(unique_ptr&& u) noexcept;

A vector of unique pointers can safely move its elements when relocation is required.

In a newer version of stl_map.h there's the following user-provided definition of map's move constructor:

map(map&& __x)
  noexcept(is_nothrow_copy_constructible<_Compare>::value)
  : _M_t(std::move(__x._M_t)) { }

which explicitly makes noexcept dependent only on whether or not copying a comparator throws.

_{¹ Technically, a copy constructor accepting a non-const l-value reference can change the original object, e.g., std::auto_ptr, but MoveInsertable requires vector elements to be constructible from r-values, that cannot bind to non-const l-value references.}