> For the complete documentation index, see [llms.txt](https://codexpress.gitbook.io/welcome-to-codexpress/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://codexpress.gitbook.io/welcome-to-codexpress/data-structures/c++-stl-ds/sets-in-c++.md).

# Sets in C++

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 &#x20;

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:

```cilkcpp
#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&#x20;

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++:

```cpp
#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&#x20;

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++:

```cpp
#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.