寻找一种快速初始化和快速查找的数据结构(O(1))

Question

我需要一个数据结构,我想在其中存储有关在操作期间已处理的实例的信息.由于限制,我无法将其存储在实例本身中(例如,因为我可以并行执行操作.

具体的是,我想要存储信息的实例具有唯一的编号,因此我可以使用该唯一编号来存储信息,而不是指向实例的指针.

我的第一个解决方案是使用std::set<Instance *>.每次我处理一个实例时,我都会将它添加到集合中,以便我知道我已经处理了该实例.

• 优点:初始化速度非常快
• 缺点:查找不是O(1),而是O(logN)

我的第二个解决方案是使用a std::vector<bool>(实际上std::vector<byte>因为bool向量具有特定的特化,这使得它比非bool向量慢).实例的唯一编号可以用作向量的索引,并且在向量中只包含true或false以指示我们是否已经处理了实例(幸运的是,我的唯一编号从1开始计数).

• 优点:查找是O(1)
• 缺点:初始化如果相对较慢,因为std :: vector需要显式初始化每个元素(也可能是独立的)

我也可以使用C风格的数组(我可以在其上使用memset),但由于事先的数量(或唯一数字的数量)是未知的,我需要编写自己的代码来扩展数组,memset数组的其余部分,......(这不是很难,但这是我想要避免的).

是否还有其他类型的数据结构,初始化速度非常快,并且具有O(1)查找时间？

Answer 1

您可以尝试boost::unordered_set或新的C++ 11 std::unordered_set.它们是基于散列的容器,而不是像std :: set这样的树.

Answer 2

好吧,有了这么简单的识别方法......我会使用哈希表.

你不能使用boost::unordered_map或std::unordered_map？

当然,如果你想要保证O(1)插入而不是分摊的O(1)插入,你可能更喜欢更复杂的实现,但它应该让你开始.