0

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

  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 中看到的一个问题是访问模式可能有点稀疏，但如果这是最快的方法，我不确定如何解决这个问题。

4

3 回答 3

5

使用向量绝对是最快的方法：

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

我认为对于少数项目，没有比使用数组或向量数据类型更快的访问方式，因为它提供了恒定时间访问。在许多对象的情况下，这种方法也是最快的，但也是最昂贵的内存。

于 2012-06-06T17:01:34.460 回答
0

如果您不介意预先为所有结构预先分配空间，并且 ID 可以按顺序排序，因此它们也是索引，只需使用方法 1。

如果结构的构建成本很高，可以通过不将构建代码实际放置在默认构造函数中（稍后通过方法调用显式执行）或使用原始数组并将新数组放置在该数组内的内存“插槽”上来延迟构造.

如果 ID 不是连续的，请使用std::unordered_map以防止在“孔”上浪费空间。

于 2012-06-06T17:07:51.737 回答