Set in C++

Set in C++ is an STL(standard template library) container. 

Definition:

  • Set is a  C++ STL container used to store the unique elements, and all the elements are stored in a sorted manner.
  • Once the value is stored in the set, it cannot be modified within the set; instead, we can remove this value and can add the modified value of the element.
  • Sets are implemented using Binary search trees.

When to use sets?

Sets are frequently used containers in competitive programming; whenever there is a need of storing the elements in a sorted manner, we can think of using the sets, but remember that the set does not allow us to store the duplicates value. The value can’t be modified once it is stored. 

Implementing sets

  • Sets are traversed using the iterators. 
  • We have to include the two main header files to work with the sets.

#include< set >

#include< iterator >

  •   Instead of using the above two header files, we can also use only this one header file.

             This one header file contains all the header file , so we can only use this one header file ,     

             instead of all the other header files .

          #include< bits/stdc++.h >

Some Basic Functions Related To Sets

  • begin() :- Returns an iterator to the first element of the set .
  • end() :- Returns an iterator to the theoretical element that follows last element in the set .
  • Empty() :- check wheather the set is empty or not .
  • max_size() :-Returns the maximum number of element that set can hold .
  • Size() :- Returns the number of elements in the set .

Code for implementing set in C++:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set < int > s;
 
    // inserting elements in random order .
    s.insert( 60 ) ;
    s.insert( 10 ) ;
    s.insert( 20 ) ;
    s.insert( 20 ) ;
    s.insert( 40 ) ;
    s.insert( 50 ) ;
    
    // printing set s
    //initialising the iterator, iterating to the beginning of the set.

    set<int >::iterator it ;
    cout << "The element of set s are : \n";
    for (it = s.begin() ; it != s.end() ; it++ ) 
    {
        cout << *it<<" ";
    }
    cout << endl;
    
    cout<< ”The size of set : \n ” << s.size() <<endl ;
    return 0 ;
}
     

Output :-

    The element of set s are :

    10 20 40 50 60 

    The size of set : 5

  •  To store the elements in decreasing order in the set.

    By default, elements are stored in ascending sorted order in the set. To store the elements in descending order, we have to use the given declaration syntax.

           // declaration syntax of the set to store the elements in decreasing sorted order.

     set<int,greater<int>> s;

find() :-

Returns an iterator pointing to the element, if the element is found else return an iterator 

pointing to the end of the set.

Syntax:

set_name.find( key ) ;

erase() :-

this method is used to delete the elements from the set

Syntax:

set_name.erase( starting_iterator , ending_iterator ) ;

Implentation code of set  in c++ :-

#include<bits/stdc++.h>
using namespace std;
int main()
{
set< int >s ;
s.insert( 34 ) ;
s.insert( 14 ) ;
s.insert( 13 ) ;
s.insert( 56 ) ;
s.insert( 5 ) ; 
s.insert( 23 ) ;
s.insert( 10 ) ;
s.insert( 4 ) ;
set<int> :: iterator it;
cout<<”the elements of set are : \n“;
for(it = s.begin() ; it != s.end() ; it++)
{
cout<<*it<< ” “;
}
cout<< endl ;

// Removing all elements upto 10
cout<< ” elements of set s after deleting elements upto 10  \n ” ;
s.erase(s.begin() , s.find(10) ) ;
for ( it = s.begin() ; it!=s.end() ; it++)
cout<< *it << ” “ ;
// Performing Lower bound and upper bound in set
cout<< ” lower bound of 13 \n ” ;
cout<< *s.lower_bound(13)<<endl;
cout<< ” lower bound of 34\n ” ;
cout<< *s.lower_bound( 34 ) << endl;
cout<< ” upper bound of 13 \n ” ;
cout<< *s.upper_bound( 13 ) <<endl;
cout<< ”upper bound of 34  \n” ;
cout<< ”*s.upper_bound( 34 ) <<endl ;
return 0;
}

Output:- 

the elements of set are :

4 5 10 13 14 23 34 56

elements of set s after deleting the elements upto 1

10 13 14 23 34 56

lower bound of 13

13

lower bound of 34

34

upper bound of 13

14

upper bound of 34

56

Some methods on set:-

  1. begin():  Returns an iterator to the first element in the set.
  2. end():- Returns an iterator to the theoretical element that follows the last element in the set.
  3. empty():- check whether the set is empty or not.
  4. size() :- Returns the number of elements in the set .
  5. max_size() :- Returns the maximum number of elements that set can hold.
  6. rbegin():- Returns a reverse pointer, pointing to the last element of the set.
  7. rend():- Returns a reverse iterator pointing to the theoretical element right before the first element in the set container.
  8. erase (iterator position):- Removes the element at the position pointed by the pointer.
  9. erase( const x ) :- Removes the value x from the set .
  10. insert( const x ) :- Inserts a new element to the set .
  11. find( x ):- Returns an iterator based on the position of the element if it is found, else return iterator at the end.
  12. count( const x ) :-Return 1 or 0 based on the element x is found in the set or not .
  13. lower_bound( const x ):- Returns an iterator to the element x if it is found else, return the iterator to the next element of it.
  14. upper_bound(const x) :- Returns an iterator to the first element after the element x .
  15. emplace():-  this function is used to insert the new element into the set container, only if the element to be inserted is unique and does not already exist in the set.
  16. swap():- This function is used to swap the content of the two sets, but the sets must be of the same type.
  1. clear() :- Removes all elements from the set .  

Difference between set, multiset, and unordered_set.

set:

  • A Set stores the elements in sorted order.
  • Set stores unique elements.
  • Elements can only be inserted and deleted but cannot be modified within the set.
  • Sets are implemented using a binary search tree.
  • Sets are traversed using iterators.

C++ program showing insertion and deletion functioning in the set.

#include<bits/stdc++.h>
using namespace std;
int main()
{
// declaring set.
set< int > s ;
// adding random elements to set using the insert().
s.insert( 13 ) ;
s.insert( 11 ) ;
s.insert( 44 ) ;
s.insert( 1 ) ;
s.insert(10 ) ;
s.insert( 25 ) ; 
s.insert( 11 ) ;   // 11 will only be added only once .  
// declaring iterators to traverse through the set .
set <int> s :: iterator ptr1 , ptr2 , ptr3 ;
cout << “ set elements are initially  : \n” ;
for ( ptr1 = s.begin() ; ptr1 != s.end() ; ptr1++)
{
 cout<< *ptr1 << “ “ ;
}
cout <<endl ;
// making another set  s2 , storing elements in decreasing order.
// copying the elements of s into s2 .
set < int , greater <int> > s2 ( s.begin()  , s.end() ); 
set < int , greater <int > > :: iterator itr ; 
ptr2 = s.find( 11 ) ;
ptr3 = s.find( 25) ;
// elements from 11 to 25 are erased from the set using the erase() . 
s.erase ( ptr2 , ptr3);
cout << ”  set element after erase  : \n ” ;
for ( ptr1 = s.begin() ; ptr1 != s.end() ; ptr1++)
{
cout << *ptr1 << “ “;
}
cout << endl ;
cout << “ elements of set s2 are : \n” ;
for ( itr = s2.begin() ; itr != s2.end()  ; itr++)
{
cout << *itr << “ “;
}    
return 0;
}

Output : 

set elements are initially :

1 10 11 13  25 44

set elements after erase :

1  10 25 44

elements of set s2 are :

44 25 13 11 10 1

Multiset :

  • It also stores the elements in a sorted manner, either ascending or decreasing.
  • Multiset allows storage of the same values many times; or, in other words, duplicate values can be stored in the multiset.
  • We can delete the elements using iterators.

       Note: – All other properties of a multiset are the same as that of the set, the difference       

                   being it allows storage of the same multiple values.

C++ program showing implementation of multiset.

#include<bits/stdc++.h>
using namespace std ;
int main()
{
// declaring multiset.
multiset < int > ms;
// elemets added to multiset . 
ms . insert ( 14 ) ;
ms . insert ( 10 ) ;
ms . insert ( 20 ) ;
ms . insert ( 5 )  ;
ms . insert ( 14 ) ;    // duplicate element added . 
ms . insert ( 25 ) ;
ms . insert ( 25 ) ;   //  duplicate element added . 
ms . insert ( 29 ) ;

// declaring iterators to traverse the mutiset.
multiset < int > :: iterator it1 , it2 , it3 ;
cout << “ elements of multiset are : \n” ;
for ( it1 = ms.begin() ; it1 != ms.end() ; it1++)
{
cout << *it1 << “ “ ;
}

it2 = ms.find ( 10 ) ;
it2 = ms.find ( 25 ) ;
// removing  the elements of multiset from 10 to 25 (exclusive) . 
ms.erase ( it1 , it2 ) ;
cout << “ elements of multiset after removing the elements : \n ” ;
for ( it1 = ms.begin() ; it1 != ms.end() ; it1++ )
{
cout<< *it1 << “ “ ;
}
return 0 ; 
}

Output :

elements of multiset are :

5 10 14 14 20 25 25 29

elements of multiset after removing the elements :

5 25 25 29

Conclusion:  multiset allows storing duplicate values, whereas set doesn’t.

Unordered_Set :

  • Unordered_set can stores elements in any order, with no specified order for storing elements. It generally depends upon the machine that you are using.
  • Stores unique elements, no duplicates allowed.
  • unordered_set uses the hash table for storing the element.

Note: All other properties are the same as that of the set.

C++ program showing implementation of set.

#include<bits/stdc++.h>
using namespace std;
int main()
{
// declaring unordered_set .
unordered_set < int > us;
// adding elements to unordered_set  . 
us . insert ( 14 ) ;
us . insert ( 10 ) ;
us . insert ( 20 ) ;
us . insert ( 14 ) ;   // duplicates added .
us . insert ( 12) ;
us . insert ( 8 ) ;
unordered_set < int > :: iterator it1 , it2 ;
cout << “ elements of unordered_set are \n “ ;
for ( it1 = us.begin() ; it1 != us.end() ; it1++ )
{
cout <<  *it1 << ” “ ;
}
// erasing element 14 
it2 = us.find ( 14 ) ;
us.erase( it2 ) ;
cout<< “ elements of unordered_set after erasing the element : \n ” ;
for(  it1 = us.begin() ; it1 != us.end() ; it1++ )
{
cout << *it1 << “ “ ;
} 
return 0;
}

Output :

elements of unordered_set are :

14 10 20 12 8   

elements of unordered_set after erasing the element :

10 20 12 8 

Note:- Don’t compare the order of output produced by printing the unordered_set with anyone because it can be different for everyone depending upon their machine, etc. 

Conclusion: In simple words, Set is an STL container that stores sorted ( ascending or descending  ) and unique elements inside it. Multiset also stores the element in a sorted manner, but it can also store duplicate values. Unordered_Set stores the element in any manner, but it doesn’t store the identical values.

This brings us to the end of the blog on the concept of Set in C++. We hope that you found this comprehensive and helpful and were able to gain the required knowledge. If you wish to up-skill and learn more such concepts, you can check out the pool of Free online courses on Great Learning Academy.

Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.


0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

18 − 17 =