std::
unordered_set
类模板 <unordered_set>
template < class Key, // unordered_set::key_type/value_type
class Hash = hash<Key>, // unordered_set::hasher
class Pred = equal_to<Key>, // unordered_set::key_equal
class Alloc = allocator<Key> // unordered_set::allocator_type
> class unordered_set;
无序集合
无序集合是存储没有特定顺序的惟一元素的容器,它允许根据单个元素的值快速检索单个元素。
在 unordered_set 中,一个元素的值与它的键同时存在,从而唯一地标识它。
键是不可变的,因此 unordered_set 中的元素在容器中一次不能修改———但是可以插入和删除它们。
在内部,unordered_set 中的元素没有按照任何特定的顺序排序,而是根据它们的散列值将它们组织到
bucket 中,
从而允许直接通过它们的值快速访问单个元素(平均时间复杂度为常数)。
Unordered_set容器通过键访问单个元素的速度比
set 容器快,但是它们在遍历元素子集的范围迭代时通常效率较低。
容器中的迭代器至少是前向迭代器。
☲ 容器特性
关联
关联容器中的元素是通过键引用的,而不是通过它们在容器中的绝对位置引用的。
无序
无序容器使用哈希表来组织元素,允许通过键快速访问元素。
固定
元素的值也是用来标识它的键。
键唯一
容器中没有两个元素具有相同的键.
分配器
容器使用allocator 对象动态地处理其存储需求。。
☲ 模板参数
Key
元素的类型。unordered_set 容器中的每个元素也是由这个值唯一标识的。
成员类型 unordered_set::key_type 和 unordered_set::value_type 的别名.
Hash
一种一元函数对象类型,它接受一个与元素类型相同的对象作为参数,并基于该对象返回size_t 类型的唯一值。
这可以是实现函数调用操作符的类,也可以是指向函数的指针(参见构造函数的示例)。
默认为 hash<Key> ,它返回一个哈希值,
冲突的概率接近 1.0/std::numeric_limits<size_t>::max() 。
unordered_set 对象使用此函数返回的哈希值在内部组织元素,加快查找单个元素的过程。
成员类型 unordered_set:: hashher 的别名.
Pred
一个二元谓词,接受两个与元素类型相同的参数,并返回布尔值。
表达式pred(a,b) ,其中pred 是该类型的一个对象,a 和b 是键值,
如果a 被认为与b 等价,则返回true 。
这可以是实现函数调用操作符的类,也可以是指向函数的指针(参见构造函数的示例)。
默认为equal_to<Key> ,其返回值与应用 equal-to operator(a==b) 相同。
unordered_set对象使用这个表达式来确定两个元素键是否相等。
unordered_set容器中不能有两个元素的键使用该谓词生成true 。
成员类型 unordered_set::key_equal 的别名。
Alloc
用于定义存储分配模型的 allocator 对象的类型。 默认情况下,
使用 allocator 类模板,它定义了最简单的内存分配模型,并且与值无关。
别名为成员类型 unordered_set::allocator_type .
在unordered_set成员函数的引用中,这些相同的名称(
Key 、
Hash 、
Pred 和
Alloc )被假定为模板形参。
☉ 成员类型
C++11
C++14
C++11:
成员类型
定义
注释
key_type
起始模板参数(Key)
value_type
起始模板参数(Key)
与key_type相同
hasher
第二个模板参数(Hash)
defaults to: hash<key_type>
key_equal
第三个模板参数(Pred)
默认为:equal_to <key_type>
allocator_type
第四个模板参数(Alloc)
默认为:allocator<value_type>
reference
Alloc::reference
const_reference
Alloc::const_reference
pointer
Alloc::pointer
默认分配器:value_type*
const_pointer
Alloc::const_pointer
默认分配器:const value_type*
iterator
指向const value_type的前向迭代器
* 可转换为const_iterator
const_iterator
指向const value_type的前向迭代器
*
local_iterator
指向const value_type的前向迭代器
* 可转换为const_local_iterator
const_local_iterator
指向const value_type的前向迭代器
*
difference_type
一种有符号整型
通常与ptrdiff_t相同
size_type
无符号整型
通常与size_t相同
C++14:
成员类型
定义
注释
key_type
起始模板参数(Key)
value_type
起始模板参数(Key)
与key_type相同
hasher
第二个模板参数(Hash)
defaults to: hash<key_type>
key_equal
第三个模板参数(Pred)
默认为:equal_to <key_type>
allocator_type
第四个模板参数(Alloc)
默认为:allocator<value_type>
reference
value_type&
const_reference
const value_type&
pointer
allocator_traits<Alloc>::pointer
默认分配器:value_type*
const_pointer
allocator_traits<Alloc>::const_pointer
默认分配器:const value_type*
iterator
指向const value_type的前向迭代器
* 可转换为const_iterator
const_iterator
指向const value_type的前向迭代器
*
local_iterator
指向const value_type的前向迭代器
* 可转换为const_local_iterator
const_local_iterator
指向const value_type的前向迭代器
*
difference_type
一种有符号整型
通常与ptrdiff_t相同
size_type
无符号整型
通常与size_t相同
*注意:unordered_set 中的所有迭代器都指向const 元素。
const_ 成员类型是否与非const 成员类型相同取决于特定的标准库实现,
但程序不应该依赖于它们与重载函数的不同:const_iterator 更通用,
因为迭代器总是可以转换为const_iterator 。
这同样适用于local_ 和非local_ 迭代器类型:它们可以是相同的类型,也可以不是,但程序不应该依赖于它们的不同。
☞ 成员函数
迭代器:
begin
返回一个指向unordered_set容器或其中一个桶开头的迭代器 (公众成员函数)
end
返回一个指向unordered_set容器或其中一个桶末尾元素的下一个元素的迭代器 (公众成员函数)
cbegin
返回一个指向unordered_set容器或其中一个桶开头的常量迭代器 (公众成员函数)
cend
返回一个指向unordered_set容器或其中一个桶末尾元素的下一个元素的常量迭代器 (公众成员函数)
容量:
查找元素:
修改器:
查看:
存储桶:
哈希策略:
非成员函数重载: