Set in C++STL

1.1K

In this tutorial we will learn about Set in C++ ,how to Initializing a Set, Traversing a Set, how to add element in Set and more.

Some Properties of Set in C++

• Uniqueness – All elements inside a C++ Set are unique.
• Sorted – The elements inside a Set are always in a sorted manner.
• Immutable – Any element inside the Set cannot be changed. It can only be inserted or deleted.
• Unindexed – The STL Set does not support indexing.
• Internal Implementation – The Sets in STL are internally implemented by BSTs (Binary Search Trees).

When to use sets in C++?

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. 

C++ Set Declaration

set<datatype> setname;

set<int> val; // defining an empty set
set<int> val = {6, 10, 5, 1}; // defining a set with values

Initializing a Set in C++

#include<bits/stdc++.h>

using namespace std;
 
int main(){
 
    // Empty Set - Increasing Order (Default)
    set<int> s1;
    // s1 = {}
 
    // Empty Set - Decreasing Order
    set<int, greater<int>> s2;
    // s2 = {} 
 
    // Set with values
    set<int, greater<int>> s3 = {6, 10, 5, 1};
    // s3 = {10, 6, 5, 1}
 
    // Initialize Set using other set
    set<int, greater<int>> s4(s3);
    // s4 = {10, 6, 5, 1} 
 
    // Initializing a set from array
    int arr[] = {10, 4, 5, 61};
    set<int> s5(arr, arr+2);  // Only two elements 
    // s5 = {4, 10}
 
    return 1;
}

Traversing a Set in C++

#include<iostream>
#include<set>
 
using namespace std;
 
int main(){
 
    // Set with values
    set<int, greater<int>> s1 = {6, 10, 5, 1};
     
    // Iterator for the set
    set<int> :: iterator it;
 
    // Print the elements of the set
    for(it=s1.begin(); it != s1.end();it++)
        cout<<*it<<" ";
    cout<<endl;
}

Output

10 6 5 1

Adding elements to a Set

#include<iostream>
#include<set>
 
using namespace std;
 
int main(){
 
    // Set with values
    set<int, greater<int>> s1 = {6, 10, 5, 1};
    // s1 = {10, 6, 5, 1}
 
    // Inserting elements in the set
    s1.insert(12);
    s1.insert(20);
    s1.insert(3);
 
    // Iterator for the set
    set<int> :: iterator it;
 
    // Print the elements of the set
    for(it=s1.begin(); it != s1.end();it++)
        cout<<*it<<" ";
    cout<<endl;
 
}

Output

20 12 10 6 5 3 1 

The time complexities for doing various operations on sets are

• Insertion of Elements – O(log N)
• Deletion of Elements – O(log N)

Removing elements from a Set in C++

#include<iostream>
#include<set>
 
using namespace std;
 
int main(){
 
    // Set with values
    set<int, greater<int>> s1 = {6, 10, 5, 1};
    // s1 = {10, 6, 5, 1}
 
    // Erasing element value = 1
    s1.erase(1);
    // s1 = {10, 6, 5}
 
    // Erasing the first element
    s1.erase(s1.begin());
    // s1 = {6, 5}
 
    // Iterator for the set
    set<int> :: iterator it;
 
    // Print the elements of the set
    for(it=s1.begin(); it != s1.end();it++)
        cout<<*it<<" ";
    cout<<endl;
 
}

Output

6 5

Searching an element in a Set in C++

#include<iostream>
#include<set>
 
using namespace std;
 
int main(){
 
    // Set with values
    set<int, greater<int>> s1 = {6, 10, 5, 1};
    // s1 = {10, 6, 5, 1}
 
    // The value to be searched
    int val = 5;
 
    // Check if the iterator returned is not the ending of set
    if(s1.find(val) != s1.end())
        cout<<"The set contains "<<val<<endl; 
    else
        cout<<"The set does not contains "<<val<<endl; 
 
    // The value to be searched
    val = 11;
 
    // Check if the iterator returned is not the ending of set
    if(s1.find(val) != s1.end())
        cout<<"The set contains "<<val<<endl; 
    else
        cout<<"The set does not contains "<<val<<endl;    
 
}

Output

The set contains 5
The set does not contains 11

Commonly used Set functions

Here is a wide range of operations(function) that can be performed on sets in C++, that are Commonly used Set functions

1. begin() –  This method returns an iterator that points to the first element in the set.
2. end() – This function returns an iterator that points to the theoretical position next to the last element of the set.
3. empty() – Returns true if the Set is empty, otherwise false.
4. size() – Returns the size of the Set
5. max_size() – This method returns upper bound of elements in a set, i.e. the maximum number that a set can hold.
6. rbegin() – Returns a reverse iterator pointing to the last element of the Set.
7. rend() – Returns a reverse iterator pointing before the first element of the Set.
8. erase (iterator_position) – This method when applied  on a set, removes the element at the position pointed by the pointer given in the parameter.
9. erase (value) – This function directly deletes the value passed in the parameter from a set .
10. insert (value) – This function inserts a new element into the set .
11. find( n ) – This method searches for the element ‘n’ in the set and returns an iterator pointing to the position of the found element. If the element is not found, it returns an iterator pointing at the end.
12. count(value) – Returns 1 if the ‘value’ is present in the Set, otherwise 0..
13. clear() – Empties the entire Set.
14. swap(set1, set2) – Swaps the contents of both sets.
15. emplace(value) – Inserts the ‘value’ inside the set, if it is not present.