In this article we will discuss how to use std::unordered_set custom hasher and comparision function.

Unordered_set uses the Hash table implementation to provide the set functionality. To know more about Hash Table visit the following article,

What is Hashing and Hash Table?

Whenever we insert an element in unordered_set two things happen i.e.

  • It calls the hasher function on passed element and compute the hash code. Now on the basis of this hash code it selects the appropriate bucket for the element.
  • Then compares the passed element with all the elements in the bucket to check if any similar element is already present. If not then it stores the element in that bucket.

Therefore, If two elements are equal then there hashcode should always be same. Otherwise it will impossible to search for correct element in unordered_set.

While declaring an unordered_set we provides the type of element that can be stored in set. Along with that we can also provide the type of custom hasher and comparison functions.

Now, suppose our unordered_set is of type T and didn’t supplied any default custom hasher function and comparison function. Then in that case default hasher andcomparison function will be used i.e.

  • std::hash<T>()
  • std::equal_to<T>

For example, if create a unordered_set of std::string i.e.

Above unordered_set uses the default hasher and comparison function and it is equivalent to,

std::hash calculates the hash of primitive data types and std::equals_to internally calls == function on the passed elements for comparison. Let’s see an example of  custom hasher and comparision function.

Custom Hasher and Comparator for unordered_set of unique length strings

Suppose, we want to create an std::unordered_set of std::string and want to store strings of unique lengths only. As, the default equals_to<>() function uses the == operator to compare the elements. But in our scenario we want to compare elements based on length i.e. two elements should be considered equal if they have the same length. For that we need to create our custom Comparison Function i.e.

Custom Compare Function

If two elements are equal according to the comparision function then their hash code should be same. In our scenario above comparator is comparing two elements based on length. So, we can’t use default std::hash<std::string>() function because that will compute the hash code on complete object instead of length.

 

For example, according to above compare function “abc” and “def” are equal because their length is same. But their hash code can be different if computed with default std::hash<std::string>. Therefore, we need custom hasher function, so that elements which are equal based on above compare function should have same hash code.

Custom hasher

Declaring unordered_set with custom hasher and compare function,

Let’s see the complete example as follows,

Output:

 

Click Here to Subscribe for more Articles / Tutorials like this.