Подсказка при вставке/размещении нового элемента в unordered_map/unordered_set
Если я вставляю новый элемент (ключ отсутствует) в std::unordered_map, могу ли я повысить производительность с помощью emplace_hint?
И какое значение должна иметь подсказка?
Часто я знаю, что значение ключа (интегрального типа) больше, чем все ключи на карте. Должен ли я тогда использовать cend как подсказку?
Ответы 2
emplace_hint на самом деле не нужен при использовании неупорядоченного контейнера. В отличие от std::map, где у вас есть гарантированный порядок и использование end в качестве подсказки даст вам постоянное размещение, неупорядоченная версия уже имеет постоянное размещение.
Если мы посмотрим на Т а б л и ц а 70 — Требования к неупорядоченному ассоциативному контейнеру (в дополнение к контейнеру), мы получим
Expects:
value_typeis Cpp17EmplaceConstructible intoXfromargs.Effects: Equivalent to
a.emplace( std::forward<Args>(args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. Theconst_iteratorpis a hint pointing to where the search should start. Implementations are permitted to ignore the hint.
и вы можете видеть, что вам даже не гарантируется, что предоставление подсказки что-то сделает.
Линия
The
const_iteratorpis a hint pointing to where the search should start
заставляет меня поверить, что итератор должен быть в начале ведра, в котором будет размещен элемент, поэтому end/cend не будет тем, что вы хотите использовать.
Я провел некоторое тестирование, и из того, что я увидел, похоже, что подсказка была полностью проигнорирована std::unordered_map. Я не мог найти никакого значения для передачи, которое, казалось бы, вообще давало какое-либо преимущество.
Стандарт явно дает реализациям неупорядоченных коллекций игнорировать подсказку, переданную emplace_hint, и я думаю, что большинство (если не все) обычно так и делают. Спецификация на самом деле не говорит, следует ли передавать итератор вставляемому значению (если оно есть) или после него (как в случае с упорядоченными ассоциативными коллекциями). Учитывая, что он основан на хеше, итератор для около правильной точки вставки, вероятно, бесполезен. Таким образом, чтобы иметь какую-либо надежду на какую-либо пользу, он, вероятно, должен быть итератором фактической точки вставки (например, той, которая имеет тот же ключ, что и вы вставляете, если вы пытаетесь вставить дубликат).
Резюме
Я сомневаюсь, что вы можете передать какое-либо значение, которое дает какое-либо значительное преимущество (и при тестировании я не нашел такого).
cendкак подсказку? – гм... это неупорядоченный