Is there some efficient way to change key in unordered multimap? For example, I want to change key from key_val1 to key_val2. It looks like this can be done much efficiently than iterating over equal_range(...) and readding all pairs for the new key with subsequent erasing the old one.
No. If you want to change keys, you have little choice but to delete the existing item, create a new item with the new key, and insert the new item into the set.
An unordered_multi(set|map) is (at least normally) implemented as a hash table. Any change in the key requires computing the hash for the new key (which may be entirely different from the hash for the old key, even though the key is only slightly modified).
Thinking about things, you probably can actually do this if you're ambitious enough. I'm not at all sure it's worthwhile, but it is probably possible. In particular, the unordered associative containers support what are called local iterators. A local iterator can iterate through the items in a specific bucket in the table. By definition, all items with equal keys must be in the same bucket.
So, you'd start by getting a local iterator to the bucket containing your items. Then you'd iterate through that using key_equal to find all the items it contains that have the same key. Then you'd use the hasher to find the new bucket for all of those, and directly move them all to the new bucket.
I've never actually done this, so I'm not certain the local_iterator gives you enough access to do it--but it does seem like it at least might be possible--likely enough to be worth further investigation, anyway.
My own take on things is that if you're likely to do this often enough to bother optimizing the task, it would probably be worth considering using an unordered_map<key, std::vector<whatever>>, so you'd only have one stored key, with an arbitrary number of items associated with it. Then if you need to modify that key, moving all the associated data with it is trivial (happens pretty much automatically).