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?
The std::unordered_set type 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.