std::map имеет метод insert, который принимает итератор "подсказки", который сокращает время вставки от log (n) до постоянного времени, если подсказка верна. Его довольно очевидно, как это будет работать, поскольку контейнер может просто убедиться, что у недавно добавленного элемента есть ключ, который меньше подсказки и имеет ключ, который больше, чем элемент перед подсказкой. В противном случае подсказка была неправильной, и она выполняет обычную вставку.
std::unordered_map также имеет аналогичную insert с функцией подсказки. Что, если что-нибудь, делает намек? Для меня не очевидно, как другой итератор "подсказки" можно было бы использовать для ускорения ввода хэш-карты.
Если он используется, что является подходящим "подсказкой". В std::map подсказка обычно находится путем вызова lower_bound на карте.
