What is the fastest way to change a key of an element inside std::map

I understand the reasons why one can't just do this (rebalancing and stuff):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

But so far the only way (I know about) to change the key is to remove the node from the tree alltogether and then insert the value back with a different key:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

This seems rather inefficient to me for more reasons:

1. Traverses the tree three times (+ balance) instead of twice (+ balance)

2. One more unnecessary copy of the value

3. Unnecessary deallocation and then re-allocation of a node inside of the tree

I find the allocation and deallocation to be the worst from those three. Am I missing something or is there a more efficient way to do that?

I think, in theory, it should be possible, so I don't think changing for a different data structure is justified. Here is the pseudo algorithm I have in mind:

1. Find the node in the tree whose key I want to change.

2. Detach if from the tree (don't deallocate)

3. Rebalance

4. Change the key inside the detached node

5. Insert the node back into the tree

6. Rebalance

In C++17, the new map::extract function lets you change the key.
Example:

std::map<int, std::string> m{ {10, "potato"}, {1, "banana"} };
auto nodeHandler = m.extract(10);
nodeHandler.key() = 2;
m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }

I proposed your algorithm for the associative containers about 18 months ago here:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839

Look for the comment marked: [ 2009-09-19 Howard adds: ].

At the time, we were too close to FDIS to consider this change. However I think it very useful (and you apparently agree), and I would like to get it in to TR2. Perhaps you could help by finding and notifying your C++ National Body representative that this is a feature you would like to see.

Update

It is not certain, but I think there is a good chance we will see this feature in C++17! :-)

You can omit the copying of value;

const int oldKey = 33;
const int newKey = 22;
const iterator it = m.find(oldKey);
if (it != m.end()) {
  // Swap value from oldKey to newKey, note that a default constructed value 
  // is created by operator[] if 'm' does not contain newKey.
  std::swap(m[newKey], it->second);
  // Erase old key-value from map
  m.erase(it);
}