将代码从 map<char, T> 重构为 vector<T>

Question

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

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.

Answer 2

我建议引入你自己的 class 来使用，它会以某种方式封装 std::vector<T> 并提供你需要的接口。

如果你要重用很多std::vector的接口，你甚至可以考虑使用实现关系：

template <class T>
struct MyMap : protected std::vector<T>
{
  using std::vector::vector;
  using std::vector::push_back;
  // ...
  // List other members which you want to inherit verbatim

  T& operator[] (char idx)
  {
    return std::vector::operator[](idx - std::numeric_limits<char>::min());
  }
  // Re-implement the members which you need to
};

将代码从 map<char, T> 重构为 vector<T>

Refactoring code from map<char, T> to vector<T>

c++

portability

dictionary

vector