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

Question

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

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

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

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

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

• 优点:查找的复杂度为 O(1)
• 缺点:初始化速度相对较慢，因为 std::vector 需要显式初始化每个元素(也可能独立地初始化)

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

是否有任何其他类型的数据结构可以非常快速地初始化，并且具有 O(1) 查找时间？

Answer 1

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