std::set

Определён в заголовочном файле <set>

Определён в заголовочном файле `<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)	(начиная с C++17)

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)

(начиная с C++17)

std::set — это ассоциативный контейнер, содержащий отсортированное множество уникальных объектов типа Key. Сортировка выполняется с использованием функции сравнения ключей Compare. Операции поиска, удаления и вставки имеют логарифмическую сложность. Множества обычно реализуются в виде красно-чёрных деревьев.

Везде, где стандартная библиотека предъявляет требования Compare, уникальность определяется с помощью отношения эквивалентности. Говоря нестрого, два объекта a и b считаются эквивалентными, если ни один из них не сравнивается как меньший другого: !comp(a, b) && !comp(b, a).

std::set удовлетворяет требованиям Container, AllocatorAwareContainer, AssociativeContainer и ReversibleContainer.

Все функции-члены std::set являются constexpr: объекты std::set можно создавать и использовать при вычислении константного выражения.

Однако определение переменной constexpr std::set обычно приводит к ошибке, поскольку вычисление константного выражения требует освобождения любой динамически выделенной памяти в рамках того же вычисления, чего обычно не происходит с инициализатором std::set.

(начиная с C++26)

Параметры шаблона

Типы-члены

Тип Определение

key_type Key

value_type Key

size_type беззнаковый целочисленный тип (обычно std::size_t)

difference_type знаковый целочисленный тип (обычно std::ptrdiff_t)

key_compare Compare

value_compare Compare

allocator_type Allocator

reference value_type&

const_reference constvalue_type&

pointer

`Allocator::pointer`	(до C++11)
std::allocator_traits<Allocator>::pointer	(начиная с C++11)

const_pointer

`Allocator::const_pointer`	(до C++11)
std::allocator_traits<Allocator>::const_pointer	(начиная с C++11)

iterator Константный LegacyBidirectionalIterator и ConstexprIterator(начиная с C++26) к value_type

const_iterator LegacyBidirectionalIterator и ConstexprIterator(начиная с C++26) к constvalue_type

reverse_iterator std::reverse_iterator<iterator>

const_reverse_iterator std::reverse_iterator<const_iterator>

node_type (начиная с C++17) специализация дескриптора узла, представляющая узел контейнера

insert_return_type (начиная с C++17)

тип, описывающий результат вставки node_type, специализация

template< class Iter, class NodeType >
struct /* unspecified */
{
    Iter     position;
    bool     inserted;
    NodeType node;
};

с аргументами шаблона iterator и node_type.

Функции-члены

(constructor)	создаёт `set` (открытая функция-член)
(destructor)	уничтожает `set` (открытая функция-член)
operator=	присваивает контейнеру значения (открытая функция-член)
get_allocator	возвращает связанный с контейнером распределитель памяти (открытая функция-член)
Итераторы
begincbegin (C++11)	возвращает итератор на начало (открытая функция-член)
endcend (C++11)	возвращает итератор на конец (открытая функция-член)
rbegincrbegin (C++11)	возвращает обратный итератор на начало (открытая функция-член)
rendcrend (C++11)	возвращает обратный итератор на конец (открытая функция-член)
Ёмкость
empty	проверяет, пуст ли контейнер (открытая функция-член)
size	возвращает количество элементов (открытая функция-член)
max_size	возвращает максимально возможное количество элементов (открытая функция-член)
Модификаторы
clear	очищает содержимое (открытая функция-член)
insert	вставляет элементы или узлы(начиная с C++17) (открытая функция-член)
insert_range (C++23)	вставляет диапазон элементов (открытая функция-член)
emplace (C++11)	создаёт элемент на месте (открытая функция-член)
emplace_hint (C++11)	создаёт элементы на месте, используя подсказку (открытая функция-член)
erase	удаляет элементы (открытая функция-член)
swap	обменивает содержимое (открытая функция-член)
extract (C++17)	извлекает узлы из контейнера (открытая функция-член)
merge (C++17)	перемещает узлы из другого контейнера (открытая функция-член)
Поиск
count	возвращает количество элементов с заданным ключом (открытая функция-член)
find	находит элемент с заданным ключом (открытая функция-член)
contains (C++20)	проверяет, содержит ли контейнер элемент с заданным ключом (открытая функция-член)
equal_range	возвращает диапазон элементов с заданным ключом (открытая функция-член)
lower_bound	возвращает итератор на первый элемент, который не меньше заданного ключа (открытая функция-член)
upper_bound	возвращает итератор на первый элемент, который больше заданного ключа (открытая функция-член)
Наблюдатели
key_comp	возвращает функцию сравнения ключей (открытая функция-член)
value_comp	возвращает функцию сравнения ключей объектов типа `value_type` (открытая функция-член)

Функции, не являющиеся членами

operator==operator!=operator<operator<=operator>operator>=operator<=> (удалён в C++20)(удалён в C++20)(удалён в C++20)(удалён в C++20)(удалён в C++20)(C++20)	лексикографически сравнивает значения двух `set` (шаблон функции)
std::swap(std::set)	специализирует алгоритм `std::swap` (шаблон функции)
erase_if(std::set) (C++20)	удаляет все элементы, удовлетворяющие заданному критерию (шаблон функции)

Руководства по выводу типов

(начиная с C++17)

Примечания

Типы-члены iterator и const_iterator могут быть псевдонимами одного и того же типа. Это означает, что определение двух перегрузок функции, использующих эти типы в качестве типов параметров, может нарушить правило одного определения. Поскольку iterator преобразуется к const_iterator, вместо этого можно использовать одну функцию с параметром типа const_iterator.

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
`__cpp_lib_containers_ranges`	`202202L`	(C++23)	Создание и вставка элементов в контейнеры из диапазонов
`__cpp_lib_constexpr_set`	`202502L`	(C++26)	Константный `std::set`

Пример

#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';
}

Вывод:

{ 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 }

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.

DR	Применялся к	Опубликованное поведение	Корректное поведение
LWG 103	C++98	iterator позволяет изменять ключи	iterator сделан константным
LWG 230	C++98	`Key` не требовалось быть CopyConstructible (ключ типа `Key` мог оказаться невозможным для создания)	`Key` также должен быть CopyConstructible

См. также

multiset	коллекция ключей, отсортированных по ключам (шаблон класса)
unordered_set (C++11)	коллекция уникальных ключей, хешированных по ключам (шаблон класса)
flat_set (C++23)	адаптирует контейнер для предоставления коллекции уникальных ключей, отсортированных по ключам (шаблон класса)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/container/set

std::set

Параметры шаблона

Типы-члены

Функции-члены

Итераторы

Ёмкость

Модификаторы