std::unordered_set
Материал из cppreference.com
<tbody>
</tbody>
| Определено в заголовочном файле <unordered_set>
|
||
template< class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key> > class unordered_set; |
(1) | (начиная с C++11) |
namespace pmr { template< class Key, class Hash = std::hash<Key>, class Pred = std::equal_to<Key> > using unordered_set = std::unordered_set<Key, Hash, Pred, std::pmr::polymorphic_allocator<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, специализация
|
Функции-элементы
(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(const auto& set)
{
for (const auto& 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
|
Смотрите также
| коллекция уникальных ключей, отсортированная по ключам (шаблон класса) |
