在数组中查找 table/index 的数据类型

Question

假设我有一个 class 'Widget'。在我的应用程序中，我创建了很多小部件（出于缓存位置和其他原因）我将它们保存在一个向量中。

为了高效查找，我想实现一个索引数据结构。为了这个问题，我们假设它是从 int 索引到上述向量中的 Widget 元素的简单查找 table。我的问题是：查找 table 的内容应该是什么。换句话说，

中的问号应该换成哪种类型

using LookupTable = std::vector<?>

我看到以下选项：

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

在这些选项中，索引似乎是唯一不会因向量调整大小而失效的选项。我实际上可以避免调整大小，但是，像这样实现查找 table 意味着对矢量实现做出假设，从 'decoupled design' 的角度来看这似乎是不合理的。

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

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

前者更具描述性。

总结：我可以使用哪种数据类型进行查找 table 以实现与向量实现的解耦和类型安全？

Answer 1

您可以创建一个 class 来表示一个索引，该索引也包含类型信息（在编译时）。

#include <vector>

template <class T>
struct typed_index {
    typed_index(int i) : i(i) {}

    template <class CONTAINER>
    T &operator[](CONTAINER &c) { return c[i]; }
    template <class CONTAINER>
    const T &operator[](const CONTAINER &c) { return c[i]; }

    int i;
};

int main() {
    std::vector<int> v1 = {0};
    std::vector<const char *> v2 = {"asd"};
    typed_index<int> i = 3;
    int z = i[v1];
    const char *s = i[v2]; // will fail
}

Answer 2

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

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

所以这看起来很合理：

void doSomethingWithLookupResult(WidgetIndex lookupResult);

这避免了矢量调整大小的问题，当你在问题中轻描淡写时，最终会回来咬你。

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

您要解决的问题（类型安全）是真实存在的，如果它是 "free,"，我们希望有一个解决方案，但与 C++ 程序员不得不搬起石头砸自己脚的其他机会相比，这不是什么大问题。
你会浪费时间。您设计 class 的时间，然后是您的代码库的每个用户（包括您在几个月内忘记了实现之后）的时间，他们将盯着该代码并不得不弄清楚它。
在未来的某个时候，您会被我们 none 中的 none 盯着这段代码看到的那个 "interesting" 角落案例绊倒。

综上所述，如果您打算在代码库中经常使用这个习惯用法（您有许多 classes 存储在非常静态的向量或数组中），那么做这笔投资。在那种情况下，维护负担会分散到更多代码上，并且使用错误容器使用错误索引类型的可能性更大。

在数组中查找 table/index 的数据类型

Datatype for lookup table/index into array

c++

oop

c++11