Set container and it’s important functions in C++ STL

Introduction

Set is an associative container present in C++ STL (Standard Template Library) that stores unique objects as keys. Set does not consider duplicate values. In the set, container key is equal to the value. Like any other associative containers in STL, a lookup for any element is done on the basis of keys.

To use set in C++ program ; include <set> header file.

Based upon the order in which keys are stored in a set container, they can be categorized into ordered and unordered sets.

1. Ordered set/Set

In an ordered set, unique keys are stored in an ordered manner, usually, they are stored in ascending order. The average time complexity for operations like insert and delete is logarithmic.

Declaration syntax :  set <object_datatype > set_name;

ex: set <int> s; This statement will create an set container named s , that will store unique key of integer type in non-decreasing order.

Storing elements in the set in descending order

Use functional object class, greater<int> for changing the default order in which keys are stored in the set container.

#includes<bits/stdc++.h>
using namespace std;
int main()
{
    set<int,greater<int>> s;
    s.insert(-9);
    s.insert(9);
    s.insert(19);
    s.insert(99);
    s.insert(-99);
    for(auto x: s)
    cout<<x<<' ';
    return 0;
}

output:

99 19 9 -9 -99

2. Unordered set

In an unordered set, unique keys are stored in random order, i.e., Stored keys do not follow any particular order. Unordered set operations are generally faster than ordered set operations. The average time complexity for general operations like insertion and deletion is constant.

Declaration syntax :  unordered_set <object_datatype > set_name;

frequently used functions in set :

begin(): it returns an iterator pointing to the first element of the set.

end(): it returns an iterator pointing to the hypothetical element post the last element of the set. Note: It is good practice to avoid accessing the memory location pointed by the end() function.

insert(): this function is used to store elements in the set container.

count(x) : this function returns count of element x, in the set. Since the set stores only unique elements, so the count of every element stored in the set is 1. The return type of this function is boolean, i.e., 0 or 1 in the set. If key x is not present in the set, then this it returns 0, otherwise 1.

find(x): this function returns an iterator pointing to the key x, if it is present in the set otherwise it returns the end() iterator.

functions for deleting elements in C++ set container

erase(): this function is used to delete a key or a range of stored keys. It can be used in 3 ways based on its input parameter:

1. When a value, x is inserted as a parameter like erase(x), then key x is deleted from the set if it would have been present in the set.
2. When an iterator, itr is passed as a parameter like erase(itr), then the key pointed by the iterator is deleted.
3. A certain range of iterators can also be passed into erase() function to be deleted like erase(it, s.end()). This will delete all the keys stored at the memory location pointed by the leftmost iterator up to one position less than the rightmost iterator. NOTE: The right side iterator is excluded i.e., [left_iterator, right_iterator)

size(): it returns the size or no of keys stored in the set.

#include<bits/std++.h>
using namespace std;
int main()
{
    set<int>s;
    s.insert(10);
    s.insert(20);
    s.insert(50);
    s.insert(100);
    s.insert(2);
    s.insert(-5);
    s.insert(10);
    cout<<"elements in set : ";
    for(auto x:s)
    {
        cout<<x<<' ';
    }
    cout<<"\nelements in set : ";
    if(s.count(10))
        cout<<"10 is present in set\n";
    else
        cout<<"10 is not present in set\n";
    auto it=s.find(10);
    cout<<*it<<"\n";
    cout<<"size of set is : "<<s.size()<<"\n";
    s.erase(10);
    cout<<"elements in set after deleting 10 from it\n";
    for(auto it=s.begin(); it!=s.end(); ++it)
    cout<<*it<<' ';
    it=s.find(-5);
    s.erase(it);
    cout<<"elements in set after deleting -5 from it\n";
    for(auto it=s.begin(); it!=s.end(); ++it)
    cout<<*it<<' ';
    it=s.find(50);
    s.erase(it, s.end());
    cout<<"elements in set after deleting -5 from it\n";
    for(auto it=s.begin(); it!=s.end(); ++it)
    cout<<*it<<' ';
    return 0;
}

Output :

elements in set : -5 2 10 20 50 100
elements in set : 10 is present in set
10
size of set is : 6
elements in set after deleting 10 from it
-5 2 20 50 100 elements in set after deleting -5 from it
2 20 50 100 elements in set after deleting -5 from it
2 20

lower_bound(x): 

1. This function returns an iterator to the first occurrence of the key, x if it is present in the set.
2. If x is not present in the set, then it returns an iterator to the element just greater than x.
3. If x is greater than the last element present in the set then it returns the hypothetical iterator s.end().

upper_bound(x): 

1. This function returns an iterator to a key just greater than x whether x is present in the set or not.
2. It behaves the same as lower_bound when x is greater than the last element.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    set<int>s={0,1,3,-3,-6,10, 98, 786, 0, 1, 2, 3, 4};
    cout<<"Elements stored in set : ";
    for(auto x:s)
    cout<<x<<' ';
    cout<<"\n";
    set<int>::iterator it=s.lower_bound(0);
    cout<<*it<<"\n";
    it=s.lower_bound(6);
    cout<<*it<<"\n";
    it=s.lower_bound(1000);
    if(it==s.end())
    cout<<"yes"<<"\n";
    it=s.upper_bound(0);
    cout<<*it<<"\n";
    it=s.upper_bound(6);
    cout<<*it<<"\n";
    it=s.upper_bound(1000);
    if(it==s.end())
    cout<<"yes"<<"\n";
    return 0;
}

output :

Elements stored in set : -6 -3 0 1 2 3 4 10 98 786
0
10
yes
1
10
yes

---

Based on the uniqueness of elements stored in the set, there is one more variation of the set, Multiset. This article is about MULTISET.

If this article added any value to your algorithmic knowledge then please share your valuable feedback in the comment section. Thank you!