std::unordered_set

 

C++

编译器支持

独立和宿主

语言

标准库

标准库头文件

具名要求

特性测试宏 (C++20)

语言支持库

概念库 (C++20)

诊断库

内存管理库

元编程库 (C++11)

通用工具库

容器库

迭代器库

范围库 (C++20)

算法库

字符串库

文本处理库

数值库

日期和时间库

输入/输出库

文件系统库 (C++17)

并发支持库 (C++11)

执行控制库 (C++26)

技术规范

符号索引

外部库

 

容器库

序列

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

hive (C++26)

deque

forward_list (C++11)

list

关联

set

multiset

map

multimap

无序关联

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

适配器

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

视图

span (C++20)

mdspan (C++23)

表格

迭代器失效

成员函数表

非成员函数表

 

std::unordered_set

成员类型
成员函数
unordered_set::unordered_set unordered_set::~unordered_set unordered_set::operator= unordered_set::get_allocator 迭代器 unordered_set::beginunordered_set::cbegin unordered_set::endunordered_set::cend 容量 unordered_set::size unordered_set::max_size unordered_set::empty 修改器 unordered_set::clear unordered_set::erase unordered_set::swap unordered_set::extract (C++17) unordered_set::merge (C++17) unordered_set::insert unordered_set::insert_range (C++23)   unordered_set::emplace unordered_set::emplace_hint	查找 unordered_set::count unordered_set::find unordered_set::contains (C++20) unordered_set::equal_range 桶接口 unordered_set::begin(size_type)unordered_set::cbegin(size_type) unordered_set::end(size_type)unordered_set::cend(size_type) unordered_set::bucket_count unordered_set::max_bucket_count unordered_set::bucket_size unordered_set::bucket 哈希策略 unordered_set::load_factor unordered_set::max_load_factor unordered_set::rehash unordered_set::reserve 观察器 unordered_set::hash_function unordered_set::key_eq
非成员函数
operator==operator!= (until C++20)	std::swap(std::unordered_set) erase_if(std::unordered_set) (C++20)
推导指引 (C++17)

 

定义于头文件 <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)	(since 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)	(since C++17)

std::unordered_set 是一个关联容器，包含一组类型为 Key 的唯一对象。搜索、插入和移除操作平均具有常数时间复杂度。

在内部，元素不以任何特定顺序排序，而是组织成桶（buckets）。元素被放入哪个桶完全取决于其值的哈希值。这允许快速访问单个元素，因为一旦计算出哈希值，它就指向元素所在的精确桶。

容器元素可能无法被修改（即使通过非常量迭代器），因为修改可能会更改元素的哈希值并破坏容器。

std::unordered_set 满足 Container、 AllocatorAwareContainer、 UnorderedAssociativeContainer 的要求。

std::unordered_set 的所有成员函数都是 constexpr：可以在常量表达式的求值中创建和使用 std::unordered_set 对象。 但是，std::unordered_set 对象通常不能是 constexpr，因为任何动态分配的存储都必须在相同的常量表达式求值中释放。

(since C++26)

迭代器失效

操作	失效
所有只读操作、 swap、 std::swap	从不
clear、 rehash、 reserve、 operator=	总是
insert、 emplace、 emplace_hint	仅在引起重哈希时
erase	仅对被移除的元素失效

注释

• swap 函数不会使容器内部的任何迭代器失效，但它们会使标记交换区域末尾的迭代器失效。

• 指向容器中存储的数据的引用和指针仅在移除该元素时失效，即使对应的迭代器失效。

• 在容器移动赋值之后，除非元素级移动赋值被不兼容的分配器强制执行，否则移动后容器的引用、指针和迭代器（past-the-end 迭代器除外）仍然有效，但引用现在位于 *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	常量 LegacyForwardIterator 和 ConstexprIterator(since C++26) 指向 value_type 的迭代器
const_iterator	LegacyForwardIterator 和 ConstexprIterator(since C++26) 指向 const value_type 的迭代器
local_iterator	迭代器类型，其类别、值、差值、指针和 引用类型与 iterator 相同。此迭代器 可用于遍历单个桶，但不能跨桶遍历
const_local_iterator	迭代器类型，其类别、值、差值、指针和 引用类型与 const_iterator 相同。此迭代器 可用于遍历单个桶，但不能跨桶遍历
node_type (since C++17)	一种 node handle 的特化，表示容器节点
insert_return_type (since C++17)	描述插入 node_type 结果的类型，是 template<class Iter, class NodeType> struct /*unspecified*/ {     Iter     position;     bool     inserted;     NodeType node; }; 使用模板参数 iterator 和 node_type 实例化。

成员函数

(构造函数)	构造 unordered_set (public member function)
(析构函数)	析构 unordered_set (public member function)
operator=	为容器赋值 (public member function)
get_allocator	返回关联的分配器 (public member function)
迭代器
begincbegin	返回指向开头的迭代器 (public member function)
endcend	返回指向末尾的迭代器 (public member function)
容量
empty	检查容器是否为空 (public member function)
size	返回元素数量 (public member function)
max_size	返回最大可能元素数量 (public member function)
修改器
clear	清除内容 (public member function)
insert	插入元素 或节点(since C++17) (public member function)
insert_range (C++23)	插入元素范围 (public member function)
emplace	就地构造元素 (public member function)
emplace_hint	使用提示就地构造元素 (public member function)
erase	erases elements (public member function)
swap	交换内容 (public member function)
extract (C++17)	从容器中提取节点 (public member function)
merge (C++17)	从另一个容器拼接节点 (public member function)
查找
count	返回匹配特定键的元素数量 (public member function)
find	查找具有特定键的元素 (public member function)
contains (C++20)	检查容器是否包含具有特定键的元素 (public member function)
equal_range	返回匹配特定键的元素范围 (public member function)
桶接口
begin(size_type)cbegin(size_type)	返回指向指定桶开头的迭代器 (public member function)
end(size_type)cend(size_type)	返回指向指定桶末尾的迭代器 (public member function)
bucket_count	返回桶的数量 (public member function)
max_bucket_count	返回最大桶数量 (public member function)
bucket_size	返回特定桶中的元素数量 (public member function)
bucket	返回特定键的桶 (public member function)
哈希策略
load_factor	返回每个桶的平均元素数 (public member function)
max_load_factor	管理每个桶的最大平均元素数 (public member function)
rehash	预留至少指定数量的桶并重新生成哈希表 (public member function)
reserve	预留至少指定数量的元素的空间并重新生成哈希表 (public member function)
观察器
hash_function	返回用于哈希键的函数 (public member function)
key_eq	返回用于比较键是否相等的函数 (public member function)

非成员函数

operator==operator!= (C++11)(C++11)(removed in C++20)	比较 unordered_set 中的值 (function template)
std::swap(std::unordered_set) (C++11)	特化 std::swap 算法 (function template)
erase_if(std::unordered_set) (C++20)	移除所有满足特定条件的元素 (function template)

推导指引	(since C++17)

注释

成员类型 iterator 和 const_iterator 可能是相同类型的别名。这意味着使用这两种类型作为参数类型定义一对函数重载可能会违反 One Definition Rule。由于 iterator 可转换为 const_iterator，因此使用 const_iterator 作为参数类型的单个函数即可替代。

特性测试 宏	值	Std	特性
__cpp_lib_containers_ranges	202202L	(C++23)	容器的范围构造和插入
__cpp_lib_constexpr_containers	202502L	(C++26)	constexpr std::unordered_set

示例

运行此代码

#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	reference、 const_reference、 pointer 的定义 和 const_pointer 基于 allocator_type	基于 value_type 和 std::allocator_traits

参见

unordered_multiset (C++11)	键的集合，按键哈希 (class template)
set	唯一键的集合，按键排序 (class template)
flat_set (C++23)	适配容器以提供唯一键的集合，按键排序 (class template)