c - 将变量 ID 与值一起存储的有效方法是什么？

Question

我希望将我的数据存储在允许我有效地执行以下操作的数据结构中：

我有 10 个类型为 1 的数组和 10 个类型为 2 的数组，每个数组有 100 个元素。这些数组中的每一个都存储 100 个变量的值。伴随着这些，我有 20 个包含相应变量 ID 的数组。类型 1 的数组总共存储 1000 个变量的值，类型 2 的数组存储相同 1000 个变量的不同值。

现在，我需要将类型 1 数组中的变量值与类型 2 数组中的变量值进行区分。让 A 成为类型 1 数组中的一个。问题是 A 中的变量每个会分布 10跨越所有 10 个类型 2 的数组。

哈希映射没有用，因为我还需要遍历每个数组中的值。有任何想法吗？

Answer 1

如果您打算经常执行此类操作，您可能希望在程序启动时构造和索引一次（构造具有O(n^2)时间复杂度），然后再参考它。

struct LookupEntry {
   A *item1;
   B *item2;
};

std::map< IdType, LookupEntry > index;

这将允许您线性地遍历类型数组并在恒定时间内A从类型数组中获取值。B您也可以以类似的方式B从中减去项目。A

或者，您可以浏览索引项目并从另一个项目中减去一个项目。