Eu entendo as razões pelas quais não se pode simplesmente fazer isso (reequilíbrio e outras coisas):

iterator i = m.find(33);

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

Mas até agora a única maneira (que eu conheço) de alterar a chave é remover o nó da árvore completamente e, em seguida, inserir o valor novamente com uma chave diferente:

iterator i = m.find(33);

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

Isto me parece ineficiente por mais razões:

transporta a árvore três vezes (+ saldo) em vez de duas vezes (+ saldo)uma cópia mais desnecessária do valor desalocação desnecessária e, em seguida, realocação de um nó dentro da árvore

Acho que a alocação e desalocação são as piores entre as três. Estou faltando alguma coisa ou existe uma maneira mais eficiente de fazer isso?

UPDATE: Eu acho que, em teoria, deveria ser possível, então não acho que mudar para uma estrutura de dados diferente seja justificada. Aqui está o pseudo algoritmo que tenho em mente:

encontre o nó na árvore cuja chave eu quero alteradetach se da árvore (não desalocar) rebalance mude a chave dentro do nó desanexado insira o nó novamente na árvore rebalance