c++ - 在 unordered_map 中搜索的最佳实践

Question

我想创建一个 std::unordered_map < int, std::string > 或 std::unordered_map< std::string, int > . 在此映射中，我将存储字符串及其整数表示。 我将仅在代码(硬编码对)中填充此映射。

我需要将输入字符串转换为其 int 值 - 在 map 中查找。 所以我只需要在运行时在 map 中搜索。 在这一点上，我需要在转换时获得最佳性能。 在最好的情况下 - O(1)。

我的问题:

1. 我应该使用 string 作为键还是 int ？
2. 我应该定义自己的哈希函数吗？
3. 对于 string/int 和 int/string 这两种情况，作为键对的最佳性能查找函数是什么？

Answer 1

std::map或 std::unordered_map或者他们的 multi - 对应部分都是相同的 - 它们将键(第一个模板参数)映射到一个值(第二个)。如果您想获得 O(1)(无序)或 O(log(n))(映射)行为，您需要将要为其获取值的数据类型定义为键。

如果您想为给定的字符串找到一个整数值，您的方法是 std::unordered_map<std::string, int> .

一个反例是查找错误代码的名称，您通常有一个函数返回的特定错误代码(或放置在 errno 中)并希望获得 e 的字符串值。 G。用于将错误打印到控制台。 然后你会得到std::unordered_map<int, std::string> (前提是您不能将错误字符串存储在数组中，因为错误代码分布太远...)。

编辑:

定义您自己的哈希函数是 Konstantin 在他的评论中提到的那种过早的优化 - std::string 提供了它自己的哈希代码函数，这应该适合大多数用例。只有当您发现您的散列算法变得太慢时，才尝试寻找更快的方法。

由于您所有的字符串都是硬编码的，您可能想看看完美散列，例如。 G。在gperf变体。