c++ 中的 unordered_set 会吗？在恒定时间内找到该数据中的值？
假设我有一个图中的顶点列表。该列表对应于图中的路径，在添加另一个顶点之前，我需要检查它是否已存在于路径中。
我正在考虑将所有顶点添加到无序集中，然后使用 find 函数。该文档指出，它在平均情况下以恒定时间运行。在这种情况下它仍然会以恒定的时间运行吗？
如果没有，有没有办法存储顶点列表并在恒定时间内查找列表中是否存在顶点？
Suppose I have a list of vertices in a graph. This list corresponds to a path in the graph and before adding another vertex I need to check if it is already present in the path or not.
I was thinking of adding all the vertices in an unordered set and then using the find function. The documentation states that it runs in constant time in an average case. Would it still run in constant time in this case?
If not, is there a way to store a list of vertices and find if a vertex exists in the list or not in constant time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
无论您在其中存储什么数据，
std::unordered_set类型都期望 O(1) 查找，所以是的，在这种情况下，您应该期望看到查找花费 O(1) 时间。一个可能的警告：这里的 O(1) 指的是相等比较和计算的哈希值的数量。如果比较两个节点是否相等需要不同的时间，或者如果您的哈希函数需要不同的时间，则总成本可能会超过 O(1)。
另一个可能的警告：预期的 O(1) 运行时间假设您有一个“好的”哈希函数。如果您编写了自己的自定义哈希函数并且它是一个“弱”哈希函数，则由于哈希冲突，运行时间可能会超过 O(1)。
The
std::unordered_settype has expected O(1) lookups regardless of what data you store in it, so yes, in this case you should expect to see lookups taking time O(1).One possible caveat: the O(1) here refers to the number of equality comparisons and hashes computed. If comparing two nodes for equality takes a variable amount of time, or if your hash function takes a variable amount of time, then the total cost might exceed O(1).
Another possible caveat: the expected O(1) runtime assumes you have a “good” hash function. If you wrote your own custom hash function and it’s a “weak” hash function, then the runtime might exceed O(1) due to hash collisions.