假设我有一个图中的顶点列表。该列表对应于图中的路径，在添加另一个顶点之前，我需要检查它是否已存在于路径中。
我正在考虑将所有顶点添加到无序集中，然后使用查找函数。该文档指出，它在平均情况下以恒定时间运行。在这种情况下它仍然会以恒定的时间运行吗？
如果没有，有没有办法存储顶点列表并在恒定时间内查找列表中是否存在顶点？
最佳答案
无论您在其中存储什么数据，std::unordered_set 类型都期望进行 O(1) 次查找，所以是的，在这种情况下，您应该期望看到查找花费 O(1) 时间.
一个可能的警告:这里的 O(1) 指的是相等比较和计算的哈希值的数量。如果比较两个节点是否相等需要不同的时间，或者如果您的哈希函数需要不同的时间，那么总成本可能会超过 O(1)。
另一个可能的警告:预期的 O(1) 运行时间假设您有一个“好的”哈希函数。如果您编写了自己的自定义哈希函数并且它是一个“弱”哈希函数，那么由于哈希冲突，运行时间可能会超过 O(1)。
关于c++ - C++ 中的 unordered_set 会在恒定时间内找到该数据中的值吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/71411946/