# std::set

> C++ Atlas: `cppatlas.com/w/cpp/container/set` | Source: https://en.cppreference.com/w/cpp/container/set | Domain: Containers | Standards: C++11, C++17, C++20, C++23

std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare.

## Official Specification Summary (cppreference)

```cpp
// Defined in header <set>

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set; // (1)

namespace pmr {
    template<
        class Key,
        class Compare = std::less<Key>
    > using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>;
} // (2) (since C++17)
```

`std::set` is an associative container that contains a sorted set of unique objects of type `Key`. Sorting is done using the key comparison function *Compare*. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as Red–black trees.

Everywhere the standard library uses the *Compare* requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects `a` and `b` are considered equivalent if neither compares less than the other: `!comp(a, b) && !comp(b, a)`.

`std::set` meets the requirements of *Container*, *AllocatorAwareContainer*, *AssociativeContainer* and *ReversibleContainer*.

### Template parameters

> Note: This section is incomplete Reason: Add descriptions of the template parameters.

### Member types

**Type — Definition**

- `key_type`: `Key`
- `value_type`: `Key`
- `size_type`: Unsigned integer type (usually `std::size_t`)
- `difference_type`: Signed integer type (usually `std::ptrdiff_t`)
- `key_compare`: `Compare`
- `value_compare`: `Compare`
- `allocator_type`: `Allocator`
- `reference`: `value_type&`
- `const_reference`: `const value_type&`
- `pointer`: `Allocator::pointer` (until C++11) `std::allocator_traits<Allocator>::pointer` (since C++11)
- `const_pointer`: `Allocator::const_pointer` (until C++11) `std::allocator_traits<Allocator>::const_pointer` (since C++11)
- `iterator`: Constant *LegacyBidirectionalIterator* to `value_type`
- `const_iterator`: *LegacyBidirectionalIterator* to `const value_type`
- `reverse_iterator`: `std::reverse_iterator<iterator>`
- `const_reverse_iterator`: `std::reverse_iterator<const_iterator>`
- `node_type` (since C++17): a specialization of node handle representing a container node
- `insert_return_type` (since C++17): type describing the result of inserting a `node_type`, a specialization of `template<class Iter, class NodeType> struct /*unspecified*/ { Iter position; bool inserted; NodeType node; };` instantiated with template arguments `iterator` and `node_type`.

### Member functions

- (constructor): constructs the `set` (public member function)
- (destructor): destructs the `set` (public member function)
- `operator=`: assigns values to the container (public member function)
- `get_allocator`: returns the associated allocator (public member function)

**Iterators**

- `begin`, `cbegin` (C++11): returns an iterator to the beginning (public member function)
- `end`, `cend` (C++11): returns an iterator to the end (public member function)
- `rbegin`, `crbegin` (C++11): returns a reverse iterator to the beginning (public member function)
- `rend`, `crend` (C++11): returns a reverse iterator to the end (public member function)

**Capacity**

- `empty`: checks whether the container is empty (public member function)
- `size`: returns the number of elements (public member function)
- `max_size`: returns the maximum possible number of elements (public member function)

**Modifiers**

- `clear`: clears the contents (public member function)
- `insert`: inserts elements or nodes (since C++17) (public member function)
- `insert_range` (C++23): inserts a range of elements (public member function)
- `emplace` (C++11): constructs element in-place (public member function)
- `emplace_hint` (C++11): constructs elements in-place using a hint (public member function)
- `erase`: erases elements (public member function)
- `swap`: swaps the contents (public member function)
- `extract` (C++17): extracts nodes from the container (public member function)
- `merge` (C++17): splices nodes from another container (public member function)

**Lookup**

- `count`: returns the number of elements matching specific key (public member function)
- `find`: finds element with specific key (public member function)
- `contains` (C++20): checks if the container contains element with specific key (public member function)
- `equal_range`: returns range of elements matching a specific key (public member function)
- `lower_bound`: returns an iterator to the first element *not less* than the given key (public member function)
- `upper_bound`: returns an iterator to the first element *greater* than the given key (public member function)

**Observers**

- `key_comp`: returns the function that compares keys (public member function)
- `value_comp`: returns the function that compares keys in objects of type `value_type` (public member function)

### Non-member functions

- `operator==`, `operator!=` (removed in C++20), `operator<` (removed in C++20), `operator<=` (removed in C++20), `operator>` (removed in C++20), `operator>=` (removed in C++20), `operator<=>` (C++20): lexicographically compares the values of two `set`s (function template)
- `std::swap(std::set)`: specializes the `std::swap` algorithm (function template)
- `erase_if(std::set)` (C++20): erases all elements satisfying specific criteria (function template)

### Deduction guides (since C++17)

### Notes

The member types `iterator` and `const_iterator` may be aliases to the same type. This means defining a pair of function overloads using the two types as parameter types may violate the One Definition Rule. Since `iterator` is convertible to `const_iterator`, a single function with a `const_iterator` as parameter type will work instead.

| Feature-test macro | Value | Std | Feature |
| --- | --- | --- | --- |
| `__cpp_lib_containers_ranges` | `202202L` | (C++23) | Ranges construction and insertion for containers |

### Example

```cpp
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <string_view>

template<typename T>
std::ostream& operator<<(std::ostream& out, const std::set<T>& set)
{
    if (set.empty())
        return out << "{}";
    out << "{ " << *set.begin();
    std::for_each(std::next(set.begin()), set.end(), [&out](const T& element)
    {
        out << ", " << element;
    });
    return out << " }";
}

int main()
{
    std::set<int> set{1, 5, 3};
    std::cout << set << '\n';

    set.insert(2);
    std::cout << set << '\n';

    set.erase(1);
    std::cout << set << "\n\n";

    std::set<int> keys{3, 4};
    for (int key : keys)
    {
        if (set.contains(key))
            std::cout << set << " does contain " << key << '\n';
        else
            std::cout << set << " doesn't contain " << key << '\n';
    }
    std::cout << '\n';

    std::string_view word = "element";
    std::set<char> characters(word.begin(), word.end());
    std::cout << "There are " << characters.size() << " unique characters in "
              << std::quoted(word) << ":\n" << characters << '\n';
}
```

Output:

```text
{ 1, 3, 5 }
{ 1, 2, 3, 5 }
{ 2, 3, 5 }

{ 2, 3, 5 } does contain 3
{ 2, 3, 5 } doesn't contain 4

There are 5 unique characters in "element":
{ e, l, m, n, t }
```

### Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

| DR | Applied to | Behavior as published | Correct behavior |
| --- | --- | --- | --- |
| LWG 103 | C++98 | iterator allows modification of keys | iterator made constant |
| LWG 230 | C++98 | `Key` was not required to be *CopyConstructible* (a key of type `Key` might not be able to be constructed) | `Key` is also required to be *CopyConstructible* |

### See also

- [`multiset`](https://en.cppreference.com/w/cpp/container/multiset): collection of keys, sorted by keys (class template)
- [`unordered_set`](https://en.cppreference.com/w/cpp/container/unordered_set) (C++11): collection of unique keys, hashed by keys (class template)
- [`flat_set`](https://en.cppreference.com/w/cpp/container/flat_set) (C++23): adapts a container to provide a collection of unique keys, sorted by keys (class template)

---
Attribution: content from https://en.cppreference.com/w/cpp/container/set (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.