Open In App

Unordered Sets in C++ Standard Template Library

Last Updated : 12 Jun, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

An unordered_set is an unordered associative container implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized. All operations on the unordered_set take constant time O(1) on an average which can go up to linear time O(n) in the worst case which depends on the internally used hash function, but practically they perform very well and generally provide a constant time lookup operation. 
 
The unordered_set can contain a key of any type – predefined or user-defined data structure but all the keys must be unique. It is defined inside <unordered_set> header file as std::unordered_set class.

Syntax:

std::unordered_set<data_type> name;

In std::unordered_set, many functions are defined among which the most used functions are:

  • The size() and empty() for capacity.
  • The find() for searching a key.
  • The insert () and erase() for modification.

Example:

C++




// C++ program to demonstrate various function of
// unordered_set
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // declaring set for storing string data-type
    unordered_set<string> stringSet;
 
    // inserting various string, same string will be stored
    // once in set
 
    stringSet.insert("code");
    stringSet.insert("in");
    stringSet.insert("c++");
    stringSet.insert("is");
    stringSet.insert("fast");
 
    string key = "slow";
 
    // find returns end iterator if key is not found,
    // else it returns iterator to that key
 
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found" << endl << endl;
    else
        cout << "Found " << key << endl << endl;
 
    key = "c++";
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found\n";
    else
        cout << "Found " << key << endl;
 
    // now iterating over whole set and printing its
    // content
    cout << "\nAll elements : ";
    unordered_set<string>::iterator itr;
    for (itr = stringSet.begin(); itr != stringSet.end();
         itr++)
        cout << (*itr) << endl;
}
 






                        










Output


slow not found

Found c++

All elements : is
fast
c++
in
code




The functions find(), insert() and erase() take a constant amount of time on average. The find() function returns an iterator to end() if a key is not there in the set, otherwise, an iterator to the key position is returned. The iterator works as a pointer to the key values so that we can get the key by dereferencing them using the * operator.


We can also see that the order of output is messed up because there is no particular order to store data in unordered_set.




Note: The Unordered_set allows only unique keys, for duplicate keys unordered_multiset should be used.




set vs unordered_set in C++ STL










Set




Unordered Set








A Set is an ordered sequence of unique keys.
An unordered_set is a set in which a key can be stored in any order, so unordered.




Set is implemented as a balanced tree structure making it possible to maintain order between the elements (by specific tree traversal).
The unordered_set is implemented as hash tables as we don’t have to worry about any order.




The time complexity of set operations is O(log n).
The time complexity of basic set operations is O(1).








A practical problem based on unordered_set


Given an array(list) of integers, find all the duplicates among them(suppose the duplicates are the same number guessed by random people in an experiment).


Input:


arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5}


Output:


Duplicate items are: 5 2 1 


Example:




C++














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















// C++ program to find duplicate from an array using


// unordered_set


#include <bits/stdc++.h>


using namespace std;


 


// Print duplicates in arr[0..n-1] using unordered_set


void printDuplicates(int arr[], int n)


{


    // declaring unordered sets for checking and storing


    // duplicates


    unordered_set<int> intSet;


    unordered_set<int> duplicate;


 


    // looping through array elements


    for (int i = 0; i < n; i++) {


        // if element is not there then insert that


        if (intSet.find(arr[i]) == intSet.end())


            intSet.insert(arr[i]);


 


        // if element is already there then insert into


        // duplicate set


        else


            duplicate.insert(arr[i]);


    }


 


    // printing the result


    cout << "Duplicate item are : ";


    unordered_set<int>::iterator itr;


 


    // iterator itr loops from begin() till end()


    for (itr = duplicate.begin(); itr != duplicate.end();


         itr++)


        cout << *itr << " ";


}


 


// Driver code


int main()


{


    int arr[] = { 1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5 };


    int n = sizeof(arr) / sizeof(int);


 


    printDuplicates(arr, n);


    return 0;


}



















                        







                        










Output


Duplicate item are : 5 2 1 




Time Complexity: O(n log n)
Auxiliary Space: O(n)
 


std::unordered_set Member Methods


The following table contains all the member functions of std::unordered_set class:










Function Name




Function Description










insert()


Insert a new {element} in the unordered_set container.






begin()


Return an iterator pointing to the first element in the unordered_set container.






end()


Returns an iterator pointing to the past-the-end-element.






count()


Count occurrences of a particular element in an unordered_set container.






find()


Search for an element in the container.






clear()


Removes all of the elements from an unordered_set and empties it.






cbegin()


Return a const_iterator pointing to the first element in the unordered_set container.






cend()


Return a const_iterator pointing to a past-the-end element in the unordered_set container or in one of its buckets.






bucket_size()


Returns the total number of elements present in a specific bucket in an unordered_set container.






erase()


Remove either a single element or a range of elements ranging from start(inclusive) to end(exclusive).






size()


Return the number of elements in the unordered_set container.






swap()


Exchange values of two unordered_set containers.






emplace()


Insert an element in an unordered_set container.






max_size()


Returns maximum number of elements that an unordered_set container can hold.






empty()


Check if an unordered_set container is empty or not.






equal_range


Returns range that includes all elements equal to a given value.






operator=


Copies (or moves) an unordered_set to another unordered_set and unordered_set::operator= is the corresponding operator function.






hash_function()


This hash function is a unary function that takes a single argument only and returns a unique value of type size_t based on it.






reserve()


Used to request a capacity change of unordered_set.






bucket()


Returns the bucket number of a specific element.






bucket_count()


Returns the total number of buckets present in an unordered_set container.






load_factor()


Returns the current load factor in the unordered_set container.






rehash()


Set the number of buckets in the container of unordered_set to a given size or more.






max_load_factor()


Returns(Or sets) the current maximum load factor of the unordered set container.






emplace_hint()


Inserts a new element in the unordered_set only if the value to be inserted is unique, with a given hint.






== operator 


The ‘==’ is an operator in C++ STL that performs an equality comparison operation between two unordered sets and unordered_set::operator== is the corresponding operator function for the same.






key_eq()


Returns a boolean value according to the comparison. It returns the key equivalence comparison predicate used by the unordered_set.






operator!=


The != is a relational operator in C++ STL which compares the equality and inequality between unordered_set containers.






max_bucket_count() 


Find the maximum number of buckets that unordered_set can have.








Must Read – Recent Articles on unordered_set 




                                    


                                                                          

                                        












                                      

                                                                        

                                        

                                            

                                                

                                                    
U
                                                

                                                

                                                    



    Utkarsh Trivedi



                                                

                                            

                                                                                    

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                            
 
                                

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Different Ways to Initialize an unordered_set in C++
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
The C++ Standard Template Library (STL)

                
The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized. Working knowledge of template classes is a prerequ

            

            
            

                
                5 min read
            

        
    
        
            

                
Sort in C++ Standard Template Library (STL)

                
Sorting is one of the most basic functions applied to data. It means arranging the data in a particular fashion, which can be increasing or decreasing. There is a builtin function in C++ STL by the name of sort(). This function internally uses IntroSort. In more details it is implemented using hybrid of QuickSort, HeapSort and InsertionSort.By defa

            

            
            

                
                6 min read
            

        
    
        
            

                
Set in C++ Standard Template Library (STL)

                
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e. either ascending or descending. The std::set class is the part of C++ Standard Template Library (STL) and it is defined inside the &lt;set&gt; header file. Syntax: std:

            

            
            

                
                7 min read
            

        
    
        
            

                
Priority Queue in C++ Standard Template Library (STL)

                
A C++ priority queue is a type of container adapter, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue, and elements are in non-increasing or non-decreasing order (hence we can see that each element of the queue has a priority {fixed order}). In C++ STL, the top elemen

            

            
            

                
                11 min read
            

        
    
        
            

                
Containers in C++ STL (Standard Template Library)

                
A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows great flexibility in the types supported as elements. The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference ob

            

            
            

                
                2 min read
            

        
    
        
            

                
Binary Search in C++ Standard Template Library (STL)

                
Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted.It works by comparing the middle item of the array with our target, if it match

            

            
            

                
                3 min read
            

        
    
        
            

                
Multimap in C++ Standard Template Library (STL)

                
Multimap is similar to a map with the addition that multiple elements can have the same keys. Also, it is NOT required that the key-value and mapped value pair have to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always. These properties of multimap make it very much useful i

            

            
            

                
                6 min read
            

        
    
        
            

                
Map in C++ Standard Template Library (STL)

                
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values. std::map is the class template for map containers and it is defined inside the &lt;map&gt; header file. Basic std::map Member FunctionsSome basic functions associated with std::

            

            
            

                
                8 min read
            

        
    
        
            

                
Multiset in C++ Standard Template Library (STL)

                
Multisets are a type of associative containers similar to the set, with the exception that multiple elements can have the same values. Some Basic Functions associated with multiset: begin() - Returns an iterator to the first element in the multiset --&gt; O(1)end() - Returns an iterator to the theoretical element that follows the last element in th

            

            
            

                
                6 min read
            

        
    
        
            

                
Queue in C++ Standard Template Library (STL)

                
Queues are a type of container adaptors that operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. Queues use an encapsulated object of deque or list (sequential container class) as its underlying container, providing a specific set of member functions to access its eleme

            

            
            

                
                3 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                            
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
three90RightbarBannerImg

	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox