Я понимаю причины, по которым нельзя просто сделать это (перебалансировка и прочее):
iterator i = m.find(33);
if (i != m.end())
i->first = 22;
Но пока единственный способ (я знаю) изменить ключ - удалить node из дерева alltogether, а затем вставить значение обратно с помощью другого ключа:
iterator i = m.find(33);
if (i != m.end())
{
value = i->second;
m.erase(i);
m[22] = value;
}
Это кажется мне неэффективным по нескольким причинам:
- пересекает дерево три раза (+ баланс) вместо двух (+ баланс)
- еще одна ненужная копия значения
- ненужное освобождение, а затем перераспределение node внутри дерева
Я считаю, что распределение и освобождение являются худшими из этих трех. Я что-то упустил или есть более эффективный способ сделать это?
UPDATE: Я думаю, что теоретически это должно быть возможно, поэтому я не думаю, что изменение для другой структуры данных оправдано. Вот псевдо-алгоритм, который я имею в виду:
- найдите node в дереве, чей ключ я хочу изменить.
- отсоединить, если из дерева (не освобождать)
- ребаланс
- измените ключ внутри отсоединенного node
- вставьте node обратно в дерево
- ребаланс