【STL】unordered

【STL】unordered_set

在 $C$ ++ $11$ 中， $ST L$ 標準庫引入了一個新的標準關聯式容器： $unordered\_set$ （無序集合）。功能和 $se t$ 類似，都用于存儲唯一元素。但是其底層數據結構是哈希表，因此集合中的元素都是無序存儲的，所以增刪查的時間復雜度為 $O (1)$ ，增刪查的效率比 $se t$ 高。

文章目錄

一、unordered_set 的介紹
二、unordered_set 的使用（常用接口）
- 1. 常見構造
- 2. iterator 的使用
- 3. 增刪查
- 4. unordered_multiset
三、unordered_set 的模擬實現
- 1. STL 中的 hash_set 源碼
- 2. unordered_set 的迭代器
- 3. 模擬實現 unordered_set
總結

一、unordered_set 的介紹

前面部分我們已經詳細介紹了 $se t$ 容器，可以參考我的這篇博客：【STL】 $se t$ 。由于 $se t$ 和 $unordered\_set$ 這兩個容器只是底層實現結構不同，其功能高度相似，基本上只要掌握 $se t$ 的用法， $unordered\_set$ 也就會用了。因此，和 $se t$ 相比只有一些性能和使用的差異，這里只介紹其差異部分。

在這里插入圖片描述

$unordered\_set$ 的聲明如下：

template < class Key, 						// unordered_set::key_type/value_typeclass Hash = hash<Key>, 			// unordered_set::hasherclass Pred = equal_to<Key>, 		// unordered_set::key_equalclass Alloc = allocator<Key> 	// unordered_set::allocator_type> class unordered_set;

$Key$ 就是 $unordered\_set$ 底層關鍵字的類型。
$unordered\_set$ 默認要求 $Key$ 支持轉換為整形，如果不支持或者有自己的需求可以自行實現支持將 $Key$ 轉成整形的仿函數傳給第二個模板參數。
$unordered\_set$ 默認要求 $Key$ 支持比較相等，如果不支持或者有自己的需求可以自行實現支持將 $Key$ 比較相等的仿函數傳給第三個模板參數。
$unordered\_set$ 底層存儲數據的內存是從空間配置器申請的，如果需要可以自己實現內存池，傳給第四個參數。

注意：一般情況下，我們都不需要傳后三個模板參數。

$unordered\_set$ 底層是用哈希桶實現，增刪查平均效率是 $O (1)$ ，迭代器遍歷不再有序，為了跟 $se t$ 區分，所以取名 $unordered\_set$ （無序集合）。

二、unordered_set 的使用（常用接口）

$unordered\_set$ 的底層結構是哈希表，因此不支持比較排序，所以細節上根據這一點和 $se t$ 有略微不同，其他都完全類似。這里只給出常用接口，更多詳細信息可以自行查官方文檔： $unordered\_set$ 。

1. 常見構造

構造 $(co n s t r u c t or)$ 函數聲明	接口說明
$unordered\_set()$	無參默認構造
$unordered\_set(const\ unordered\_set\&\ ust)$	拷貝構造
$unordered\_set(InputIterator\ first, InputIterator\ last)$	使用迭代器區間構造
$unordered\_set (initializer\_list<value\_type> il)$	使用 $ini t ia l i zer$ 列表構造

2. iterator 的使用

$i t er a t or$ 的使用	接口說明
$b e g in ()$ $+$ $e n d ()$	$i t er a t or$
$c b e g in ()$ $+$ $ce n d ()$	$const\_iterator$

$unordered\_set$ 的迭代器是一個單向迭代器：iterator -> a forward iterator to const value_type。

在這里插入圖片描述

3. 增刪查

$unordered\_set$ 增刪查	接口說明
$in ser t$	插入 $v a l$ 數據
$er a se$	刪除 $v a l$ 數據
$f in d$	查找 $v a l$ ，返回 $v a l$ 位置的迭代器（沒找到返回 $e n d ()$ ）
$co u n t$	查找 $v a l$ ，返回 $v a l$ 的個數

由于 $unordered\_set$ 不支持比較大小，且容器內元素是無序的，因此就沒有 $lower\_bound$ 和 $upper\_bound$ 接口了。

4. unordered_multiset

$unordered\_multiset$ 和 $m u lt i se t$ 的使用基本完全類似，都支持關鍵值（ $Key$ ）冗余。

和 $m u lt i se t$ 完全類似， $in ser t / f in d / co u n t / er a se$ 都圍繞著支持值冗余有所差異：

$in ser t$ 可以插入相同的值。
如果要查找的 $x$ 有多個值， $f in d$ 會返回第一個迭代器。
$co u n t$ 會返回 $x$ 的實際個數。
$er a se$ 指定值刪除時，會刪除所有的 $x$ 。

三、unordered_set 的模擬實現

1. STL 中的 hash_set 源碼

$SGI-STL\ 30$ 版本是 $C$ ++ $11$ 之前的 $ST L$ 版本，源代碼中沒有 $unordered\_set$ ，因為這個容器是 $C$ ++ $11$ 之后才更新的。但是 $SGI-STL\ 30$ 實現了哈希表，容器的名字是 $hash\_set$ ，它是作為非標準容器（非 $C$ ++ 標準規定必須實現的容器）出現的。

$hash\_set$ ：

$ha s h t ab l e . h$ ：

2. unordered_set 的迭代器

3. 模擬實現 unordered_set

$ha s h t ab l e . h$ ：

$unordered\_set.h$ ：

$t es t . c pp$ ：

總結

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/77991.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/77991.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/77991.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！