C++ STL unordered_set

75 阅读 0 评论 50 点赞

我是靠谱客的博主高贵鲜花，这篇文章主要介绍C++ STL unordered_set，现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
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 里的元素是不可以被修改，不过他们可以被插入和删除。

稍微翻译一下：

复制代码

1
2
3
4
5
6
7
8
9
10
template < class Key,
// 键类型或者值的类型
class Hash = hash<Key>,
// 哈希函数，一元函数
class Pred = equal_to<Key>,
// 判断相等的函数
class Alloc = allocator<Key>
// 分配器类型
> class unordered_set;

好像一般情况下，只需要关心 Key，也就是元素的类型。以下是四个参数详解。

1、Key
元素的类型，每个元素能被它的值唯一定位。

2、Hash

A unary function object type that takes an object of the same type as the elements as argument and returns a unique value of type size_t based on it.（出自：C++ Reference）

一种一元函数对象类型，它将元素类型相同的对象作为参数，并根据它返回类型为 size_t 的唯一值。

unary adj. 一元的
argument n. 参数
size_t 是一个无符号的整数类型，以字节为单位表示大小

可以理解为hash函数，返回类型是 size_t。

PS：标准库为 string 类型对象提供了一个 hash 函数，即：Murmur hash

3、Pred

A binary predicate that takes two arguments of the same type as the elements and returns a bool.（出自：C++ Reference）

将两个相同元素类型作为二元谓词的参数，然后返回一个布尔类型值。

例如 Pred (a, b)，如果 a 等于 b，就返回 true，不等则返回 false。其实就是判断两个元素是否相等。在 unordered_set 中，不会有两个元素进行这样的判断时会返回 true。（因为元素唯一存在嘛）

4、Alloc

Type of the allocator object used to define the storage allocation model.（出自：C++ Reference）

用于定以存储分配模型的分配对象的类型。（其实我不知道是啥意思）

常用操作：

1、定义一个 string 类型的 unordered_set 为 hash：

复制代码

1
2
unordered_set<string> hash;

2、在 hash 中插入 s：

复制代码

1
2
hash.insert(s);

3、在 hash 中删除 s：

复制代码

1
2
hash.erase(s);

4、hash 中元素个数：

复制代码

1
2
n = hash.size();

5、取第一个元素、最后一个元素（指针类型），顺序是按照哈希函数之后的顺序：

复制代码

1
2
3
4
5
6
7
first = hash.begin();
// 第一个元素的地址
last = hash.end();
// 最后一个元素的地址
std::cout << *first << endl;
// 输出第一个元素

Example

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// unordered_set::begin/end example
#include <iostream>
#include <string>
#include <unordered_set>
int main ()
{
std::unordered_set<std::string> myset =
{"Mercury","Venus","Earth","Mars","Jupiter","Saturn","Uranus","Neptune"};
// 按照哈希函数之后的顺序，把每个元素都输出
std::cout << "myset contains:";
for ( auto it = myset.begin(); it != myset.end(); ++it )
std::cout << " " << *it;
std::cout << std::endl;
// bucket 是“桶”的意思。元素经过了哈希函数之后，会分别放到了每个“桶”中去。
// 以下就是分别输出每个“桶”存放的元素
std::cout << "myset's buckets contain:n";
for ( unsigned i = 0; i < myset.bucket_count(); ++i) {
std::cout << "bucket #" << i << " contains:";
for ( auto local_it = myset.begin(i); local_it!= myset.end(i); ++local_it )
std::cout << " " << *local_it;
std::cout << std::endl;
}
return 0;
}

输出结果

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
myset contains: Venus Jupiter Neptune Mercury Earth Uranus Saturn Mars
myset's buckets contain:
bucket #0 contains:
bucket #1 contains: Venus
bucket #2 contains: Jupiter
bucket #3 contains:
bucket #4 contains: Neptune Mercury
bucket #5 contains:
bucket #6 contains: Earth
bucket #7 contains: Uranus Saturn
bucket #8 contains: Mars
bucket #9 contains:
bucket #10 contains: