C++11引入的STL中的unordered系列關聯(lián)式容器
更新時間：2025年10月03日 09:32:55 作者：oi嘉菲貓
STL中的unordered系列容器是C++11引入的基于哈希表實現(xiàn)的關聯(lián)式容器,STL unordered系列容器基于哈希表,支持快速查找但遍歷效率低,適用于無序場景；樹形容器基于紅黑樹,有序且性能穩(wěn)定,適用于需要有序的場景
STL中的unordered系列容器是C++11引入的基于哈希表實現(xiàn)的關聯(lián)式容器，與傳統(tǒng)的紅黑樹實現(xiàn)的關聯(lián)容器(map/set)相比，它們在元素存儲和訪問機制上有顯著差異
1.補充認識
STL中的unordered系列容器的底層就是哈希表，包括unordered_set、unordered_map、unordered_multiset、unordered_multimap四個。
底層哈希原理
補充：從底層來說應該分別類似的命名為tree_map和hash_map，也就是樹形結構和哈希結構的，但是由于map之類的出來的早，后面的為了對應就把hash實現(xiàn)的命名為unordered_xx。
2.unordered_set
2.1容器原型
- unordered_set是存儲key鍵值的關聯(lián)式容器，其允許通過keys快速的索引到與其對應的value。
- 在unordered_set中，鍵值通常用于惟一地標識元素。
- 在內(nèi)部,unordered_set沒有對kye按照任何特定的順序排序, 為了能在常數(shù)范圍內(nèi)找到key，unordered_set將相同哈希值的鍵值放在相同的桶中。
- unordered_set容器通過key訪問單個元素要比set快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
- 它的迭代器至少是前向迭代器。
2.2常用接口
3.unordered_multiset
和set與multiset的區(qū)別一樣，unordered_multiset相對于unordered_set支持相同關鍵碼的存放。
接口區(qū)別：
4.unordered_map
4.1容器原型
- unordered_map是存儲<key, value>鍵值對的關聯(lián)式容器，其允許通過keys快速的索引到與其對應的value。
- 在unordered_map中，鍵值通常用于惟一地標識元素，而映射值是一個對象，其內(nèi)容與此鍵關聯(lián)。鍵和映射值的類型可能不同。
- 在內(nèi)部,unordered_map沒有對<kye, value>按照任何特定的順序排序, 為了能在常數(shù)范圍內(nèi)找到key所對應的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。
- unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
- unordered_maps實現(xiàn)了直接訪問操作符(operator[])，它允許使用key作為參數(shù)直接訪問value。
- 它的迭代器至少是前向迭代器。
4.2常用接口
與unordered_set相比，unordered_map就是鍵值對KV模型，并且提供了[]重載和at接口，這兩個與map相似功能。
其他接口功能與unordered_set相同。
5.unordered_multimap
unordered_multimap和unordered_map的區(qū)別就是unordered_multiset和unordered_multiset的區(qū)別。
另外就是unordered_multimap不支持[]和at。
6.樹形關聯(lián)容器和哈希關聯(lián)容器的對比
特性 | 哈希容器 | 樹形容器 |
底層結構 | 哈希表（順序表+順序表/紅黑表） | 紅黑樹（平衡二叉搜索樹） |
元素順序 | 無序 | 有序 |
平均時間復雜度 | O(1) | O(log_2 N) |
最壞時間復雜度 | O(N)（所有元素都沖突，實際幾乎不可能） | O(log_2 N) |
迭代器 | 單向迭代器 | 雙向迭代器 |
關鍵特性 | 增刪查改都很快，遍歷較慢。性能依賴哈希函數(shù)。 | 插入后自然有序。 |
適用場景 | 快速查找，不關注順序。 | 需要元素有序。 |
小總結：除非有有序的要求，不然都可以先考慮哈希容器。
7.unordered系列模擬實現(xiàn)
7.1重要補充
1）具體存放什么數(shù)據(jù)類型應該是set和map層面決定的，底層的哈希表只是存放數(shù)據(jù)，所以需要一個從存放數(shù)據(jù)提取關鍵碼的KeyOfT反函數(shù)。
2）另外還需要一個哈希函數(shù)來處理不能直接取模的情況。
3）哈希表的迭代器迭代邏輯：單鏈表迭代+順序表的哈希桶迭代。
4）如果使用自定義類型取作為樹形關聯(lián)容器的關鍵碼的話，需要提供一個小于比較仿函數(shù)，有了小于也就有了大于和等于。
5）如果使用自定義類型取作為哈希關聯(lián)容器的關鍵碼的話，需要提供一個等于比較仿函數(shù)。
6）set的迭代器無論是普通迭代器還是const迭代器在底層都是使用const迭代器。
7.2代碼
源碼
7.2.1哈希表
#pragma once
#include <iostream>
// 使用哈希桶解決哈希表的哈希沖突
#include <vector>
#include <utility>
using namespace std;
namespace lbq
{
// 將輸入轉成整型的哈希函數(shù)
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
// 針對常用的字符串類型的特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& str)
{
size_t ret = 0;
for(auto& ele : str)
{
ret = ret * 131 + ele;
}
return ret;
}
};
// 哈希桶具體存儲的數(shù)據(jù)類型
// 實際為一個單鏈表節(jié)點
template<class T>
struct _HashNode
{
T _data;
_HashNode<T>* _next;
_HashNode(const T& data)
: _data(data)
, _next(nullptr)
{}
};
// 哈希表的迭代器，其實是順序表迭代+鏈表迭代
template<class K, class T, class KeyOfT, class Hash > class HashTable; // 迭代器中需要訪問，提前聲明
template<class K, class T, class KeyOfT, class Hash>
struct _HashTableIterator
{
typedef _HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef _HashTableIterator<K, T, KeyOfT, Hash> Iterator;
Node* _node;
HT* _ht;
_HashTableIterator(Node* node, HT* ht)
: _node(node)
, _ht(ht)
{}
bool operator==(const Iterator& it)const
{
return _node == it._node;
}
bool operator!=(const Iterator& it)const
{
return _node != it._node;
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &(_node->_data);
}
Iterator operator++()
{
if(_node->_next != nullptr)
{
_node = _node->_next;
}
else
{
// 找下一個桶的位置
size_t table_index = Hash()(KeyOfT()(_node->_data)) % _ht->_table.size();
while(++table_index < _ht->_table.size())
{
if(_ht->_table[table_index] != nullptr)
{
_node = _ht->_table[table_index];
break;
}
}
// 如果后面已經(jīng)沒有桶了
if(table_index == _ht->_table.size())
{
_node = nullptr;
}
}
return *this;
}
Iterator operator++(int)
{
Iterator tmp(_node, _ht);
operator++();
return tmp;
}
};
// 使用除留余數(shù)法作為哈希表的哈希函數(shù)，使用哈希桶解決沖突
// K：關鍵碼數(shù)據(jù)類型
// T：存儲的數(shù)據(jù)類型，Key或者pair<K, V>
// KeyOfT：從存儲的數(shù)據(jù)中提取關鍵碼
// Hash：將關鍵碼轉成整型用于取模運算
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
private:
typedef _HashNode<T> Node;
friend struct _HashTableIterator<K, T, KeyOfT, Hash>;
public:
typedef _HashTableIterator<K, T, KeyOfT, Hash> iterator;
iterator begin()
{
for(size_t i = 0; i < _table.size(); i++)
{
if(_table[i] != nullptr)
{
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
//HashTable()
//{
// _table.resize(10, nullptr);
// _sz = 0;
//}
~HashTable()
{
for(size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while(cur != nullptr)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
pair<iterator, bool> insert(const T& data)
{
Hash hash;
KeyOfT kot;
iterator find_it = find(kot(data));
if(find_it != end())
{
// 已經(jīng)存在相同的元素
return make_pair(find_it, false);
}
if(_table.size() == 0 || _sz == _table.size())
{
// 順序表為空，或者載荷因子大于1時增容
size_t new_size = _table.size() == 0 "h14">7.2.2unordered_set#pragma once
// hash set模擬實現(xiàn)
#include "hashtable.hpp"
namespace lbq
{
template<class K, class Hasher = HashFunc<K>>
class unordered_set
{
private:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef HashTable<K, K, SetKeyOfT, Hasher> HT;
public:
typedef typename HT::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
bool empty()
{
return _ht.empty();
}
size_t size()
{
return _ht.size();
}
iterator find(const K& key)
{
return _ht.find(key);
}
size_t count(const K& key)
{
return _ht.count(key);
}
pair<iterator, bool> insert(const K& key)
{
return _ht.insert(key);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
size_t bucket_count()
{
return _ht.bucket_count();
}
size_t bucket_size(size_t n)
{
return _ht.bucket_size(n);
}
private:
HT _ht;
};
}7.2.3unordered_map
#pragma once
// unorder_map 模擬實現(xiàn)
#include "hashtable.hpp"
namespace lbq
{
template<class K, class V, class Hasher = HashFunc<K>>
class unordered_map
{
private:
typedef pair<K, V> T;
struct MapKeyOfT
{
const K& operator()(const T& kv)
{
return kv.first;
}
};
typedef HashTable<K, T, MapKeyOfT, Hasher> HT;
public:
typedef typename HT::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
size_t size()
{
return _ht.size();
}
bool empty()
{
return _ht.empty();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key)
{
return _ht.find(key);
}
size_t count(const K& key)
{
return _ht.count(key);
}
pair<iterator, bool> insert(const T& kv)
{
return _ht.insert(kv);
}
bool erase(const K& key)
{
return _ht.erase(key);
}
size_t bucket_count()
{
return _ht.bucket_count();
}
size_t bucket_size(const size_t& n )
{
return _ht.bucket_size(n);
}
private:
HT _ht;
};
}到此這篇關于C++11引入的STL中的unordered系列關聯(lián)式容器的文章就介紹到這了,更多相關C++的STL中的unordered容器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
大家好，本篇文章主要講的是C++類和對象之多態(tài)詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
這篇文章主要給大家介紹了關于VC++6.0實現(xiàn)直線掃描轉換的相關資料,文中通過圖文將實現(xiàn)的步驟一步步介紹的非常詳細,對大家學習或者使用VC++6.0具有一定的參考學習價值,需要的朋友可以參考下2023-01-01
這篇文章主要介紹了C++ sizeof的相關資料，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
C語言 以數(shù)據(jù)塊的形式讀寫文件詳解及實現(xiàn)代碼
本文主要介紹 C語言 以數(shù)據(jù)塊的形式讀寫文件，這里對相關知識資料做了整理，并附代碼示例，以便大家學習參考，有學習此部分知識的朋友可以參考下2016-08-08
這篇文章主要介紹了CLion安裝、漢化、激活、配置圖文詳解,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
C++中strlen(),sizeof()與size()的區(qū)別
本文主要介紹了C++中strlen(),sizeof()與size()的區(qū)別，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
c/c++ 利用sscanf進行數(shù)據(jù)拆分操作
這篇文章主要介紹了c/c++ 利用sscanf進行數(shù)據(jù)拆分操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要給大家介紹了關于c++中為什么不提倡使用vector的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用c++具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-08-08
這篇文章主要介紹了C++實現(xiàn)移動立方體，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧2022-12-12
這篇文章主要為大家詳細介紹了C++實現(xiàn)掃雷、排雷小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05