在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肯定是最快的方法:

• 向量具有复杂度O(1).无需搜索或哈希,您将立即找到您的实例.
• 映射具有复杂度O(log N).地图需要将您的索引与logN其他条目进行比较以查找您的实例.
• Unordered_map具有复杂度O(1),但是计算哈希值的开销很大(尽管对于简单的数字,它不会那么多).但是,std :: unordered_map仍然在一个哈希索引后面放置多个条目,因此它不是比较一个索引,而是必须比较几个(我认为默认情况下它是4).