c++ unordered_set

unordered_set

可直译为“无序 set 容器”，即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
本质是使用hash散列的方式存储数据，是一种使用hash值作为key的容器，所以当有频繁的搜索、插入和移除拥有常数时间。
unordered_set存储原理是声明一个有n个桶的数据结构，计算加入到unordered_set的新的值hash，然后计算hash%n后的值x，将新的值加入到桶x中。当桶x中已经有了元素，就直接链接在后边。当数据结构中的元素满足一定数量时需要扩充桶的数量，并重新构建桶结构。

特点

1. unordered_set是一种容器，它以不特定的顺序存储唯一的元素，并允许根据元素的值快速检索单个元素。
2. 在unordered_set中，元素的值同时是唯一标识它的键。键是不可变的，只可增删，不可修改。
3. 在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织成桶（一个线性链表代表一个桶），从而允许通过它们的值直接快速访问单个元素（平均时间复杂度为常数）。
4. unordered_set容器比set容器更快地通过它们的键访问单个元素，尽管它们在元素子集的范围迭代中通常效率较低。
5. 容器中的迭代器只能是正向迭代器。

基本使用

初始化

调用 unordered_set 模板类的默认构造函数，可以创建空的 unordered_set 容器

std::unordered_set<std::string> uset;
1

创建 unordered_set 容器的同时，可以完成初始化操作

std::unordered_set<std::string> c{ "aaa", "bbb", "ccc" }
1

调用 unordered_set 模板中提供的复制（拷贝）构造函数，将现有 unordered_set 容器中存储的元素全部用于为新建 unordered_set 容器初始化

std::unordered_set<std::string> uset2(uset);
1

以右值引用的方式，利用临时 unordered_set 容器中存储的所有元素，给新建容器初始化

//返回临时 unordered_set 容器的函数
std::unordered_set <std::string> retuset() {
    std::unordered_set<std::string> tempuset{ "aaa", "bbb", "ccc" };
    return tempuset;
}
//调用移动构造函数，创建 uset 容器
std::unordered_set<std::string> uset(retuset());
1
2
3
4
5
6
7

使用 unordered_set 类模板提供的迭代器，在现有 unordered_set 容器中选择部分区域内的元素，为新建 unordered_set 容器初始化

//传入 2 个迭代器，
std::unordered_set<std::string> uset2(++uset.begin(),uset.end());
1
2

添加元素

c.insert("dddd")：向容器添加元素”dddd"

a.insert({ "aaa","bbbb","cccc" })：向容器添加元素"aaa","bbbb","cccc"

a.insert(b.begin(), b.end())：b是一个存储着和a相同类型元素的向量，可将b中所有元素添加到a中
1
2
3
4
5

查找元素

a.find("eeee")：查找元素"eeee"，返回结果为a.end()则表明没有找到，否则返回所对应元素

a.count("eeee")：查找元素"eeee"在a中有几个（由于unordered_set中没有相同的元素，所以结果通常为0或1）
1
2
3

查找桶接口

a.bucket_count()：返回数据结构中桶的数量

a.bucket_size(i)：返回桶i中的大小

a.bucket(“eeee")：返回元素"eeee"在哪个桶里
1
2
3
4
5

观察器

a.hash_function()("aaa")：返回"aaa"所对应的hash值；

a.key_eq()("aaa","aaaa") ：当元素相同时返回true，否则返回false。
1
2
3

清除元素

a.clear()：清除a中所有元素；

a.erase("aaa")：清除元素"aaa"。
1
2
3

统计函数

a.size()：返回a中总的元素个数；

a.max_size()：返回a中最大容纳元素；

a.empty()：判断a中是否为空
1
2
3
4
5

方法列表