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