Unordered Map

According to the documentation, the average searching complexity is O(1), by looking more into unordered_map.find()

It is redirected to lower_bound, passing in the original key value

For _Traits, it’s the template operators (open hashing I supposed), for the iterator defined within the _Traits class