Set in C++STL

by anupmaurya
0 comment

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; }
Code language: PHP (php)

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; }
Code language: PHP (php)

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; }
Code language: PHP (php)

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; }
Code language: PHP (php)

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; }
Code language: PHP (php)

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.

You may also like