std::map : update key when using custom operator

When using a custom operator for std::map<KeyType,ValueType,Comparator>, which by design only compares some of my KeyType's fields, it is possible that two objects KeyType k1, k2 contain different data but for the map they look like the same key. After all, this is the reason why we wrote our custom Comparator in the first place.

So if I write

map[k1] = 1;
map[k2] = 2;

with k1 and k2 such that the comparator reports them as being equal, the map will contain the key/value pair {k1, 2}.

What is the most elegant way to replace the pair {k1, 1} by {k2, 2} or is the only way to erase k1 first and then insert k2?