[ 2011-10-02 Daniel comments and refines the proposed wording ]

Unfortunately the template constraints expressed as "P is implicitly convertible to value_type" reject the intended effect to support move-only key types, which was the original intention when the library became move-enabled through the rvalue-reference proposals by Howard (This can clearly be deduced from existing carefully selected wording that emphasizes that CopyConstructible is only required for special situations involving lvalues or const rvalues as arguments). The root of the problem is based on current core rules, where an "implicitly converted" value has copy-initialization semantics. Consider a move-only key type KM, some mapped type T, and a source value p of type P equal to std::pair<KM, T>, this is equivalent to:

std::pair<const KM, T> dest = std::move(p);

Now [dcl.init] p16 b6 sb2 says that the effects of this heterogeneous copy-initialization (p has a different type than dest) are as-if a temporary of the target type std::pair<const KM, T> is produced from the rvalue p of type P (which is fine), and this temporary is used to initialize dest. This second step cannot succeed, because we cannot move from const KM to const KM. This means that std::is_convertible<P, std::pair<const KM, T>>::value is false.

But the actual code that is required (with the default allocator) is simply a direct-initialization from P to value_type, so imposing an implicit conversion is more than necessary. Therefore I strongly recommend to reduce the "overload participation" constraint to std::is_constructible<std::pair<const KM, T>, P>::value instead. This change is the only change that has been performed to the previous proposed wording from Pablo shown below.