Using unordered_set with custom hasher and comparision function

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.

std::unordered_set<std::string> setOfStrs;

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

std::unordered_set<std::string, std::hash<std::string> , std::equal_to<std::string> > setOfStrs;

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

// Custom comparator that compares the string objects by length
struct StringEqualBySize {
public:
	bool operator()(const std::string & str1, const std::string & str2) const {

		if (str1.length() == str2.length())
			return true;
		else
			return false;
	}
};

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.

[showads ad=inside_post]

 

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

// Custom Hash Functor that will compute the hash on the
// passed string objects length
struct StringHashBySize {
public:
	size_t operator()(const std::string & str) const {
		int size = str.length();
		return std::hash<int>()(size);
	}
};

Declaring unordered_set with custom hasher and compare function,

// Declaring unordered_set with Custom Hash Function and comparator
std::unordered_set<std::string, StringHashBySize, StringEqualBySize> setOfStrs;

Let’s see the complete example as follows,

#include <iostream>
#include <unordered_set>
#include <algorithm>

// Custom Hash Functor that will compute the hash on the
// passed string objects length
struct StringHashBySize {
public:
	size_t operator()(const std::string & str) const {
		int size = str.length();
		return std::hash<int>()(size);
	}
};

// Custom comparator that compares the string objects by length
struct StringEqualBySize {
public:
	bool operator()(const std::string & str1, const std::string & str2) const {

		if (str1.length() == str2.length())
			return true;
		else
			return false;
	}
};

int main() {
	// Declaring unordered_set with Custom Hash Function and comparator
	std::unordered_set<std::string, StringHashBySize, StringEqualBySize> setOfStrs;

	setOfStrs.insert("First");
	setOfStrs.insert("second");

	// Try to insert element with same length as "First"
	// It will not be added
	setOfStrs.insert("third");

	// Try to insert element with same length as "Second"
	// It will not be added

	setOfStrs.insert("second");
	setOfStrs.insert("five");

	// Only three elements are added in set
	// Display them
	for (std::string s : setOfStrs)
		std::cout << s << std::endl;


}

Output:

five
second
First

 

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top