我不熟悉 C++ 中的工具。如果这个问题听起来很垃圾，请原谅我。
来自doc map.find() 的复杂度为 O(log(N))。这似乎暗示了实现中的树结构。
来自doc unordered_map.find() 的平均复杂度是恒定的，而最坏情况是 O(N)。这看起来像一个哈希表。
我正在寻找一种 map ，它可以让我:
- 预分配内存，即我确切地知道有多少项目将进入 map
- 当在 map 中找不到大量查询时，具有良好的性能，我知道这会在我的用例中发生
unordered_map 通过 unordered_map.rehash 满足 (1)，但未找到的查询可能需要很长时间。 map 似乎对于未找到的查询具有更好的性能，但没有预分配内存功能。有什么建议吗？
最佳答案
拥有单个固定数量的项目往往意味着您将插入一些特定的项目，然后将它们保留在集合中，直到您完成为止。
如果是这样的话，我可能会将这些项目放入 std::vector 中并对它们进行排序。然后，如果分布可以合理预测，则使用插值搜索，否则使用二分搜索。
只要您不必插入/删除更多项目并保留顺序，即使您使用二分搜索，这通常也比树快得多，因为数据是连续的。
考虑到您预计搜索中会有相当多的失误，我会考虑将哈希表 (unordered_map) 设置为极低的负载因子，以便在绝大多数情况下，您将对键进行哈希处理，如果不存在，您很有可能会遇到一个空的哈希桶，因此您会得到一个指示，表明搜索很快就失败了。您可以使用 max_load_factor() 设置负载系数。
关于C++:预计会出现很多失误:map 与 unordered_map，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34192113/