c++ 中的 unordered_set 会在恒定时间内找到此数据中的值吗？
Would an unordered_set in c++ find the values in this data in constant time?
假设我有一个图中的顶点列表。此列表对应于图中的路径，在添加另一个顶点之前，我需要检查它是否已存在于路径中。
我正在考虑将所有顶点添加到一个无序集合中，然后使用查找函数。文档指出，在一般情况下，它在恒定时间内 运行s。在这种情况下，它还会 运行 在恒定时间内吗？
如果没有，有没有办法存储一个顶点列表，并在恒定时间内查找列表中是否存在某个顶点？
无论您在其中存储什么数据，std::unordered_set 类型都需要 O(1) 次查找，所以是的，在这种情况下，您应该期望看到查找花费时间 O(1)。
一个可能的警告：这里的 O(1) 指的是相等比较和哈希计算的次数。如果比较两个节点的相等性需要可变的时间，或者如果您的哈希函数需要可变的时间，那么总成本可能超过 O(1)。
另一个可能的警告：预期的 O(1) 运行时间假设您有一个“好的”哈希函数。如果您编写了自己的自定义哈希函数并且它是一个“弱”哈希函数，那么由于哈希冲突，运行时间可能会超过 O(1)。
假设我有一个图中的顶点列表。此列表对应于图中的路径，在添加另一个顶点之前，我需要检查它是否已存在于路径中。
我正在考虑将所有顶点添加到一个无序集合中，然后使用查找函数。文档指出，在一般情况下，它在恒定时间内 运行s。在这种情况下，它还会 运行 在恒定时间内吗？
如果没有，有没有办法存储一个顶点列表，并在恒定时间内查找列表中是否存在某个顶点？
无论您在其中存储什么数据，std::unordered_set 类型都需要 O(1) 次查找，所以是的，在这种情况下，您应该期望看到查找花费时间 O(1)。
一个可能的警告：这里的 O(1) 指的是相等比较和哈希计算的次数。如果比较两个节点的相等性需要可变的时间，或者如果您的哈希函数需要可变的时间，那么总成本可能超过 O(1)。
另一个可能的警告：预期的 O(1) 运行时间假设您有一个“好的”哈希函数。如果您编写了自己的自定义哈希函数并且它是一个“弱”哈希函数，那么由于哈希冲突，运行时间可能会超过 O(1)。