使用提示的方式插入std::unordered_map

Question

std::map有一个insert方法，它需要一个“提示”迭代器，如果这个提示正确的话，插入时间将从log(n)降低到常数时间。显然这是如何工作的，因为容器可以确保新添加的项具有小于提示的键，并且具有大于提示前一项的键。否则，提示是错误的并进行常规插入。

std::unordered_map也有类似的带提示的insert函数。什么是提示所起的作用呢？我不明白如何使用“提示”迭代器来加速哈希表的插入。

如果使用它，应该选择什么样的"提示"。在std::map中，通常通过对映射调用lower_bound来找到提示。

- default

---

我认为提示超载仅是为了与普通的 std::map 进行接口兼容，因为如果要执行任何有用的操作，您必须确切地知道要插入值的哈希位置 - 这意味着您需要考虑负载、桶等因素，基本上重新实现了 unordered_map 内部的功能。另外，正如您所指出的，插入已经是摊销 O(1)。 - Xeo

那么明确一点，你的意思是它什么也不做？这正是我猜测的...它只是为了兼容性。 - default

Answer 1

这是一个界面兼容性问题。基本上，设计是考虑到 std::map 的接口。

换句话说，对于 std::unordered_map，无论是否提供提示，都没有区别。

以下是评论区的额外信息：

接口兼容性非常重要，因为能够快速轻松地在 map 和 unordered_map 之间切换，提供了宝贵的灵活性，使得过渡变得毫不费力，因为性能往往是选择其中一种的决定性因素。

- meyumer

---

+1 是的，接口兼容性对于泛型代码非常重要（例如，当容器作为模板参数时：“template <class Map>”）。能够快速轻松地在“map”和“unordered_map”之间进行切换非常重要，因为性能通常是选择其中一个的决定性因素。 - Howard Hinnant

正如 OP 所述，提示通常通过调用 map::lower_bound() 方法获得，而 unordered_map 没有此方法（因为对于无序容器来说是没有意义的）。这是否意味着仍未提供接口兼容性呢？ - Andriy Tylychko

@AndyT：接口兼容性有明显的限制。但是，find和equal_range是两个API中都可以找到的其他丰富的迭代器资源。如果来回切换很重要，那么您应该坚持使用公共API子集。委员会已经尽其所能使子集尽可能大，例如允许在插入unordered_map时提供无用的提示。 - Howard Hinnant

@HowardHinnant：难道清晰度不应该比方便性更重要吗？在这种情况下，方便性很小，因为它只是为您提供了一个更兼容的接口。我相信，那些试图理解如何使用提示参数的困惑人们所花费的时间比真正需要在map和unordered_map之间切换的人节省的时间更多。当然，这是我的主观看法。 - Andriy Tylychko

@AndyT：这对你来说总是一个选择：http://cplusplus.github.io/LWG/lwg-active.html#submit_issue - Howard Hinnant

Answer 2

提示允许unordered map实现先进行值比较来查看提示是否有效。这样可以避免进行哈希函数运算，因为后者可能比比较操作更加耗时。

- steviekm3

---

你能举个例子说明这是如何工作的吗？比如，你如何找到一个提示并将其插入到地图中？ - default

我认为这里的重点是，如果提示指向正确的项...也就是说，键已经在unordered_map中，那么插入操作将会看到这一点（通过将提示处的值与传入值进行比较），并且不需要计算哈希。如果键不在unordered_map中，在这种情况下似乎没有任何改进。 - D. A.

在我使用std::map中遇到的典型用例中，只有在你已经知道该项不在映射中时（因为你首先搜索并发现它不在那里，但知道它应该在哪里（使用lower_bound）），才会使用提示调用插入。因此，如果这种对unordered_map的提示使用是真实的话，似乎没有实际价值。 - default

现有的标准库实现是否会这样做？ - underscore_d