C++11引入的STL中的unordered系列關聯(lián)式容器
更新時間：2025年10月03日 09:32:55 作者：oi嘉菲貓
STL中的unordered系列容器是C++11引入的基于哈希表實現的關聯(lián)式容器,STL unordered系列容器基于哈希表,支持快速查找但遍歷效率低,適用于無序場景；樹形容器基于紅黑樹,有序且性能穩(wěn)定,適用于需要有序的場景
STL中的unordered系列容器是C++11引入的基于哈希表實現的關聯(lián)式容器，與傳統(tǒng)的紅黑樹實現的關聯(lián)容器(map/set)相比，它們在元素存儲和訪問機制上有顯著差異
1.補充認識
STL中的unordered系列容器的底層就是哈希表，包括unordered_set、unordered_map、unordered_multiset、unordered_multimap四個。
底層哈希原理
補充：從底層來說應該分別類似的命名為tree_map和hash_map，也就是樹形結構和哈希結構的，但是由于map之類的出來的早，后面的為了對應就把hash實現的命名為unordered_xx。
2.unordered_set
2.1容器原型
- unordered_set是存儲key鍵值的關聯(lián)式容器，其允許通過keys快速的索引到與其對應的value。
- 在unordered_set中，鍵值通常用于惟一地標識元素。
- 在內部,unordered_set沒有對kye按照任何特定的順序排序, 為了能在常數范圍內找到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中，鍵值通常用于惟一地標識元素，而映射值是一個對象，其內容與此鍵關聯(lián)。鍵和映射值的類型可能不同。
- 在內部,unordered_map沒有對<kye, value>按照任何特定的順序排序, 為了能在常數范圍內找到key所對應的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。
- unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
- unordered_maps實現了直接訪問操作符(operator[])，它允許使用key作為參數直接訪問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) |
迭代器 | 單向迭代器 | 雙向迭代器 |
關鍵特性 | 增刪查改都很快，遍歷較慢。性能依賴哈希函數。 | 插入后自然有序。 |
適用場景 | 快速查找，不關注順序。 | 需要元素有序。 |
小總結：除非有有序的要求，不然都可以先考慮哈希容器。
7.unordered系列模擬實現
7.1重要補充
1）具體存放什么數據類型應該是set和map層面決定的，底層的哈希表只是存放數據，所以需要一個從存放數據提取關鍵碼的KeyOfT反函數。
2）另外還需要一個哈希函數來處理不能直接取模的情況。
3）哈希表的迭代器迭代邏輯：單鏈表迭代+順序表的哈希桶迭代。
4）如果使用自定義類型取作為樹形關聯(lián)容器的關鍵碼的話，需要提供一個小于比較仿函數，有了小于也就有了大于和等于。
5）如果使用自定義類型取作為哈希關聯(lián)容器的關鍵碼的話，需要提供一個等于比較仿函數。
6）set的迭代器無論是普通迭代器還是const迭代器在底層都是使用const迭代器。
7.2代碼
源碼
7.2.1哈希表
#pragma once
#include <iostream>
// 使用哈希桶解決哈希表的哈希沖突
#include <vector>
#include <utility>
using namespace std;
namespace lbq
{
// 將輸入轉成整型的哈希函數
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;
}
};
// 哈希桶具體存儲的數據類型
// 實際為一個單鏈表節(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;
}
}
// 如果后面已經沒有桶了
if(table_index == _ht->_table.size())
{
_node = nullptr;
}
}
return *this;
}
Iterator operator++(int)
{
Iterator tmp(_node, _ht);
operator++();
return tmp;
}
};
// 使用除留余數法作為哈希表的哈希函數，使用哈希桶解決沖突
// K：關鍵碼數據類型
// T：存儲的數據類型，Key或者pair<K, V>
// KeyOfT：從存儲的數據中提取關鍵碼
// 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())
{
// 已經存在相同的元素
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模擬實現
#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 模擬實現
#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容器內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現學籍管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
VC中SendMessage和PostMessage的區(qū)別
這篇文章主要介紹了VC中SendMessage和PostMessage的區(qū)別,較為全面的分析了SendMessage和PostMessage運行原理及用法上的不同之處,非常具有實用價值,需要的朋友可以參考下2014-10-10
今天小編就為大家分享一篇關于C語言實現模擬USB對8bit數據的NRZI編碼輸出，小編覺得內容挺不錯的，現在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C++的構造函數的作?：初始化類對象的數據成員。即類的對象被創(chuàng)建的時候，編譯系統(tǒng)對該對象分配內存空間，并?動調?構造函數，完成類成員的初始化。構造函數的特點：以類名作為函數名，?返回類型2022-05-05
QCommandLinkButton 是 Qt 框架中 QtWidgets 模塊的一個類,它提供了一個結合了文本標簽和按鈕功能的控件,本文主要介紹了Qt中QCommandLinkButton控件的使用,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了C語言單鏈表實現方法,結合實例形式分析了基于C語言的單鏈表定義、創(chuàng)建、添加、刪除、排序、打印等操作技巧,并附帶了相關的優(yōu)化算法,需要的朋友可以參考下2018-04-04
這篇文章主要為大家詳細介紹了C++的程序流程結構，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
由于工作需要抽出一周的時間來研究C/C++訪問各種數據庫的方法，并打算封裝一套數據庫操作類，現在奉上最簡單的一部分：在Linux下訪問MySQL數據庫。2017-05-05
這篇文章主要介紹了C++ 內聯(lián)函數inline案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C++string中的insert()插入函數，本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03