Сложность std :: map :: insert_or_assign с подсказкой

Question

Какова временная сложность std::map::insert или std::map::assign с подсказкой в ​​случае, если элемент уже существует на карте?CPP-Reference говорит, что это то же самое, что и emplace_hint, который говорит:

"амортизированная константа, если новый элемент вставляется непосредственно перед подсказкой"

Но:

1. Что делать, если новый элемент не вставлен?
2. И подсказка должна быть lower_bound или upper_bound?

Answer 1

Если ключ уже существует, то это даже проще, не нужно добавлять новый узел в карту, просто присваивание, и опять же, амортизированный O (1).Слова «непосредственно перед подсказкой» предполагают, что подсказка должна быть немного выше сопоставленной клавиши, то есть upper_bound.