How to Set vs Hashset in C++

1. Set vs. Hashset in C++
2. Set in C++
3. Hashset in C++
4. Key Differences Between a Set and Hashset in C++
5. Conclusion

A set in C++ works as a container to store data elements and retrieve them whenever needed. Similarly, a hashset, more precisely, unordered_set in C++, serves a similar purpose as sets of storing data elements.

In this article, we will be discussing a set and an unordered_set in detail.

Set vs. Hashset in C++

A set is an associative container used to store data elements, whereas an unordered_set is also an associative container used to store data elements for our future needs. Then, how are both of these data structures different from vectors, maps, and other container objects?

The answer is simple. The set and an unordered_set store unique data elements.

Therefore, they do not allow duplicate elements. However, other data structures like vectors and maps also allow the storage of duplicate elements.

Both these data structures are present in the C++ Standard Template Library.

Now, since we briefly explain when to use the set and the unordered_set in C++, let us now understand them in detail.

Set in C++

As discussed earlier, a set is an associative container that stores unique data elements in a sorted manner. However, you can store them in any random order, but as soon as you retrieve them from the set, it will return the elements in a sorted fashion only.

Therefore, a set contains definitions for sorting the hidden data elements from the user.

The sets in C++ are implemented as Binary Search Trees; therefore, they are ordered. Moreover, searching an element takes O(log n) time.

Let us see how to implement a set in C++.

#include <iostream>
#include <set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Output:

1 3 4 6 8 9

Therefore, as you can see in the above code example, the elements stored in the array are in random order and contain duplicate elements. However, as soon as they are stored in a set s, they are internally sorted, and the duplicate elements are also removed.

Therefore, the output is a sorted group of elements without any duplicates.

Hashset in C++

The unordered_set or hashset in C++ both mean the same thing. This unordered_set is also used to store unique data elements, but the only difference between a set and an unordered_set is that an unordered_set does not have an order in which the elements are stored while the set stores the elements in sorted order.

This unordered_set also does not store duplicate elements. However, they are implemented using hash tables.

The element, also called a key, to be inserted is hashed into an index of the hash table and gets stored at that particular index.

Since the elements are stored in any random order, retrieving them takes O(1) time, making its search operation faster to implement.

Let us take an example of using an unordered_set in C++.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  unordered_set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  unordered_set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Output:

1 9 6 3 8 4

Therefore, as you can see in the above code example, the elements are stored in any random order in the set; however, the elements returned from the set are also in any random order, but it does remove all the duplicate elements and returns only the unique elements to the user.

Key Differences Between a Set and Hashset in C++

1. The sets are used to store the elements in increasing order, whereas an unordered_set stores the elements in no order.
2. The sets are implemented using the Binary Search Trees, whereas an unordered_set is implemented using the hash tables.
3. The search operation in a set takes O(log n) time to search an element, whereas it takes O(1) time to search an element in an unordered_set.
4. The sets are included in the #include<set> header file whereas an unordered_set is included using the #include<unordered_set> header file.

Conclusion

In this article, we have discussed a set and a hashset in C++. Both these data structures are present in the C++ STL and are used to store unique data elements.

However, the key difference between the two is that a set returns a sorted set of elements, whereas an unordered_set returns the data elements in no order.

You can use any of the two, but the search operation is faster in an unordered_set, taking almost constant time to search an element; therefore, it is preferred.