命名空间
变体
操作

std::unordered_set

来自 cppreference.com
< cpp‎ | 容器
 
 
 
 
定义在头文件 <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 的唯一对象集。搜索、插入和删除的平均时间复杂度为常数。

在内部,元素不会按任何特定顺序排序,而是被组织成桶。元素放置到哪个桶完全取决于其值的哈希值。这使得快速访问单个元素成为可能,因为一旦计算出哈希值,它就会指向元素被放置到的确切桶。

容器元素不能修改(即使是非 const 迭代器),因为修改可能会更改元素的哈希值并破坏容器。

std::unordered_set 满足 容器分配器感知容器无序关联容器 的需求。

内容

[编辑] 迭代器失效

操作 失效
所有只读操作,交换std::swap 从不
清除重新哈希保留operator= 总是
插入放置放置提示 只有在导致重新哈希时
擦除 仅限于被擦除的元素

[编辑] 备注

  • 交换函数不会使容器内的任何迭代器失效,但它们会使标记交换区域末尾的迭代器失效。
  • 即使在相应迭代器失效时,对存储在容器中的数据的引用和指针也只会通过擦除该元素而失效。
  • 在容器移动赋值后,除非元素移动赋值被不兼容的分配器强制执行,否则对移动前容器的引用、指针和迭代器(除了尾部后迭代器)仍然有效,但指向现在位于 *this 中的元素。

[编辑] 模板参数

[编辑] 成员类型

成员类型 定义
key_type Key[edit]
value_type Key[edit]
size_type 无符号整数类型(通常为 std::size_t)[edit]
difference_type 有符号整数类型(通常为 std::ptrdiff_t)[edit]
hasher Hash[edit]
key_equal KeyEqual[edit]
allocator_type Allocator[edit]
reference value_type&[edit]
const_reference const value_type&[edit]
pointer std::allocator_traits<Allocator>::pointer[edit]
const_pointer std::allocator_traits<Allocator>::const_pointer[edit]
iterator 指向 value_type 的常量 LegacyForwardIterator[edit]
const_iterator LegacyForwardIterator 指向 const value_type[edit]
local_iterator 一种迭代器类型,其类别、值、差值、指针和
引用类型与 iterator 相同。此迭代器
可用于遍历单个桶,但不能跨桶遍历[edit]
const_local_iterator 一种迭代器类型,其类别、值、差值、指针和
引用类型与 const_iterator 相同。此迭代器
可用于遍历单个桶,但不能跨桶遍历[edit]
node_type (自 C++17 起) 表示容器节点的 节点句柄 的特化[edit]
insert_return_type (自 C++17 起) 描述插入 node_type 结果的类型,是

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

使用模板参数 iteratornode_type 实例化的。[edit]

[编辑] 成员函数

构造 unordered_set
(公有成员函数) [edit]
析构 unordered_set
(公有成员函数) [edit]
将值赋给容器
(公有成员函数) [edit]
返回关联的分配器
(公有成员函数) [edit]
迭代器
返回指向开头的迭代器
(公有成员函数) [edit]
返回指向结尾的迭代器
(公有成员函数) [edit]
容量
检查容器是否为空
(公有成员函数) [edit]
返回元素数量
(公有成员函数) [edit]
返回最大可能的元素数量
(公有成员函数) [edit]
修改器
清除内容
(公有成员函数) [edit]
插入元素 或节点(自 C++17 起)
(公有成员函数) [edit]
插入一系列元素
(公有成员函数) [edit]
就地构造元素
(公有成员函数) [edit]
使用提示就地构造元素
(公有成员函数) [edit]
擦除元素
(公有成员函数) [edit]
交换内容
(公有成员函数) [edit]
(C++17)
从容器中提取节点
(公有成员函数) [edit]
(C++17)
将节点从另一个容器中拼接到当前容器
(公有成员函数) [edit]
查找
返回与特定键匹配的元素数量
(公有成员函数) [edit]
查找具有特定键的元素
(公有成员函数) [edit]
(C++20)
检查容器是否包含具有特定键的元素
(公有成员函数) [edit]
返回与特定键匹配的元素范围
(公有成员函数) [edit]
桶接口
返回指向指定桶开头的迭代器
(公有成员函数) [edit]
返回指向指定桶结尾的迭代器
(公有成员函数) [edit]
返回桶的数量
(公有成员函数) [edit]
返回桶的最大数量
(公有成员函数) [edit]
返回特定桶中的元素数量
(公有成员函数) [edit]
返回特定键所在的桶
(公有成员函数) [edit]
哈希策略
返回每个桶的平均元素数量
(公有成员函数) [edit]
管理每个桶的最大平均元素数量
(公有成员函数) [edit]
保留至少指定数量的桶并重新生成哈希表
(公有成员函数) [edit]
为至少指定数量的元素保留空间并重新生成哈希表
(公有成员函数) [编辑]
观察者
返回用于对键进行哈希处理的函数
(公有成员函数) [编辑]
返回用于比较键是否相等的函数
(公有成员函数) [编辑]

[编辑] 非成员函数

(C++11)(C++11)(C++20中已移除)
比较 unordered_set 中的值
(函数模板) [编辑]
专门用于 std::swap 算法
(函数模板) [编辑]
删除满足特定条件的所有元素
(函数模板) [编辑]

推导指南

(自 C++17 起)

[编辑] 备注

成员类型 iteratorconst_iterator 可能是同一类型的别名。这意味着使用这两种类型作为参数类型定义一对函数重载可能违反 单定义规则。由于 iterator 可以转换为 const_iterator,因此使用 const_iterator 作为参数类型的单个函数将起作用。

特性测试 Std 特性
__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}; // 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++ 标准。

DR 应用于 已发布的行为 正确行为
LWG 2050 C++11 referenceconst_referencepointer 的定义
const_pointer 基于 allocator_type
基于 value_type
std::allocator_traits

[编辑] 另请参阅

由键哈希的键集合
(类模板) [编辑]
按键排序的唯一键集合
(类模板) [编辑]
(C++23)
调整容器以提供按键排序的唯一键集合
(类模板) [编辑]