std::unordered_set

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

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

std::unordered_set — это ассоциативный контейнер, содержащий набор уникальных объектов типа Key. Поиск, вставка и удаление имеют среднюю постоянную временную сложность.

Внутри контейнера элементы не отсортированы в каком-либо определённом порядке, а сгруппированы по корзинам. Корзина, в которую помещается элемент, полностью зависит от хеш-значения этого элемента. Благодаря этому обеспечивается быстрый доступ к отдельным элементам: после вычисления хеш-значения оно указывает на конкретную корзину, в которую помещён элемент.

Элементы контейнера нельзя изменять (даже с помощью неконстантных итераторов), поскольку изменение элемента может изменить его хеш-значение и повредить контейнер.

std::unordered_set соответствует требованиям Container, AllocatorAwareContainer, UnorderedAssociativeContainer.

Инвалидация итераторов

Примечания

• Функции обмена не инвалидируют итераторы внутри контейнера, но инвалидируют итератор, указывающий на конец области обмена.
• Ссылки и указатели на данные, хранящиеся в контейнере, инвалидируются только при удалении соответствующего элемента, даже если соответствующий итератор инвалидирован.
• После перемещающего присваивания контейнера, если только поэлементное перемещающее присваивание не было вызвано несовместимыми аллокаторами, ссылки, указатели и итераторы (кроме итератора за последним элементом) контейнера-источника остаются действительными, но указывают на элементы, которые теперь находятся в *this.

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

Типы-члены

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

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

Нефункции-члены

Примечания

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

Пример

#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}; // creates a set of ints
    print(mySet);
    
    mySet.insert(5); // puts an element 5 in the set
    print(mySet);
    
    if (auto iter = mySet.find(5); iter != mySet.end())
        mySet.erase(iter); // removes an element pointed to by iter
    print(mySet);
    
    mySet.erase(7); // removes an element 7
    print(mySet);
}

8 1 7 2
5 8 1 7 2
8 1 7 2
8 1 2

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

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

См. также