Краткий ответ

Следует применить узловой дескриптор: извлечь элемент через std::map::extract, изменить ключ через node_handle::key(), а затем вернуть узел методом insert. Элемент временно покидает контейнер, поэтому его ключ можно изменить без нарушения инварианта упорядоченности и без создания новой пары «ключ — значение».

Исторический контекст

В обычном std::map ключ элемента доступен через итератор как константный: его непосредственное изменение могло бы нарушить порядок дерева. До появления узловых дескрипторов изменение ключа обычно требовало удалить элемент и создать новый, что усложняло перенос значения и могло приводить к дополнительному выделению памяти.

В C++17 появились узловые дескрипторы для ассоциативных контейнеров. Они позволяют временно владеть внутренним узлом контейнера, изменять его допустимые свойства и переносить узел между совместимыми контейнерами.

Постановка проблемы

std::map поддерживает элементы в порядке, заданном компаратором ключей. Если изменить ключ непосредственно внутри дерева, позиция элемента может перестать соответствовать этому порядку, поэтому такой ключ намеренно недоступен для обычной записи.

Удаление с последующей вставкой решает проблему, но может потребовать копирования или перемещения отображаемого значения. Кроме того, при вставке нового элемента возможен отказ из-за уже существующего ключа, что нужно корректно обработать.

Подробное решение

extract отсоединяет узел от дерева и возвращает объект типа std::map<...>::node_type. Пока узел находится в дескрипторе, он не является частью контейнера, поэтому изменение ключа безопасно.

#include <map>
#include <string>
#include <utility>

int main() {
    std::map<int, std::string> m;
    m.emplace(1, "payload");

    auto node = m.extract(1);
    node.key() = 2;
    auto result = m.insert(std::move(node));
}

Извлечение по итератору имеет амортизированную константную сложность, а поиск узла по ключу — логарифмическую. Повторная вставка в std::map требует поиска позиции и обычно имеет логарифмическую сложность. Само значение узла при успешном переносе сохраняется; контейнер не обязан создавать новый узел для него.

Если новый ключ уже существует, вставка в std::map не выполняется. Возвращаемый результат содержит непринятый узловой дескриптор, поэтому элемент можно обработать, вернуть под прежним ключом или перенести в другой совместимый контейнер.

Во время извлечения итератор на этот элемент становится недействительным. Итераторы на остальные элементы std::map сохраняют действительность. До повторной вставки узел находится отдельно от контейнера и должен оставаться под управлением узлового дескриптора.

Ситуация из практики

В конфигурационном хранилище записи индексируются числовым идентификатором, но один идентификатор нужно заменить, сохранив большое строковое содержимое и связанные ресурсы.

Вариант с копированием значения прост, но может быть дорогим для крупных объектов. Вариант с удалением и созданием новой записи универсален, однако усложняет обработку исключений и может вызвать лишние операции с памятью.

Выбран extract с изменением ключа и последующей вставкой. Такой подход сохраняет узел и его отображаемое значение, явно обрабатывает конфликт нового ключа и сохраняет инвариант упорядоченного дерева. Если конфликт обнаружен, непринятый узел не теряется.

Что кандидаты часто упускают

Что произойдёт, если изменённый ключ уже присутствует в std::map?

Вставка завершится неудачно, поскольку std::map допускает только уникальные ключи. Результат вставки содержит итератор на конфликтующий элемент и сам непринятый узловой дескриптор. Узел можно не уничтожать: его разрешается повторно вставить, изменить ключ ещё раз или перенести в другой подходящий контейнер.
Какие итераторы сохраняют действительность после extract?

Итератор, указывавший на извлечённый элемент, недействителен. Итераторы на остальные элементы std::map сохраняются, потому что извлечение удаляет только один узел и не требует перестройки остальных элементов. После повторной вставки старый итератор всё равно нельзя использовать: нужно получить новый итератор из результата вставки или найти элемент заново.
Почему извлечение по итератору быстрее извлечения по ключу?

При извлечении по итератору контейнер уже знает расположение узла, поэтому поиск ключа не нужен; операция имеет амортизированную константную сложность. При извлечении по ключу сначала выполняется поиск в упорядоченном дереве, поэтому сложность составляет O(log N). Если узел затем вставляется обратно с новым ключом, поиск новой позиции всё равно требует логарифмического времени.