In case of unordered_map we define the hash and pred functors whenever we are using user-defined keys.
The template syntax for a map is as follows:
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_type
> class map;
In case of map there is no hash and pred functors option. Do we never have collisions in case of map. If collisions happen then why don't we have the hash and pred functors as in unordered_map?
Am I missing something here?
std::map and std::unordered_map are two different types of containers that both provided key-value pair mapping. How they do that though is completely different.
std::map uses a tree structure for its implementation. Typically this is an RBTree but any tree that can guarantee worst case O(logN) operations will work. This means it only needs to have a comparison operator for the key type since you can get total ordering and check for equality with a comparator that implements a strict weak ordering. This means you'll never have a hash collision since you aren't using a hash.
std::unordered_map is based on a hash table implementation. Since it hashes the key, you need a hash operator. You also need a comparison operator since two values could hash to the same value (hash collision). Without the comparison operator you would not be able to tell if the duplicate hash is really a duplicate item.