C++ STL Set

In C++, a set is the foundational data structure that organizes distinct elements in a specific order and retains them. These sets are categorized as associative containers, with the individual sorted elements referred to as sorted keys. While it is possible to add or remove these keys, it is not permissible to alter them.

By default, sets arrange keys in ascending order. Sets are a component of the Standard Template Library (STL) provided in C++, where the set class includes beneficial features that enhance the effectiveness of set operations. Since sets rely on the default sorting order for keys and do not employ an indexing system, it is not possible to retrieve keys using their index values.

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 define the set using the <set> header file and initialize it 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's consider a scenario to demonstrate the process of declaring and initializing 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 instance, we have defined a collection of integers called val, which is established and populated with the values {8, 6, 7, 3, 9}. Subsequently, the collection arranges the elements in ascending order and eliminates any repeated values. The for loop displays each element in increasing sequence.

Operations of the Set

While numerous actions can be executed on a set in C++, a few of them include:

1) Insert Elements

In C++, the insert method is employed to add elements to the set. Both insert and emplace functions serve the purpose of adding elements, and attempting to insert a duplicate element will not result in a new entry. Additionally, the insertion position cannot be specified, as it is managed automatically based on the sorting order.

C++ Insertion Elements Example

Let's consider an instance to demonstrate the process of adding elements to 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 instance, a set called 'a' is created with {1, 3, 5}, and new elements are inserted using both insert and emplace methods. Subsequently, the set organizes all items in a sorted and distinct manner, resulting in the display of elements in ascending sequence.

2) Accessing Elements

In the C++ set container, direct element access via index is not supported. To retrieve elements based on their position, the begin and end iterators are employed. Additionally, the next and advance functions offer alternative ways to access elements within the set.

C++ Accessing Elements Example

Let's consider a scenario to demonstrate the process of accessing an item within a set in the C++ programming language.

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 instance, we set up a collection of integer values and retrieve them utilizing iterators. The start method provides access to the initial (lowest) element, while the proceed (val1, 2) method advances two positions to reach the third element in ascending sequence.

3) Finding Elements

In C++, the find method is employed to locate an element within the set. This function facilitates quick retrieval based on a specific value, and if the desired element exists in the set, it will provide the value; otherwise, it will return the end iterator.

C++ Finding Elements Example

Let's consider an example to demonstrate how to locate elements within 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 instance, we illustrate the process of locating an item within a set by employing the find method. The function searches for the element 8 within the set, and if it is located, the element is printed; if not, a message is shown indicating that the element is absent.

4) Traversing Elements

In C++, the start and finish iterators are employed to navigate or loop through the set using for loops, which rely on range iteration.

C++ Traversing Elements Example

Let's consider a scenario to demonstrate how to iterate through elements in a set using 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 instance, a set<int> is employed to maintain a collection of distinct integers arranged in a sorted manner. Subsequently, it iterates through the set utilizing an iterator (val) to display each individual element.

5) Deleting Elements

In C++, the erase function is employed to eliminate elements from a set based on either their value or position.

C++ Deleting Elements Example

Let's consider a scenario to demonstrate the process of removing elements from 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 instance, we illustrate the process of eliminating elements from a set. Subsequently, the element with a value of 9 is eliminated, and the initial element is removed using an iterator. Ultimately, the set displays the remaining elements in a sorted manner, as sets inherently uphold ascending sequence.

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 are all the member functions available for sets in C++:

Constructor/Destructor

The provided table displays various constructor and destructor functions utilized in C++ Set operations.

Iterators

The provided table displays various iterator functions commonly utilized in C++ Set.

Capacity

The provided table displays various capacity functions utilized in C++ Set.

Modifiers

The provided table displays various modifier functions utilized in C++ Set.

Observers

The provided table displays various observer functions utilized in C++ Set.

Operations

The provided table displays various operations carried out in a C++ Set.

Allocator

The provided table displays the allocator function utilized in C++ Set.

Non-Member Overloaded Functions

The provided table displays various Overloaded functions for non-members that are utilized in C++ Set.

Types of Set

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

1) Ordered Set

In C++, sets that maintain the order of elements based on a defined sorting criterion are referred to as Ordered Sets.

2) Unordered Set

In C++, the set that organizes elements in a random sequence is referred to as an Unordered set.

Difference between Ordered Set and Unordered Set

An ordered set arranges elements based on a specified sorting order, typically ascending by default. Conversely, an unordered set stores elements in a random order.

When working with an ordered set, operations like insert, delete, and find require a time complexity of O(log n) due to the sorting mechanism. In contrast, an unordered set employs hashing for operations such as insert, delete, or element access, resulting in a time complexity of O(1).

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.

b) They direct the elements in an organized sequence