什么时候使用std :: unordered_map :: emplace_hint？ [英] When do you use std::unordered_map::emplace_hint?

问题描述

我知道如何使用 std :: unordered_map :: emplace ，但是如何使用 emplace_hint ？ cplusplus 或 cppreference 提供了一组示例，说明我们如何知道在哪里放置元素。

I know how to use std::unordered_map::emplace, but how do I use emplace_hint? Neither cplusplus nor cppreference provide a set of examples that illustrate how we might know where to put the element.

任何人都可以提供一些信息

Can anyone provide some information on this or give some examples / illustrations of when we might know where the emplaced element should go?

推荐答案

什么是 unordered_map 潜在地使用提示？好吧，如果迭代器寻址一个与 emplace_hint 要求插入的元素具有相同键值的元素，那么它可能会快速失败 - 只是一个没有任何散列的键比较，探索该桶处的任何哈希冲突元素列表。但是如果密钥不匹配，则提示否则是无用的，因为任何其他密钥 - 无论如何接近值（在概率上）应该在完全不相关的桶（给定通常被认为是好的散列函数），因此时间会浪费在一个关键的比较上，只需要重新开始，就像是一个正常的 emplace 。

What could an unordered_map potentially do with the hint? Well, if the iterator addresses an element with the same key as the element that emplace_hint has been asked to insert, then it can fail quickly - just a key comparison without any hashing or groping through any list of hash-colliding elements at that bucket. But if the key doesn't match, then the hint is otherwise useless because any other key - no matter how "close" in value - should (probabilistically) be at a completely unrelated bucket (given what's normally considered a "good" hash function), so time would have been wasted on a key comparison only to have to start over as if it were a normal emplace.

这可能是有用的，当你插入预排序的关键元素，旨在删除大量的重复的过程，但关键是如此巨大，更容易保持一个迭代器到刚刚插入的元素

This might be useful when you're inserting pre-sorted-by-key elements, aiming to remove lots of duplicates in the process, but the key is so huge it's easier to keep an iterator to the just-inserted element than a copy of the key, or perhaps the hash function is particularly slow.

unordered_map :: emplace_hint 与 map :: emplace_hint 更好的API兼容性，因此代码可以切换容器类型并使 emplace_hint 打破编译，虽然他们可能会结束比如果代码切换到 emplace（）作为close-but-different-key提示帮助一个 map 可能无效与 unordered_map 。

Another benefit of unordered_map::emplace_hint is better API compatibility with map::emplace_hint, so code can switch the container type and have the emplace_hints not break the compile, though they might end up slower than if the code were switched to emplace() as the close-but-different-key hints that help with a map may be useless with an unordered_map.

这篇关于什么时候使用std :: unordered_map :: emplace_hint？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！