std::unordered_set
Определено в заголовочном файле <unordered_set> | ||
template< class Key, | (1) | (начиная с C++11) |
namespace pmr { template<class Key, | (2) | (начиная с C++17) |
std::unordered_set это ассоциативный контейнер, содержащий набор уникальных объектов типа Key. Поиск, вставка и удаление имеют среднюю постоянную сложность.
Внутри элементы не сортируются в каком-либо определённом порядке, а организованы в сегменты. В какой сегмент помещается элемент, полностью зависит от хеша его значения. Это обеспечивает быстрый доступ к отдельным элементам, поскольку после вычисления хеша он ссылается на точный сегмент, в который помещается элемент.
Элементы контейнера не могут быть изменены (даже неконстантными итераторами), поскольку модификация может изменить хэш элемента и повредить контейнер.
std::unordered_set соответствует требованиям Container, AllocatorAwareContainer, UnorderedAssociativeContainer.
Содержание |
[править]Аннулирование итераторов
| Операция | Аннулируются |
|---|---|
| Все операции только для чтения, swap, std::swap | Никакие |
| clear, rehash, reserve, operator= | Все |
| insert, emplace, emplace_hint | Только если вызывает перехеширование |
| erase | Только на удалённые элементы |
[править]Примечание
- Функции обмена не делают недействительными ни один из итераторов внутри контейнера, но они делают недействительным итератор, отмечающий конец области обмена.
- Ссылки и указатели на данные, хранящиеся в контейнере, становятся недействительными только при удалении этого элемента, даже если соответствующий итератор становится недействительным.
- После присвоения перемещением контейнера, если только поэлементное присваивание перемещением не вызвано несовместимыми аллокаторами, ссылки, указатели и итераторы (кроме итератора вставки в конец) на перемещаемый контейнер остаются действительными, но ссылаются на элементы, которые теперь находятся в *this.
[править]Параметры шаблона
| Этот раздел не завершён Причина: Добавьте описания параметров шаблона. |
[править]Типы элементы
| Тип элемент | Определение |
key_type | Key |
value_type | Key |
size_type | Беззнаковый целочисленный тип (обычно std::size_t) |
difference_type | Знаковый целочисленный тип (обычно std::ptrdiff_t) |
hasher | Hash |
key_equal | KeyEqual |
allocator_type | Allocator |
reference | value_type& |
const_reference | const value_type& |
pointer | std::allocator_traits<Allocator>::pointer |
const_pointer | std::allocator_traits<Allocator>::const_pointer |
iterator | Constant LegacyForwardIterator в value_type |
const_iterator | LegacyForwardIterator в const value_type |
local_iterator | Тип итератора, category, value, difference, pointer и ссылочные типы которого совпадают с типами iterator. Этот итераторможно использовать для итерации по одному сегменту, но не по сегментам. |
const_local_iterator | Тип итератора, category, value, difference, pointer и ссылочные типы которого совпадают с типами const_iterator. Этот итератор можно использовать для итерации по одному сегменту, но не по сегментам. |
node_type(начиная с C++17) | специализация дескриптора узла, представляющая узел контейнера |
insert_return_type(начиная с C++17) | тип, описывающий результат вставки node_type, специализацияtemplate<class Iter, class NodeType>struct/*неопределена*/{ |
[править]Функции-элементы
(C++11) | создаёт unordered_set(public функция-элемент) |
(C++11) | уничтожает unordered_set(public функция-элемент) |
(C++11) | присваивает значения контейнеру (public функция-элемент) |
(C++11) | возвращает связанный аллокатор (public функция-элемент) |
Итераторы | |
(C++11) | возвращает итератор на начало (public функция-элемент) |
(C++11) | возвращает итератор на конец (public функция-элемент) |
Ёмкость | |
(C++11) | проверяет, пуст ли контейнер (public функция-элемент) |
(C++11) | возвращает количество элементов (public функция-элемент) |
(C++11) | возвращает максимально возможное количество элементов (public функция-элемент) |
Модификаторы | |
(C++11) | очищает содержимое (public функция-элемент) |
(C++11) | вставляет элементы или узлы(начиная с C++17) (public функция-элемент) |
(C++23) | вставляет ряд элементов (public функция-элемент) |
(C++11) | создаёт элемент на месте (public функция-элемент) |
(C++11) | создаёт элементы на месте, используя подсказку (public функция-элемент) |
(C++11) | удаляет элементы (public функция-элемент) |
(C++11) | обменивает содержимое (public функция-элемент) |
(C++17) | извлекает узлы из контейнера (public функция-элемент) |
(C++17) | сливает с узлами из другого контейнера (public функция-элемент) |
Просмотр | |
(C++11) | возвращает количество элементов, соответствующих определённому ключу (public функция-элемент) |
(C++11) | ищет элемент с определённым ключом (public функция-элемент) |
(C++20) | проверяет, содержит ли контейнер элемент с определённым ключом (public функция-элемент) |
(C++11) | возвращает диапазон элементов, соответствующих определённому ключу (public функция-элемент) |
Интерфейс сегментов | |
| возвращает итератор на начало указанного сегмента (public функция-элемент) | |
| возвращает итератор на конец указанного сегмента (public функция-элемент) | |
(C++11) | возвращает количество сегментов (public функция-элемент) |
(C++11) | возвращает максимальное количество сегментов (public функция-элемент) |
(C++11) | возвращает количество элементов в конкретном сегменте (public функция-элемент) |
(C++11) | возвращает сегмент для конкретного ключа (public функция-элемент) |
Политика хеширования | |
(C++11) | возвращает среднее количество элементов на сегмент (public функция-элемент) |
(C++11) | управляет максимальным средним количеством элементов на сегмент (public функция-элемент) |
(C++11) | резервирует как минимум указанное количество сегментов и регенерирует хеш-таблицу (public функция-элемент) |
(C++11) | резервирует место по крайней мере для указанного количества элементов и регенерирует хеш-таблицу (public функция-элемент) |
Наблюдатели | |
(C++11) | возвращает функцию, используемую для хэширования ключей (public функция-элемент) |
(C++11) | возвращает функцию, используемую для сравнения ключей на равенство (public функция-элемент) |
[править]Функции, не являющиеся элементами
(удалено в C++20) | сравнивает значения в unordered_set (шаблон функции) |
| специализация алгоритма std::swap (шаблон функции) | |
(C++20) | стирает все элементы, соответствующие определённым критериям (шаблон функции) |
Правила вывода | (начиная с C++17) |
[править]Примечание
Типы элементы iterator и const_iterator могут быть псевдонимами одного и того же типа. Это означает, что определение пары перегруженных функций с использованием этих двух типов в качестве типов параметров может нарушить Правило Одного Определения. Поскольку iterator можно преобразовать в const_iterator, будет работать одна функция с типом параметра const_iterator.
| Макрос тест функциональности | Значение | Стандарт | Комментарий |
|---|---|---|---|
__cpp_lib_containers_ranges | 202202L | (C++23) | Создание и вставка диапазонов для контейнеров |
[править]Пример
#include <iostream>#include <unordered_set> void print(constauto& set){for(constauto& elem : set)std::cout<< elem <<' ';std::cout<<'\n';} int main(){ std::unordered_set<int> mySet{2, 7, 1, 8, 2, 8};// создаёт набор int print(mySet); mySet.insert(5);// помещает элемент 5 в набор print(mySet); if(auto iter = mySet.find(5); iter != mySet.end()) mySet.erase(iter);// удаляет элемент, на который указывает iter print(mySet); mySet.erase(7);// удаляет элемент 7 print(mySet);}
Возможный вывод:
8 1 7 2 5 8 1 7 2 8 1 7 2 8 1 2
[править]Отчёты о дефектах
Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:
| Номер | Применён | Поведение в стандарте | Корректное поведение |
|---|---|---|---|
| LWG 2050 | C++11 | определения reference, const_reference, pointer иconst_pointer были основаны на allocator_type | на основе value_type и std::allocator_traits |
[править]Смотрите также
| коллекция уникальных ключей, отсортированная по ключам (шаблон класса) |
