Подсказка при вставке / размещении нового элемента в unordered_map / unordered_set

Question

Если я вставляю новый элемент (ключ отсутствует) в std::unordered_map, могу ли я повысить производительность с emplace_hint? И какое значение должен иметь подсказка?

Часто я знаю, что значение ключа (целочисленного типа) больше, чем все ключи на карте. Должен ли я использовать cend в качестве подсказки тогда?

Answer 1

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

Если мы посмотрим на Таблица 70 - Неупорядоченныйтребования к ассоциативному контейнеру (в дополнение к контейнеру) у нас есть

Ожидается: value_­type является Cpp17EmplaceConstructible в X с args.

Эффекты: Эквивалент a.emplace( std::forward<​Args>(​args)...).Возвращаемое значение - это итератор, указывающий на элемент с ключом, эквивалентным вновь вставленному элементу.const_­iterator p - подсказка, указывающая, где должен начинаться поиск.Реализациям разрешено игнорировать подсказку.

, и вы можете видеть, что вам даже не гарантировано, что предоставление подсказки будет что-либо делать.

Строка

* const_­iterator p - подсказка, указывающая, где должен начинаться поиск

наводит меня на мысль, что итератор должен находиться в начале сегмента, в который будет помещен элемент, поэтомуend / cend не будет тем, что вы хотите использовать.

Answer 2

Я провел некоторое тестирование, и из того, что я увидел, похоже, что подсказка была полностью проигнорирована std::unordered_map. Я не мог найти никакой ценности, чтобы передать это, которое, казалось, обеспечивало какое-либо преимущество вообще.

Стандарт явно дает реализации неупорядоченных коллекций, чтобы игнорировать подсказку, переданную emplace_hint, и я думаю, что большинство (если не все) обычно делают. Спецификация на самом деле не говорит, следует ли вам передавать итератор для вставляемого значения (если оно есть) или для одного после него (как это было бы с упорядоченными ассоциативными коллекциями). Учитывая, что он основан на хэше, итератор для около правильной точки вставки, вероятно, бесполезен. Таким образом, чтобы иметь хоть какую-то надежду, он должен быть итератором к фактической точке вставки (например, тот, который имеет тот же ключ, что и вставляемый вами, если вы пытаетесь вставить дубликат).

Резюме

Я сомневаюсь, что есть какое-то значение, которое вы можете передать, которое дает какое-либо существенное преимущество (а в тестировании я не нашел такого, которое дает).