The keys must still be copyable, because we store two copies of them.
Do you want to static_assert on random_access_iterator_tag in the class?
This O(n) behavior is unfortunate. It could have been O(1), by swapping the to-be-erased element with back(), then pop_back().
Just a comment, no change required. :)
I think that should be a separate change -- it's the same as the other insert() function.
Except that wouldn't preserve order.