c++ - 将代码从 map 重构为 vector

Question

其实问题出在标题上。我有一个工作代码，我大量使用 std::map<char, T> table . Profiler 告诉我 operator[]方法相当耗时。所以我认为由于 char 只有几个不同的值(我想是从 -128 到 127)，所以可以更改我的 table 的类型。变量为 std::vector<T>甚至 T[256] .我的问题是如何安全地做到这一点。我的意思是我不能相信 char type 恰好有 256 个不同的值，所以我想添加一些可移植的代码，这些代码将使用 std::numeric_limits 之类的东西，并确保 table大小涵盖 char 的所有可能值.另一个问题是我在使用 std::map 时并不关心负值。 .但我不能对 std::vector 做同样的事情因为table[(char)-15]会产生异常。这是否意味着最简单的解决方案是从 char 转换所有 key 至 unsigned char打电话前 operator[]我的table ？如果没有，我应该怎么做？

Answer 1

我建议切换到 std::unordered_map<char, T> .

对于 std::unordered_map operator[] 的复杂性表示为近似值 O(1)

Average case: constant, worst case: linear in size.

对于 std::map operator[] 的复杂性是O(logN)

Logarithmic in the size of the container.