我需要一个数据结构，我想在其中存储有关我在操作期间已处理的实例的信息。由于限制，我无法将它存储在实例本身中(例如，因为我可以并行执行操作。
具体的是，我要为其存储信息的实例具有唯一编号，因此我可以使用该唯一编号来存储信息，而不是指向实例的指针。
我的第一个解决方案是使用 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) 查找时间？
最佳答案
您可以尝试 boost::unordered_set 或新的 C++11 std::unordered_set .它们是基于散列的容器，而不是像 std::set 这样的树。
关于c++ - 寻找一种可以快速初始化和快速查找的数据结构 (O(1))，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10349990/