Когда вы используете std :: unordered_map :: emplace_hint?

Question

Я знаю, как использовать std::unordered_map::emplace, но как я могу использовать emplace_hint? Ни cplusplus, ни cppreference не представляют собой набор примеров, которые иллюстрируют, как мы можем знать, где положить элемент.

Может ли кто-нибудь предоставить некоторую информацию об этом или дать несколько примеров/иллюстраций того, когда мы можем знать, куда должен идти элемент emplaced?

Answer 1

Что может сделать unordered_map с подсказкой? Ну, если итератор обращается к элементу с тем же ключом, что и элемент, который был запрошен вставить emplace_hint, он может быстро сработать - просто сравнение ключей без какого-либо хэширования или поиска в любом списке хеш-сталкивающихся элементов в этом ведре. Но если ключ не совпадает, то подсказка в противном случае бесполезна, потому что любой другой ключ - независимо от того, как «близко» по значению - должен (вероятностно) находиться в полностью несвязанном ведре (учитывая то, что обычно считается «хорошей» хэш-функцией), поэтому время было бы потрачено впустую на ключевое сравнение только для того, чтобы начать, как если бы это был нормальный emplace.

Это может быть полезно, если вы вставляете предварительно отсортированные по ключу элементы, направленные на удаление большого количества дубликатов в процессе, но ключ настолько огромен, что проще сохранить итератор только что вставленному элементу чем копия ключа, или, может быть, хеш-функция особенно медленна.

Еще одно преимущество unordered_map::emplace_hint лучше совместимость API с map::emplace_hint, поэтому код может переключать тип контейнера и имеют emplace_hint ы не нарушить компиляции, хотя они могли бы в конечном итоге медленнее, чем если бы код был переключен на emplace() как близок но разные подсказки, которые помогают с map, могут быть бесполезны с помощью unordered_map.