c++ - 查找表/数组索引的数据类型

Question

假设我有一个“Widget”类。在我的应用程序中，我创建了很多小部件(出于缓存位置和其他原因)我将它们保存在一个 vector 中。

为了高效查找，我想实现一个索引数据结构。为了这个问题，我们假设它是一个简单的查找表，从 int 索引到上述 vector 中的 Widget 元素。 我的问题是:查找表的内容应该是什么。 换句话说，我应该用哪种类型来替换

中的问号？

using LookupTable = std::vector<?>

我看到以下选项:

• 引用(Widget&，或者更确切地说，因为它必须是可分配的:reference_wrapper)
• 指针(小部件*)
• Widget vector 中的索引 (size_t)
• 指向 Widget vector 的迭代器对象 (std::vector::iterator)

在这些选项中，索引似乎是唯一不会因 vector 调整大小而失效的选项。我实际上可能能够避免调整大小，但是，像这样实现查找表意味着对 vector 实现做出假设，从“解耦设计”的角度来看这似乎是不合理的。

OTOH 索引不是类型安全的:如果我从查找表中得到的是一个引用，我只能用它来访问相应的小部件。使用 size_t 值我可以做无意义的操作，比如将结果乘以 3。还要考虑以下两个签名:

void doSomethingWithLookupResult(Widget& lookupResult);
void doSomethingWithLookupResult(size_t lookupResult);

前者更具描述性。

总结:我的查找表可以使用哪种数据类型来实现与 vector 实现的解耦和类型安全？

Answer 1

使用 std::vector::size_type(不是 size_t)。 std::vector::size_type 在大多数实现中可能是 size_t，但为了可移植性和面向 future 的考虑，我们会做对的。

继续做一个typedef: 使用 WidgetIndex = std::vector::size_type;

所以这看起来很合理:

void doSomethingWithLookupResult(WidgetIndex lookupResult);

这避免了 vector 调整大小问题，当您在问题中淡化它时，最终会回来咬你。

不要玩一些用户定义类型的游戏，例如 tohava(非常聪明)建议，除非您计划在您的代码库中大量使用这个习语。原因如下:

• 您正在解决的问题(类型安全)是真实存在的，如果它是“免费的”，我们希望有一个解决方案，但与 C++ 程序员不得不搬起石头砸自己的脚的其他机会相比，这不是这不是什么大问题。
• 你会浪费时间。您设计类的时间，然后是您的代码库的每个用户(包括您在几个月内忘记了实现之后)的时间，他们将盯着该代码并不得不弄清楚它。
• 在未来的某个时刻，您将被“有趣”的角落案例绊倒，现在我们都无法通过盯着这段代码看到它。

总而言之，如果您打算在您的代码库中经常使用这个习惯用法(您有许多类存储在非常静态的 vector 或数组中)，那么进行这项投资可能是有意义的。在那种情况下，维护负担会分散到更多代码上，并且使用错误容器的错误索引类型的可能性更大。