查找表/索引到数组的数据类型

Question

假设我有一个班级'小工具'.在我的应用程序中,我创建了许多小部件(用于缓存局部性和其他原因)我保存在向量中.

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

using LookupTable = std::vector<?>

我看到以下选项:

• 引用(小部件&,或者更确切地说,它必须是可分配的:reference_wrapper <Widget>)
• 指针(小工具*)
• Widget向量中的索引(size_t)
• Iterator对象指向Widget向量(std :: vector <Widget> :: iterator)

在这些选项中,索引似乎是不会被向量调整大小无效的唯一选项.我可能实际上可以避免调整大小,但是,实现查找表就像这意味着对矢量实现进行假设,从"解耦设计"的角度来看这似乎是不合理的.

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

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

前者更具描述性.

总结:我可以将哪种数据类型用于查找表,以实现与向量实现和类型安全性的分离？

Answer 1

您可以创建一个表示索引的类，该索引还携带类型信息（在编译时）。

#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
}