What is an Set?

A set in C++ STL is an associative container that stores a collection of unique elements in sorted order. Each element in the set is unique, and the elements are arranged according to a strict weak ordering criterion. Sets are typically implemented using balanced binary search trees (such as red-black trees), ensuring efficient insertion, deletion, and search operations.

Understanding Set

The unique feature of a set lies in its ability to store only distinct elements. If an element is already present in the set, attempting to insert it again will have no effect. This property makes sets particularly useful for tasks that require handling unique values, such as maintaining a collection of unique identifiers or eliminating duplicates from a dataset.

Syntax

Include the Set Header File:

#include <set>

Declaring a Set:

std::set<T> setName;

Replace T with the type of elements you want to store in the set, and setName with the desired variable name.

Initializing a Set with elements:

std::set<T> setName = {element1, element2, ...};

Set Sorted order in Descending:

By default, the std::set is sorted in ascending order. However, we have the option to change the sorting order by using the following syntax.

std::set <data_type, greater<data_type>> set_name;

Example

#include <iostream>
#include <set>

int main() {
    // Create a set of integers
    std::set<int> mySet;

    // Insert elements into the set
    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(15);
    mySet.insert(20);
    mySet.insert(5); // Duplicate element, will not be inserted

    // Print elements of the set
    std::cout << "Elements of the set: ";
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Check if an element exists in the set
    int elementToFind = 15;
    if (mySet.count(elementToFind)) {
        std::cout << elementToFind << " exists in the set." << std::endl;
    } else {
        std::cout << elementToFind << " does not exist in the set." << std::endl;
    }

    // Erase an element from the set
    mySet.erase(10);

    // Print elements of the set after erasing
    std::cout << "Elements of the set after erasing 10: ";
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Check if the set is empty
    if (mySet.empty()) {
        std::cout << "The set is empty." << std::endl;
    } else {
        std::cout << "The set is not empty." << std::endl;
    }

    // Print the size of the set
    std::cout << "Size of the set: " << mySet.size() << std::endl;

    return 0;
}


// Output
Elements of the set: 5 10 15 20 
15 exists in the set.
Elements of the set after erasing 10: 5 15 20 
The set is not empty.
Size of the set: 3

Characteristics

1. Uniqueness of Elements: One of the primary properties of a set is that it stores unique elements. Duplicate elements are not allowed in a set. When attempting to insert a duplicate element, the insertion operation is simply ignored, ensuring that each element in the set is unique.
2. Ordered Elements: Sets maintain their elements in sorted order. By default, elements are sorted in ascending order according to their values. This sorted nature allows for efficient searching and retrieval of elements using various operations like lower_bound() and upper_bound().
3. Balanced Binary Search Tree Implementation: Internally, sets are often implemented using balanced binary search trees such as red-black trees. These trees ensure that the height of the tree remains balanced, which guarantees efficient insertion, deletion, and search operations with logarithmic time complexity on average.
4. Efficient Searching: Sets provide efficient searching capabilities due to their sorted nature. Searching for an element in a set can be done with a logarithmic time complexity using the find() function. Additionally, functions like lower_bound() and upper_bound() provide iterators to elements based on their values, further enhancing search efficiency.
5. Dynamic Size: Sets have a dynamic size that can grow or shrink dynamically as elements are inserted or erased. This dynamic resizing ensures efficient memory utilization and allows sets to adapt to varying numbers of elements.
6. Iterator Support: Sets support iterators that allow for traversal of elements in sorted order. Iterators can be used to iterate over the elements of the set or to perform various operations like searching, insertion, and deletion.
7. Associative Container: Sets are associative containers that allow for efficient storage and retrieval of elements based on their values. This property makes sets suitable for tasks that require maintaining a collection of unique values or eliminating duplicates from a dataset.
8. Efficient Set Operations: Sets support efficient set operations such as intersection, union, and difference. These operations can be performed between sets using built-in functions like std::set_intersection(), std::set_union(), and std::set_difference(), providing a convenient way to manipulate sets.

Functions

1 insert()

Inserts an element into the set.

std::set<int> mySet;
mySet.insert(10);

Complexity:

• Time Complexity: Logarithmic time O(log n) on average, where n is the number of elements in the set.

2 erase()

Removes specified elements from the set.

std::set<int> mySet = {1, 2, 3};
mySet.erase(2);

Complexity:

• Time Complexity: Logarithmic time O(log n) on average, where n is the number of elements in the set.

3 find()

Searches the set for a specified element.

std::set<int> mySet = {1, 2, 3};
auto it = mySet.find(2);

Complexity:

• Time Complexity: Logarithmic time O(log n), where n is the number of elements in the set.

4 count()

Returns the number of elements with a specific value.

std::set<int> mySet = {1, 2, 2, 3};
int count = mySet.count(2); // count will be 1

Complexity:

• Time Complexity: Logarithmic time O(log n), where n is the number of elements in the set.

5 size()

Returns the number of elements in the set.

std::set<int> mySet = {1, 2, 3};
int setSize = mySet.size(); // setSize will be 3

Complexity:

• Time Complexity: Constant time O(1)

6 empty()

Checks if the set is empty.

std::set<int> mySet = {1, 2, 3};
bool isEmpty = mySet.empty(); // isEmpty will be false

Complexity:

• Time Complexity: Constant time O(1)

7 clear()

Removes all elements from the set.

std::set<int> mySet = {1, 2, 3};
mySet.clear();

Complexity:

• Time Complexity: Linear time O(n), where n is the number of elements in the set.