In C++, both set and HashSet(also called unordered_set) are used to store elements but they have different properties and use cases. In this article, we will learn the key differences between a set and a HashSet in C++.

Set in C++

In C++, a std::set is a container that stores only the unique elements in a sorted fashion. We can add duplicate elements in any random order but when we retrieve the elements we will get the unique elements in a sorted manner only. Following are the important points regarding set in C++:

• Set are implemented using self-balancing Binary Search Trees, therefore they are ordered.
• Elements in a set are always sorted in increasing order.
• The time complexity for searching in a set is O(log(n)).

Syntax to Declare Set

set <dataType> setName;

Example

The below example demonstrates the use of a set in C++.

// C++ program to demonstrate the use of set container

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

int main()
{
    // creating a set of integer type
    set<int> st;

    // Inserting values in random order and with duplicates
    // in a set
    st.insert(10);
    st.insert(5);
    st.insert(10);
    st.insert(15);

    // printing the element in a set
    for (auto it : st) {
        cout << it << ' ';
    }
    return 0;
}

5 10 15 

Time Complexity: O(log n), where n is the number of elements in the set,
Auxilliary Space: O(n)

HashSet in C++

In C++ , a HashSet or std::unordered_set both are same. It is a container which is also used to store elements but unlike set it does not store elements in a sorted order. Following are some important points about HashSet:

• HashSet is not part of the C++ standard. It’s an extension and its equivalent is unordered_set in the C++ standard library.
• HashSet is implemented using hash tables.
• The key element, is hashed into an index of the hash table and gets stored at that particular index.
• The time complexity to search an element in a HashSet is O(1), which is faster than a set.
• When we iterate through a HashSet, the order of elements will be random.

Syntax to Declare HashSet

unordered_set<dataType> unordered_set_name;

Example

The below example demonstrates the use of a HashSet in C++.

// C++ program to demonstrate the use of HashSet container

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

int main()
{
    // creating a HashSet of integer type
    unordered_set<int> ust;

    // Inserting values in random order and with duplicates
    // in a HashSet
    ust.insert(10);
    ust.insert(5);
    ust.insert(10);
    ust.insert(15);

    // printing the element in a set
    for (auto it : ust) {
        cout << it << ' ';
    }
    return 0;
}

15 5 10 

Time Complexity: O(1), but can degrade to O(n) in the worst case due to hash collisions.
Auxilliary Space: O(n)

Difference Between Set and HashSet in C++

To understand the difference between Set and HashSet in C++, we need to know what each container does.