When I do unordered_set::find
unordered_set<int> uniqueNum;
//code...
if(uniqueNum.find(num + k) != uniqueNum.end())
//code ...
the runtime of this code is faster than
unordered_set<int> uniqueNum;
//code...
if(find(uniqueNum.begin(), uniqueNum.end(), num + k) != uniqueNum.end())
//code...
According to the reference, unordered_set::find is "Worst case: linear in container size" while find is "Up to linear in the distance between first and last: Compares elements until a match is found".
Are they not the same runtimes? Why is unordered_set::find faster when I run my code? Is std::find doing something behind the hood that I'm missing?
This is due to how they are implemented. std::find operates as you might expect. Start at the beginning and compare each element until it reaches the end. This is fairly universal, but won't benefit from the specific data structure used. However, unordered_set is a hashset so if there are no hash collisions, every element takes the same amount of time to find.
The reason it says there is a "worst case of linear in container size" is because if the hash table were to have a length of 1, every entry would be placed at the same position in the table (pseudocode: table[hash(element) % table_length].push(element)). If this were to happen, then depending on the implementation it could end up looking more like a list in memory and it would have to check every item sequentially. In practice though, this would likely never happen.