title: What is the fastest way to change a key of an element inside std::map
body: <p>I understand the reasons why one can't just do this (rebalancing and stuff):</p>
  <pre><code>iterator i = m.find(33);
  
  if (i != m.end())
    i-&gt;first = 22;
  </code></pre>
  <p>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:</p>
  <pre><code>iterator i = m.find(33);
  
  if (i != m.end())
  {
    value = i-&gt;second;
    m.erase(i);
    m[22] = value;
  }
  </code></pre>
  <p>This seems rather inefficient to me for more reasons:</p>
  <ol>
  <li><p>Traverses the tree three times (+ balance) instead of twice (+ balance)</p>
  </li>
  <li><p>One more unnecessary copy of the value</p>
  </li>
  <li><p>Unnecessary deallocation and then re-allocation of a node inside of the tree</p>
  </li>
  </ol>
  <p>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?</p>
  <p>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:</p>
  <ol>
  <li><p>Find the node in the tree whose key I want to change.</p>
  </li>
  <li><p>Detach if from the tree (don't deallocate)</p>
  </li>
  <li><p>Rebalance</p>
  </li>
  <li><p>Change the key inside the detached node</p>
  </li>
  <li><p>Insert the node back into the tree</p>
  </li>
  <li><p>Rebalance</p>
  </li>
  </ol>