C++ STL Set

In C++, a set represents the fundamental data structure that arranges the unique elements in some sorting order and stores them. The sets are known as the associative containers, and the unique sorted elements are known as the sorted keys. We can insert or delete these keys, but we cannot modify them.

By default, sets follow ascending order to sort the keys. Sets are part of the Standard Template Library (STL) available in C++ , where in the STL, the set class offers useful components that upgrade the efficiency of the set operation. As the sets use the default sorting order for keys and do not use an indexing mechanism, we cannot access these keys with their index numbers.

Syntax

It has the following syntax:

template < class T,     // set::key_type/value_type  

           class Compare = less<T>,   // set::key_compare/value_compare  

           class Alloc = allocator<T>    // set::allocator_type  

           > class set;

Parameter:

• ✅ T: T represents the type of element stored in the container set.
• ✅ Compare: A comparison class that takes two arguments of the same type bool and returns a value. This argument is optional, and the binary predicate less<T> is the default value.
• ✅ Alloc: Type of the allocator object which is used to define the storage allocation model.

Declaration and Initialization of Set

In C++, we can declare the set using <set> header file and initialized with the std::set container.

Syntax

It has the following syntax:

#include <set>   // Required for using set

std::set<data_type> set_name;

C++ declaration and initialization of Set Example

Let us take an example to illustrate how to declare and initialize a set in C++.

Example

#include <iostream>

#include <set>  //using set header

using namespace std;  //using standard namespace

int main() {  //main function

    

    // Creating a set of integers

    set<int> val = {8, 6, 7, 3, 9};

    

    for (auto a : val)

        cout << a << " ";

    return 0;

}

Output:

3 6 7 8 9

Explanation:

In this example, we have taken a set of integers named val is created and initialized with values {8, 6, 7, 3, 9}. After that, the set automatically stores the elements in sorted order and removes any duplicates. The for loop prints each element in ascending order.

Operations of the Set

Although there are several operations are performed on a set in C++. Some of them are as follows:

1) Insert Elements

In C++, the insert function is used to insert elements in the set. The insert or emplace operations are used to insert the elements and if we try to insert an already existing element in the set, it will not get inserted. Moreover, we are not allowed to specify the insertion position as it is automatically taken care of at the time of sorting order.

C++ Insertion Elements Example

Let us take an example to illustrate how to insert elements in a set in C++.

Example

#include <iostream>

#include <set>  //using set header

using namespace std;  //using standard namespace

int main() {  //main function

    set<int> a = {1, 3, 5};

    

    // Insert elements into set

    a.insert(8);

    a.emplace(9);

    a.insert(7);

    a.emplace(4);

    

    for (auto x: a) cout << x << " ";

    return 0;

}

Output:

1 3 4 5 7 8 9

Explanation:

In this example, we have taken a set named a is initialized with {1, 3, 5}, and additional elements are added using insert and emplace. After that, the set stores all elements in sorted and unique order, so the output prints the elements in ascending order.

2) Accessing Elements

In the C++ set, we cannot directly access the elements using the index. The begin and end iterators are used to access the elements by their position. Along with these, the next and advance methods can also be used to access the set elements.

C++ Accessing Elements Example

Let us take an example to illustrate how to access an element in a set in C++.

Example

#include <iostream>

#include <set>  //using set header file

using namespace std;  //using standard namespace

int main() {  //main function

    set<int> a = {1, 7, 4, 8, 5, 9};

a

    // Accessing first element

    auto val1 = a.begin();

    

    // Accessing third element

    auto val2 = next(val1, 2);

    

    cout << *val1 << " " << *val2;

    return 0;

}

Output:

Explanation:

In this example, we initialize a set of integers and access elements using iterators. The begin function gives the first (smallest) element, and the next (val1, 2) function moves two positions forward to access the third element in sorted order.

3) Finding Elements

In C++, the find function is used to find an element from the set. The find function enables fast search by value operation, and if the searched element is present in the set, it will return the value, else it returns the end iterator.

C++ Finding Elements Example

Let us take an example to illustrate how to find elements in a set in C++.

Example

#include <iostream>

#include <set>  //using set header file

using namespace std;  //using standard namespace

int main() {   //main function

    set<int> a = {2, 5, 8, 3, 7, 4};

    // Find the selected element

    auto it = a.find(8);

    

    if (it != a.end()) cout << *it;

    else cout << "Element not Found in the set";

    return 0;

}

Output:

Explanation:

In this example, we demonstrate how to search for an element in a set using the find function. It looks for element 8 in the set and prints it if found; otherwise, it displays a message, which indicates that the element is not present.

4) Traversing Elements

In C++, the begin and end iterators are used to traverse or iterate the set with the help of for loops, which are based on range.

C++ Traversing Elements Example

Let us take an example to illustrate how to traverse elements in a set in C++.

Example

#include <iostream>

#include <set>  //using set header file

using namespace std;  //using standard namespace

int main() {  //main function

    set<int> a = {7, 2, 5, 3, 4, 8};

    

    // Traversing using range based for loop

    for(auto val = a.begin(); val != a.end(); val++)

        cout << *val << " ";

    return 0;

}

Output:

2 3 4 5 7 8

Explanation:

In this example, we use a set<int> to store unique integers in sorted order. After that, it traverses the set using an iterator (val) and prints each element.

5) Deleting Elements

In C++, the erase method is used to remove elements from a set either by value or by position.

C++ Deleting Elements Example

Let us take an example to illustrate how to delete elements in a set in C++.

Example

#include <iostream>

#include <set>  //using set header file

using namespace std;  //using standard namespace

int main() {  //main function

    set<int> a = {5, 7, 1, 6, 9, 3};

    

    // Deleting elements by value

    a.erase(9);

    

    // Deleting first element by iterator

    a.erase(a.begin());

    

    for (auto x: a) cout << x << " ";

    return 0;

}

Output:

3 5 6 7 9

Explanation:

In this example, we demonstrate how we can delete elements from a set. After that, it removes the element 9 by value and deletes the first element using an iterator. Finally, it prints the remaining elements in sorted order, as sets automatically maintain ascending order.

Time Complexity for the Basic Operations

The time complexities for the basic operations are as follows :

• ✅ Insert: The time complexity for inserting an element is O(log n).
• ✅ Delete: The time complexity for deleting an element is O(log n).
• ✅ Find: The time complexity for searching an element is O(1).
• ✅ Find by Value: The time complexity for searching an element by value is O(log n).
• ✅ Traverse: The time complexity for traversing elements in a set is O(n).

Member Functions

Below is the list of all member functions of the set in C++:

Constructor/Destructor

The given table shows several constructor/destructor functions that are used in C++ Set.

Iterators

The given table shows several iterator functions that are used in C++ Set.

Capacity

The given table shows several capacity functions that are used in C++ Set.

Modifiers

The given table shows several modifier functions that are used in C++ Set.

Observers

The given table shows several observer functions that are used in C++ Set.

Operations

The given table shows several operations that are performed in C++ Set.

Allocator

The given table shows allocator function that is used in C++ Set.

Non-Member Overloaded Functions

The given table shows several Non-Member Overloaded functions that are used in C++ Set.

Types of Set

There are two types of sets in C++, they are:

1) Ordered Set

In C++, the set that obeys the sorting order when storing elements in a set, these sets are known as the Ordered Sets.

2) Unordered Set

In C++, the set that stores the elements in an arbitrary order; such type of set is known as an Unordered set.

Difference between Ordered Set and Unordered Set

Several differences between ordered set and unordered set in C++ are as follows:

• ✅ An ordered set stores the elements in the set by following the sorting mechanism, which is ascending by default. On the other hand, an unordered set stores the elements in the set by following an arbitrary order.
• ✅ In an ordered set, the operations such as insert, delete, and find operations take the logarithmic O(log n) time complexity to perform the assigned tasks. On the other hand, the unordered set uses the hashing technique when performing any operations such as insert, delete, or accessing the elements, and so it takes O(1) time complexity to perform the assigned tasks.

C++ Sets MCQs

1) Which of the following header file is required to use std::set container in C++?

• ✅ < map >
• ✅ < vector >
• ✅ < set >
• ✅ < unordered_set >

2) What is the time complexity to insert an element into an std:: set in C++?

• ✅ O (n)
• ✅ O (1)
• ✅ O (n log n)
• ✅ O (log n)

3) Select the correct syntax to initialize a std::set with values.

• ✅ Std :: set <int> s = ( 1, 2, 3 );
• ✅ Std:: set <int> s ( 1, 2, 3 );
• ✅ Std:: set <int> s ( 3, 2, 1 );
• ✅ Std :: set <int> s = { 1, 2, 2, 3 };

4) What is the return type of the insert method present in std::set in C++?

• ✅ Pair <iterator, bool>
• ✅ Bool
• ✅ Void
• ✅ Iterator

5) Which of the following is the correct statement about the iterators of a std: set?

• ✅ They allow modification of the elements
• ✅ They point the elements in a sorted order
• ✅ They do not support the ++ operator
• ✅ They can be used to access the elements in reverse order only.