имаю причины, почему нельзя просто сделать это (ребалансировка и прочее):

iterator i = m.find(33);

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

Но пока единственный способ (я знаю о) изменить ключ - это полностью удалить узел из дерева, а затем вставить значение обратно с другим ключом:

iterator i = m.find(33);

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

Это кажется мне неэффективным по нескольким причинам:

обходит дерево три раза (+ баланс) вместо двух (+ баланс)еще одна ненужная копия значенияненужное освобождение, а затем перераспределение узла внутри дерева

Я считаю, что распределение и освобождение являются худшими из этих трех. Я что-то упустил или есть более эффективный способ сделать это?

ОБНОВЛЕНИЕ: Я думаю, в теории, это должно быть возможно, поэтому я не думаю, что изменение для другой структуры данных является оправданным. Вот псевдоалгоритм, который я имею в виду:

найти узел в дереве, ключ которого я хочу изменить.отсоединить, если от дерева (не освобождать)восстановить равновесиеизменить ключ внутри отдельного узлавставить узел обратно в деревовосстановить равновесие