I've ran into a case where set::find is not the correct way to find the object because I'm finding the object in a different way (by std::find_if) than it is ordered in the set. I have not found any complexity information on finding elements this way. I assume it's linear because iterating through a "unordered" container to find a match is linear.
You can look here and see that the complexity of find_if is linear.
It is because find_if is a generalized algorithm and it doesn't know a certain type of container it works with. So it can't use peculiarities of different containers to boost a search process and just checks all the elements to find the appropriate one.