Unordered_set in C++

How to Create Unordered_set in C++?

• Include the Header: You need to include the <unordered_set> header in your program.
• Declare the Set: You can declare an unordered_set by specifying the type of elements it will store.
• Operations: You can perform various operations such as insert, erase, find, and iterate through the elements.

How to Initialize an Unordered_set in C++? 

We can initialize an unordered_set in multiple ways in C++. Let’s see those methods with the below example.

#include<bits/stdc++.h>
using namespace std;
 
 
int main(){
 
    // Method 1
    // Initialize an empty unordered set of integer type
    unordered_set<int> s1;
 
    // Method 2   
    // Initializing a Hard-coded unordered set
    unordered_set<int> s2 = {1, 4, 5, 3, 2};
 
    // Method 3
    // IAn Unordered set using another unordered set
    unordered_set<int> s4(s2);
    // s4 = {1, 4, 5, 3, 2}
 
    // Method 4
    // An unordered set using arrays
    int arr[] = {6, 2, 3, 5, 1};
    unordered_set<int> s5(arr, arr+3);
    // s4 = {3, 2, 6} 
}

We have initialized unordered sets using four different methods where,

• Method 1: We have initialized an empty unordered set of integer types.
• Method 2: We have initialized an unordered set of integer types by hardcoding.
• Method 3: We have initialized an unordered set using another unordered set.
• Method 4: We have initialized an unordered set using an array. It stores the elements in reverse order.

You can also practice with the help of Online C++ Compiler

How unordered_set is Implemented Internally in C++

An unordered_set in C++ is typically implemented using a hash table. Each element is hashed to determine its bucket index, allowing for efficient retrieval, insertion, and deletion operations. The hash table manages collisions through techniques like chaining or open addressing. When the load factor exceeds a certain threshold, the table is resized and rehashed to maintain performance, ensuring average constant time complexity for basic operations.

Set vs unordered_set in C++

A set in C++ stores elements in a specific order (usually sorted) and allows for efficient range queries, with operations having a logarithmic time complexity. In contrast, an unordered_set stores unique elements without any particular order, offering average constant time complexity for insertions, deletions, and lookups. The choice between the two depends on whether order matters and the performance characteristics required for specific use cases.

Functions on Unordered_ set in C++

For an unordered set, many functions or methods are defined, among which the most used ones are the empty and size for capacity, find for searching a key, erase and insert for modification.

Now let's learn about them in brief with the below table:

Let's consider an example of declaration, insert, find, and iteration in an unordered set.

• C++

C++

// C++ program to demonstrate various function of unordered_set
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // Declaring unordered set for string data-type
    unordered_set <string> stringSet ;
 
    // Inserting various strings in the set 
    stringSet.insert("code") ;
    stringSet.insert("in") ;
    stringSet.insert("c++") ;
    stringSet.insert("is") ;
    stringSet.insert("fast") ;
 
    string key = "slow" ;
 
    //  Find returns an iterator to the key,
    //  Else it returns end iterator if the key is not found
 
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found" << endl;
    else
        cout << "Found " << key << endl ;
 
    key = "fast";
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found"<<endl ;
    else
        cout << "Found " << key << endl ;
 
    // Now iterating over complete set and printing its content
    cout << "All elements : "<<endl;


    // Initializing an iterator to the unordered set
    unordered_set<string> :: iterator itr;
    for (itr = stringSet.begin(); itr != stringSet.end(); itr++)
        cout << (*itr) << " ";
}

You can also try this code with Online C++ Compiler

Run Code

Output

slow not found
Found fast
All elements : 
fast is c++ in code

Iterator in Unordered_set in C++

An iterator to an unordered_set is an object (like a pointer) pointing to an element inside the unordered_set container. We can use these iterators to move through the elements of the container.

Syntax of Iterator in Unordered_set in C++

// Initializing an iterator
unordered_set<data_type> :: iterator itr;

Example:

Let’s consider an example for iterating over the complete unordered_set.

• C++

C++

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // Declaring unordered set for string data-type
    unordered_set <string> stringSet ;
 
    // Inserting various strings in the set
 
    stringSet.insert("code") ;
    stringSet.insert("in") ;
    stringSet.insert("c++") ;
 
    // Now iterating over complete set and printing its content
    cout << "All elements : "<<endl;


    // Initializing an iterator to the unordered set
    unordered_set<string> :: iterator itr;
    for (itr = stringSet.begin(); itr != stringSet.end(); itr++)
        cout << (*itr) << " ";
}

You can also try this code with Online C++ Compiler

Run Code

Output

All elements : 
c++ in code 

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

What are the differences between set and unordered_set in C++?

A set is an ordered sequence of unique keys, whereas an unordered_set is a set in which unique keys can be stored without any order, so unordered. The time complexity for set operations is O(log(n)), while for an unordered_set, it is O(1).

What is the difference between begin(), cbegin() and end(), cend()?

begin() and end() method returns the iterator to the beginning and end of the unordered_set in c++ whereas cbegin() and cend() returns a const_iterator to the beginning and end of the unordered_set.

What are data types supported for the key of an unordered_set in C++?

An unordered_set can contain a key of any type – user-defined or pre-defined data structure. Still, when we define a key of a user-defined type, we need to specify our custom comparison function according to compare the keys.

What is the worst and average time complexity of an unordered_set in C++?

For an unordered_set, the average time complexity is O(1), while the worst-case complexity is O(n).

Conclusion

In this article, we discussed about unordered_set in C++. We learned how to initialize it and looked at its different methods. Knowing how to use unordered_set can help you manage unique elements effectively in your C++ programs.

Check out this problem - Reverse Nodes In K Group

We hope that this blog has helped you enhance your knowledge regarding different unordered_set in C++, and if you would like to learn more, check out our articles on STL containers in C++, Data Types in C++, and Implementing Sets Without C++ STL Containers.