Sets in C++

All about sets in C++ programming language!!!

In C++, a set is a container that stores a collection of unique elements. Sets are part of the C++ Standard Library and are defined in the <set> header. Here are some key features and information about sets in C++:

1. Uniqueness: A set ensures that all elements it contains are unique. If you try to insert a duplicate element, it won't be added to the set.

2. Ordered: By default, elements in a set are ordered in ascending order. This order is based on the keys of the elements. If you need an unordered collection of unique elements, you can use std::unordered_set from the <unordered_set> header.

3. Implementation: Sets are typically implemented as binary search trees (BST), such as Red-Black Trees, to ensure efficient insertion, deletion, and search operations. This allows for O(log N) time complexity for these operations.

4. Iterators: You can use iterators to traverse elements in a set in a sorted order.

1. Ordered Set

In C++, an ordered set typically refers to a set data structure where the elements are maintained in a specific order, often in ascending or descending order based on their values. The C++ Standard Library provides std::set for ordered sets and std::multiset for ordered multisets (allowing duplicate elements). Here's how you can use std::set as an ordered set:

#include <iostream>
#include <set>

int main() {
    std::set<int> orderedSet;

    // Insert elements into the ordered set - O(log N) on average
    orderedSet.insert(5);
    orderedSet.insert(2);
    orderedSet.insert(8);
    orderedSet.insert(2); // Duplicate element, will not be added

    // Iterate and print the elements in ascending order - O(N)
    for (const int& element : orderedSet) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // Check if an element exists in the ordered set - O(log N) on average
    int target = 8;
    if (orderedSet.find(target) != orderedSet.end()) {
        std::cout << target << " exists in the ordered set." << std::endl;
    } else {
        std::cout << target << " does not exist in the ordered set." << std::endl;
    }

    // Remove an element from the ordered set - O(log N) on average
    orderedSet.erase(2);

    // Size of the ordered set - O(1)
    std::cout << "Size of the ordered set: " << orderedSet.size() << std::endl;

    return 0;
}

2. Unordered Set

In C++, an unordered set is a container that stores a collection of unique elements, just like a regular set (std::set). However, unlike a set, an unordered set does not maintain the elements in any specific order. Instead, it uses a hashing mechanism to achieve faster average lookup, insertion, and deletion times compared to a regular set.

Here are some key features and information about unordered sets in C++:

1. Uniqueness: Like sets, unordered sets ensure that all elements are unique. If you try to insert a duplicate element, it won't be added to the unordered set.

2. Unordered: Elements in an unordered set are not sorted in any specific order. Their arrangement is determined by the internal hash table.

3. Hashing: Unordered sets use a hash table internally to store elements and quickly locate them during operations. This allows for O(1) average time complexity for these operations, making them highly efficient.

4. Iterators: You can use iterators to traverse elements in an unordered set, but the order in which elements are visited is not guaranteed to be sorted.

Here's a basic example of how to use std::unordered_set in C++:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    // Insert elements into the unordered set - Average: O(1), Worst-case: O(N)
    myUnorderedSet.insert(5);
    myUnorderedSet.insert(2);
    myUnorderedSet.insert(8);
    myUnorderedSet.insert(2); // Duplicate element, will not be added

    // Iterate and print the elements (order not guaranteed) - O(N)
    for (const int& element : myUnorderedSet) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // Check if an element exists in the unordered set - Average: O(1), Worst-case: O(N)
    int target = 8;
    if (myUnorderedSet.find(target) != myUnorderedSet.end()) {
        std::cout << target << " exists in the unordered set." << std::endl;
    } else {
        std::cout << target << " does not exist in the unordered set." << std::endl;
    }

    // Remove an element from the unordered set - Average: O(1), Worst-case: O(N)
    myUnorderedSet.erase(2);

    // Size of the unordered set - O(1)
    std::cout << "Size of the unordered set: " << myUnorderedSet.size() << std::endl;

    return 0;
}

In this example, we create a std::unordered_set called myUnorderedSet and perform various operations like insertion, checking for the existence of elements, and erasing elements. The elements are not sorted in any specific order.

Use std::unordered_set when you need fast average-time complexity for insertion, deletion, and lookup operations and do not require elements to be maintained in any particular order.

3. Multiset

In C++, a std::multiset is a container that stores a collection of elements in a sorted order, allowing duplicate elements. It is part of the C++ Standard Library and is defined in the <set> header. A std::multiset is similar to a std::set, but it allows multiple elements with the same value.

Here are some key features and information about std::multiset:

1. Sorted Order: Like std::set, a std::multiset maintains elements in a sorted order, typically ascending order by default. You can provide a custom sorting criterion by using a comparator if needed.

2. Duplicates Allowed: Unlike std::set, a std::multiset allows duplicate elements. It stores all occurrences of the same value.

3. Efficient Insertion and Removal: std::multiset uses a balanced binary search tree (e.g., Red-Black Tree) internally to ensure efficient insertion, deletion, and search operations. This allows for O(log N) time complexity for these operations.

4. Iterators: You can use iterators to traverse elements in a std::multiset in sorted order, including duplicate elements.

Here's a basic example of how to use std::multiset in C++:

#include <iostream>
#include <set>

int main() {
    std::multiset<int> myMultiset;

    // Insert elements into the multiset - Average: O(log N), Worst-case: O(N)
    myMultiset.insert(5);
    myMultiset.insert(2);
    myMultiset.insert(8);
    myMultiset.insert(2); // Duplicate element, will be added

    // Iterate and print the elements in sorted order - O(N)
    for (const int& element : myMultiset) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    // Check the count of a specific element - O(log N)
    int target = 2;
    int count = myMultiset.count(target);

    // Remove specific occurrences of an element from the multiset - O(log N) per erase operation
    myMultiset.erase(2);

    // Size of the multiset - O(1)
    std::cout << "Size of the multiset: " << myMultiset.size() << std::endl;

    return 0;
}

In this example, we create a std::multiset called myMultiset and insert elements, including duplicate elements. The multiset maintains the elements in sorted order and allows duplicates. You can count and remove specific occurrences of elements.

Use std::multiset when you need to store a collection of elements with duplicates in a sorted order and you want efficient insertion, deletion, and search operations.