C++ sets

---

Introduction

In C++, a set is a container that stores unique elements in a specific order. The std::set is part of the C++ Standard Library and is defined in the <set> header. It is an associative container that does not allow duplicate elements and automatically orders the elements in ascending order (or according to a custom comparator if provided).

Unlike an array or vector, where elements are stored at specific indices, a set uses keys to maintain a collection of unique elements. Operations like insertion, deletion, and lookup in a set are performed in logarithmic time (O(log n)) due to the underlying self-balancing binary search tree (typically a Red-Black Tree).

---

Syntax

To declare a set, the syntax is:

std::set<Type> set_name;

Where:

• Type: The type of the elements in the set (e.g., int, std::string).

You can also provide a custom comparison function to define the order of elements in the set:

std::set<Type, Compare> set_name;

Where:

• Compare is a function or function object that provides a custom comparison of the elements (by default, it sorts in ascending order).

---

Declaring and Initializing a Set

Example 1: Basic Set Declaration

#include <iostream>
#include <set>

int main() {
    // Declare a set that stores integers
    std::set<int> s;

    // Inserting elements into the set
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(20);  // Duplicate elements are ignored

    // Displaying the elements in the set
    for (int elem : s) {
        std::cout << elem << " ";
    }

    return 0;
}

Output:

10 20 30

Explanation:

• The set automatically ignores the duplicate element 20 because a set cannot contain duplicates.
• The elements are displayed in ascending order, which is the default sorting order.

---

Operations on Sets

1. Insert Elements

You can insert elements into a set using the insert() method. If the element is already present, it will not be added again.

s.insert(40);  // Inserts 40 into the set

2. Erase Elements

To remove an element from the set, you can use the erase() method. You can remove an element by value or by iterator.

• Remove by value:

s.erase(20);  // Removes the element with value 20

Remove by iterator:

auto it = s.find(30);
if (it != s.end()) {
    s.erase(it);  // Removes the element at the iterator
}

3. Find Elements

You can check if an element exists in the set using the find() method. It returns an iterator to the element if found or s.end() if the element does not exist.

auto it = s.find(10);
if (it != s.end()) {
    std::cout << "Element found: " << *it << std::endl;  // Output: 10
} else {
    std::cout << "Element not found!" << std::endl;
}

4. Size and Emptiness

You can check the size of the set and whether it is empty using the size() and empty() methods:

std::cout << "Size of set: " << s.size() << std::endl;  // Size of the set
std::cout << "Is the set empty? " << (s.empty() ? "Yes" : "No") << std::endl;  // Check if the set is empty

5. Clear the Set

You can remove all elements from the set using the clear() method:

s.clear();  // Removes all elements from the set

---

Iterating Over a Set

You can iterate over the elements of a set using an iterator or a range-based for loop:

Example 1: Using Iterator

for (auto it = s.begin(); it != s.end(); ++it) {
    std::cout << *it << " ";  // Dereferencing iterator to access value
}

Example 2: Using Range-Based For Loop

for (int elem : s) {
    std::cout << elem << " ";
}

---

Custom Sorting in Sets

By default, the std::set stores elements in ascending order. You can specify a custom sorting order using a comparator function.

Example: Custom Sorting (Descending Order)

#include <iostream>
#include <set>

bool descendingOrder(int a, int b) {
    return a > b;  // Custom comparator for descending order
}

int main() {
    // Create a set with a custom comparator
    std::set<int, bool(*)(int, int)> s(descendingOrder);

    s.insert(10);
    s.insert(30);
    s.insert(20);
    s.insert(40);

    // Display elements in descending order
    for (int elem : s) {
        std::cout << elem << " ";
    }

    return 0;
}

Output:

40 30 20 10

---

Set Operations in Detail

1. Lower Bound and Upper Bound

You can use the lower_bound() and upper_bound() methods to find elements in a set.

• lower_bound(): Returns an iterator to the first element not less than the given key (i.e., the key or the first larger element).
• upper_bound(): Returns an iterator to the first element greater than the given key.

auto lb = s.lower_bound(20);  // Find the first element not less than 20
if (lb != s.end()) {
    std::cout << "Lower bound of 20: " << *lb << std::endl;
}
auto ub = s.upper_bound(20);  // Find the first element greater than 20
if (ub != s.end()) {
    std::cout << "Upper bound of 20: " << *ub << std::endl;
}

2. Count Elements

You can count the occurrences of an element in a set using the count() method. Since sets only store unique elements, the count of any element is either 0 or 1.

if (s.count(20)) {
    std::cout << "20 is in the set" << std::endl;
} else {
    std::cout << "20 is not in the set" << std::endl;
}

---

Advantages of Using std::set

1. Unique Elements: The set automatically ensures that each element is unique, so there are no duplicates.
2. Efficient Searching: Sets use a self-balancing binary search tree (usually a Red-Black Tree), ensuring efficient searching, insertion, and deletion with logarithmic time complexity (O(log n)).
3. Automatic Ordering: The elements in a set are automatically sorted according to the keys, which simplifies data management.
4. Efficient Set Operations: Sets provide efficient support for set operations like union, intersection, and difference when combined with other sets.

---

When to Use std::set

Use a std::set when:

• You need to store a collection of unique elements.
• You want the elements to be automatically ordered.
• You need efficient insertion, removal, and lookup operations.
• You need to perform operations like finding the smallest or largest element, range queries, or set operations like union, intersection, or difference.

---

---