Using Unordered_set with Custom Hasher and Comparision function

Unordered_set example – Using Unordered_set with Custom Hasher and Comparision function

by

Unordered_set:

Unordered_set example: Since the value of an element defines it, sets are a form of associative container in which each element must be special. The element’s value cannot be changed after it has been added to the set, but the element’s modified value can be removed and added again.

A hash table is used to implement an unordered set, with keys hashed into hash table indices to ensure that insertion is always random. All operations on the unordered set take constant time O(1) on average, which can go up to linear time O(n) in the worst case depending on the internally used hash function, but they perform very well in practise and generally provide a constant time lookup operation.

Custom Hasher and Comparision Function using Unordered_set

Hashing and HashTable

When we add an element to the unordered set, two things happen.

  • It calculates the hash code by calling the hasher function on the passed element. It now chooses the appropriate bucket for the element based on the hash code.
  • The passed element is then compared to all of the elements in the bucket to see if all are identical. If not, the element is stored in that bucket.

As a result, if two elements are identical, their hashcode should always be the same. Otherwise, searching for the correct element in unordered set would be impossible.

We specify the type of element that can be stored in an unordered set when we declare it. In addition, we can include the form of custom hasher and comparison functions.
Assume our unordered set is of type T and we haven’t given a default custom hasher function or comparison function. In that case, the default hasher and comparison function, i.e.

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

For instance, if you construct an unordered set of :string
unordered_set<string> stringset;
you can use the default hasher and comparison function, which is equivalent to:
unordered_set<string, hash<string>,equal_to<string> > stringset;
std::hash calculates the hash of primitive data types, and std::equals to internally calls the == function on the passed elements for comparison

Custom Hasher and Comparision Function

Let’s say we want to store only strings of specific lengths in a std::unordered set of std::string. The default equals to<>() function compares the elements using the == operator. However, in our case, we want to equate elements based on duration, so two elements of the same length should be considered equal. To do so, we’ll need to write our own Comparison Function, i.e.

1)Custom Compare Function

// A custom comparator that compares the lengths of string
// elements.
struct stringEqualbyLen {
public:
    bool operator()(const string& str1,
                    const string& str2) const
    { // if both the lengths are equal then return True else
      // False
        if (str1.length() == str2.length())
            return true;
        else
            return false;
    }
};

The hash code of two elements that are identical according to the comparison function should be the same. In our example, the comparator compares two elements based on their duration. As a result, we can’t use the default std::hash<std::string>() function because it computes the hash code on the entire object rather than the length.

For example, the compare function says that “word” and “bird” are equal because their lengths are the same. However, if the hash code is computed using the default std::hash<std::string>, it can differ. As a result, we’ll need a custom hasher function to ensure that elements that are identical using the compare function above have the same hash code.

2)Custom Hasher

// Custom Hash Function that computes the hash based on
// the length of the passed string object.
struct StringHashByLen {
public:
    size_t operator()(const string& str) const
    {
        int string_size = str.length();
        return hash<int>()(string_size);
    }
};

3)Implementation of Custom Hasher and Compare Functions

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
// Custom Hash Function that computes the hash based on
// the length of the passed string object.
struct StringHashByLen {
public:
    size_t operator()(const string& str) const
    {
        int string_size = str.length();
        return hash<int>()(string_size);
    }
};
// A custom comparator that compares the lengths of string
// elements.
struct stringEqualbyLen {
public:
    bool operator()(const string& str1,
                    const string& str2) const
    { // if both the lengths are equal then return True else
      // False
        if (str1.length() == str2.length())
            return true;
        else
            return false;
    }
};
int main()
{
    // Declaring an unordered_set using custom hash function
    // and Comparator
    unordered_set<string, StringHashByLen, stringEqualbyLen>
        stringset;
    // insering elements to unordered set
    stringset.insert("Hello");
    stringset.insert("This");
    // Try to insert element with same length as "First"
    // It will not be added
    // When we try to insert element with same lengt as
    // "Hello" then the element will not be inserted as shown
    // below
    stringset.insert("world");
    // When we try to insert element with same lengt as
    // "this" then the
    // element will not be inserted
    // as shown below
    stringset.insert("word");
    stringset.insert("BTechGeeks");
    stringset.insert("Python");
    // Only 4 elements will be added to given unordered_set
    // print the unordered set
    for (string str : stringset)
        cout << str << endl;
}

Output:

Python
BTechGeeks
Hello
This

Related Programs: