c - c 中用于快速查找/插入/删除整数的数据结构(来自已知的有限域)

Question

我正在用 c 编写一个基于手机的游戏。我对支持快速(如果可能的话分摊 O(1))插入、查找和删除的数据结构很感兴趣。数据结构将存储域 [0, n] 中的整数，其中 n 是提前已知的(它是一个常数)并且 n 相对较小(大约 100000)。

到目前为止，我已经考虑了一个整数数组，其中设置了“第 ith”位当且仅当“第 ith”整数包含在集合中(因此 a[0] 是从 0 到 31 的整数，a[1] 是整数32 到 63 等)。

在 c 中有更简单的方法吗？

Answer 1

您的想法简单而高效 - 假设您有 100000/8 = 12.5 KB 可以玩，那么我认为寻找其他解决方案没有任何意义。