c++ - 在 C++ 中通过 int id 跟踪少量结构类型的有效方法是什么？

Question

我有大约 70-150 个不同的结构 X，它们带有一个无符号整数 ID 字段。它们在程序初始化时被读入并初始化，此后永远不会被修改。在以下(或其他一些方法？)中访问它们的最快方法是什么(这种情况经常发生？):

1. 使用 std::vector v；其中 v[X.id] = X；通过 X& x = v[id]; 访问(这应该在开始时进行复制，但稍后仅在本质上是平面数组上按 id 进行查找。

2. 同上但 std::vector v; X* x = v[id];我对这个很谨慎，因为它有一个额外的间接级别。

3. std::map - 与上面相比感觉有点矫枉过正？

4. 与上面相同，但 unordered_map - 再次出现 70-150 次可能甚至不会超过建议 3。

5. 还有什么更聪明的吗？我看到 1 的一个问题是它的访问模式可能有点稀疏，但不确定如何解决这个问题(如果这是最快的方法)。

Answer 1

使用 vector 绝对是最快的方法:

• vector 的复杂度为 O(1)。无需搜索或散列，您将立即找到您的实例。
• map 的复杂度为 O(log N)。该 map 需要将您的索引与 logN 个其他条目进行比较以找到您的实例。
• Unordered_map 的复杂度为 O(1)，但计算散列值的开销相当大(尽管对于简单数字来说不会那么多)。然而，std::unordered_map 仍然将多个条目放在一个哈希索引后面，因此它必须比较多个索引而不是比较一个索引(我认为默认情况下是 4 个)。