Set in C++ with Examples

Back to: C++ Tutorials For Beginners and Professionals

Set in C++ with Examples

In this article, we will start our discussion on associative containers i.e. Set in C++ with Examples. The first associative container that we will discuss is set and if you understand set then you understand the fundamental of other associative containers. Please read our previous article where we discussed Priority Queue in C++ with Examples.

Set in C++:

An associative container that contains a sorted set of unique objects of type key. Instead of accessing by some index here, we have a key-value association. In the case of a set, there is no value, the key itself is the value. In terms of mathematics, a set is a group of elements that does not allow duplicates. Similarly in C++ also, the set will not allow duplicate elements.

We have another version of the set called multiset which allows duplicate keys. The set contains a sorted set of unique objects. It uses the compare function to order the elements or sort the elements. We also have an unordered version called unordered set which does not contain the order and that is purely a hash table.

In order to work with the set, you need to include <set> header file. A user-provided comparison can be supplied to change the ordering (sorting). And if you don’t provide it, it will be std::less. So it will sort in ascending order. Let’s say you are creating a set of some custom defined class std::less will not work. So, you will need to define your own compare function for that. We will see an example of this.

So, it enables you to insert and remove elements and also find elements in the set. All these operations will take logarithmic time. And this is maintained with the use of some balanced binary search trees and usually, it is red-black trees.

RB Tree:

The red-black tree is balanced by its red and black properties. We have a tree where the root will be black and its children can be red or black but a red cannot have a red child. So double red is not possible but you can have double black. Another property is that all the leaves will have the same black depth. Black depth is the number of black nodes from that to the root. They can be at different depths but black depths would be the same for all the leaves. So, using these two properties that no two red can occur and the black depth of all leaves is the same, maintains the balance search property. So, this is kind of balanced and you are able to maintain all the operations in the log of n because the height of this balanced binary search tree will be the log of n. Now let us see some of the functions that we can use.

Set Functions in C++:

1. Size () – it will give the number of elements present in the set and it does not allow duplicates. So, if you insert the same number multiple times, only one of them will be inserted.
2. = – you can create one initializer list and assign to it, this set. We will see an example of this.
3. Clear () – it will remove all elements from the set.
4. Count () – here you need to pass the key and it will search the number of occurrences of that. In this case, it will be either 0 or 1 depending on whether it’s present or not.
5. Find () – it will search for a number and return the iterator to that number. if it does not find the number, it will return SET_NAME.end () that is it will not point to a valid index but beyond the last one.
6. Empty () – it is used to check whether there are any elements or not.
7. Insert (), erase () –we will see these functions in some detail because they have multiple versions and all of them can be useful.
8. Upper_bound (), lower_bound () – In upper bound, let us say you have 5 10 12 15 20. In this case, let’s say we are calling upper_bound (10), it will return greater than 10. So, it will start from 12 and you can iterate till the end. So upper_bound (10) will return 12 and lower_bound (10) will return 10 which is greater than equal to. Let us see the insert and erase different versions in some detail.

Insert Functions in Set:

Insert (Key key):

If you are inserting a key like you have a set ‘s’ i.e. set of integers and you are inserting s.insert (5), this will insert five here and this version will return a pair consisting of iterators to inserted element. If it is already present then it will return that only. Let us say you insert 5 again so it will not insert it again but return the iterator to it and the bool value which will denote whether insertion took place or not. So it will return a pair.

Insert (iterator pos1, iterator pos2):

If you pass two iterator positions, these iterator positions will be like let us say you have a vector of int and it has a few elements and you want to insert from the x to the y position of this vector into a set,

V = {_ _ _ x _ _ _ y _ _ _ _ }

Let’s say you want to insert everything so s.insert (v.begin (), v.end ()) will insert all the elements. If there are duplicates then it will insert one of them, not all. It can be used in some scenarios where you have a vector and you want to create a set out of that. So, you can do it in one line and it does not return anything.

Insert (initializer_list l):

Similarly, we can pass the initializer list. You can think of it as in the above example if we are inserting from x to y, so it will be an initializer list or you can say a subset of the vector. So, you will pass that initializer list and it will insert one of the duplicate elements to set. It will not return anything. We will see examples of all of these functions.

Erase Functions in Set:

1. erase (iterator pos): It removes the element at the given position and returns the iterator following the last element removed.
2. erase (iterator pos1, iterator pos2): As we have seen in the insert function, we can also pass two positions in this function so that all the elements between these positions will be removed. So, the x position will be included and the y position will be excluded. It also returns the iterator following the last element removed.
3. erase (key): In this signature, we have passed the iterator to the key but here we are passing the key itself. If any key is present in the set, it will remove all the elements with the key values. It will return the number of elements removed.

Now let’s see the complete program.

Example to understand Set Functions in C++:

#include <iostream>
#include <set>
#include <vector>
using namespace std;

class Branch{
public:
    int year;
    string b_name;
    
    void print_student() const {
        cout << "[ Branch Name = " << b_name << ", Year = " << year << "]\n";
    }
    
    bool operator < (const Branch& other) const {
        return (this->year > other.year);
    }
};

int main() {
    set<int> s = {100, 200, 50, 100, 150, 200, 40};
    cout << "size = " << s.size() << endl;
    s.insert(1000);
    s.insert(100);
    cout << "size = " << s.size() << endl;
    
    for(auto& el: s)
        cout << el << " ";
    cout << endl;
    
    //auto it = s.erase(s.find(10));
    //cout << *it << endl;
    int num_erased = s.erase(100);
    cout << "num_erased = " << num_erased << endl;
    
    for(auto& el: s)
        cout << el << " ";
    cout << endl;
    
    auto ub = s.upper_bound(100);
    auto lb = s.lower_bound(100);
    cout << "ub = " << *ub << endl;
    cout << "lb = " << *lb << endl;
    
    s.insert({-100, -300, -200});
    for(auto& el: s)
        cout << el << " ";
    cout << endl;
    
    vector<int> v = {100, 200, 150, 50, 40};
    s.insert(v.begin(), v.end());
    for(auto& el: s)
        cout << el << " ";
    cout << endl;
    
    //------------
    set<Branch> b = {{2, "IT"}, {1, "CS"}};
    for(auto& bh: b)
        bh.print_student();
    
    return 0;
}

Output:

In the next article, I am going to discuss MultiSet in C++ with Examples. Here, in this article, I try to explain Set Functions in C++ with Examples and I hope you enjoy this article. I would like to have your feedback. Please post your feedback, question, or comments about this Set Functions in C++ with Examples article.