Code

#include <iostream>
#include <unordered_map>
#include <utility>

using namespace std;

struct Foo {
    Foo(const int value) : val(value) {
        cout << "Foo(int), val: " << val << '\n';
    }
    Foo(Foo & foo) {
        val = foo.val;
        cout << "Foo(Foo &)" << '\n';
    }
    Foo(const Foo & foo) {
        val = foo.val;
        cout << "Foo(const Foo &)" << '\n';
    }
    Foo(Foo && foo) {
        val = foo.val;
        cout << "Foo(Foo &&)" << '\n';
    }
    ~Foo() { cout << "~Foo(), val: " << val << '\n'; }
    Foo& operator=(const Foo& rhs)
    {
        cout << "Foo& operator=(const Foo& rhs), rhs.val: " << rhs.val;
        val = rhs.val;
        return *this;
    }
    bool operator==(const Foo& rhs) const { return val == rhs.val; }
    bool operator<(const Foo& rhs)  const { return val < rhs.val; }

    int val;
};
template<> struct std::hash<Foo> {
    size_t operator()(const Foo& f) const { return hash<int>{}(f.val); }
};

int main()
{
    std::unordered_map<Foo, int> mp;
    mp.insert(std::pair<Foo, int>{1, 50});
    std::cout << '\n';
    mp.insert(std::pair<const Foo, int>{2, 60});
    std::cout << '\n';

    std::cout << "exiting main()\n";
}

Output

Foo(int), val: 1
Foo(Foo &&)
~Foo(), val: 1

Foo(int), val: 2
Foo(const Foo &)
~Foo(), val: 2

exiting main()
~Foo(), val: 1
~Foo(), val: 2

Question #1

Why does mp.insert(std::pair<Foo, int>{1, 50}) compile? Does an implicit conversion occur?

Let's break it down as I see it.

1. Foo(int) with val 1 is called when temporary std::pair is created, val 1 is provided to Foo ctor. Foo(int), val: 1 is printed.
2. std::pair<iterator, bool> insert(value_type && value) is called with temporary pair provided as argument. How? The std::unordered_map<Foo, int>::value_type is std::pair<const Foo, int>. Does an implicit conversion from std::unordered_map<Foo, int> to std::unordered_map<const Foo, int> occur here? If so, should the copy ctor be invoked here?
3. key is searched in the map. The key is not found, so the node is allocated and initialized with std::pair{std::move(value)}; ctor. Foo(Foo &&) is printed.
4. Temporary pair object is destructed. ~Foo(), val: 1 is printed.

Question #2

Why Foo's move ctor is called on the first insert and Foo's copy ctor is called on the second insert?

Answer to Question 1

An implicit conversion is performed, but not in the way you expect it. A different overload for the insert() method is used that itself performs the conversion. To be more precise:

1. Correct
2. Incorrect. Instead the overload template<class P> iterator insert(P && value); is called, since the pair is not of the type const value_type & and not value_type &&, or of node_type &&, which are the other possible single-argument overloads here. See the C++ reference for unordered_map::insert() for all overloads.
3. In essence yes.
4. Yes.

Answer to Question 2

The problem is that a move of std::pair<const Foo, int> is only possible if Foo defines a const rvalue move constructor, i.e. Foo(const Foo && other). Since that specific constructor does not exist, the compiler must resort back to the copy constructor of the pair, that's why that one is called.

(Not to say you should define const rvalue move constructors. Unless you absolutely need them in very specific circumstances, I'd avoid them because it makes reasoning about your class more difficult by adding additional complexity.)

General Note

You might also want to take a look at unordered_map::emplace if you want to avoid needless constructor calls.