stl 基于哈希的map c++_【C++】一文带你入门 STL
一 STL 組成
graph LRA[STL] --- B[容器 container]
A --- C[配接器 adapter]
A --- D[迭代器 iterator]
A --- E[仿函數 function]
A --- F[算法 algorithm]
A --- G[空間配置器 allocator]
二 常用容器
容器簡介
下面我們來簡單看一下這些容器的常用接口的使用，并分析其復雜度
vector
list
deque
stack
queue
priority_queue
set & multiset
map & multimap
unordered_map & unordered_multimap
| 底層實現： | 動態數組 + 鏈表(紅黑樹) |
| 查找： | find() |
| 計數： | count() |
| 指定插入： | insert() |
| 指定刪除： | erase() |
| 隨機訪問 | operator[] |
由于底層實現哈希表的時候，會有負載因子的存在，所以可以認為上述操作的復雜度都為 O(1)
如果哈希沖突比較多，可以采用 動態數組 + 紅黑樹實現，復雜度最多為 O(logn)
因此，哈希表的優勢為 O(1) 的查找；這是一種以空間換時間的策略。
容器選擇
不知道使用什么容器時，優先選擇 vector
如果不需要頻繁的任意位置插入，需要支持隨機訪問，選擇 vector
如果不需要隨機訪問，需要頻繁的插入，選擇 list
如果需要頻繁的對頭/尾操作，選擇 deque
如果需要高效的查找，但對內存沒有限制，可以選擇 unordered_map ；如果對內存有限制，可以選擇 set/map
deque 在 STL 中作為 stack 和 queue 底層實現。其優勢為：
劣勢為：不適合遍歷，因為在遍歷時，deque 的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下
- 相比于 vector ：頭部插入和刪除以及擴容時，效率更高，因為不需要搬大量的元素
- 相比于 list：底層空間更為連續，空間利用率更高
三 迭代器
1. 迭代器種類
迭代器種類一節摘自： Stl整理 (https://wu-kan.cn/_posts/2019-04-20-STL%E6%95%B4%E7%90%86/#%E7%AE%97%E6%B3%95%E6%A6%82%E8%A7%88)
C++中，一圖解釋五類迭代器之間的繼承關系：
graph LRA[輸入迭代器]
B[輸出迭代器]
C[前向迭代器]
D[雙向迭代器]
E[隨機訪問迭代器]
A --> C
B --> C
C --> D
D --> E
輸入迭代器(input iterator)
只讀，不寫；單遍掃描，只能遞增。
輸入迭代器只支持順序訪問，通常用于讀取序列中的元素。對于一個輸入迭代器it，*it++保證是有效的，但遞增它可能導致所有其他指向流的迭代器失效。其結果就是，不保證其狀態可以保存下來并用來訪問元素。因此，輸入迭代器只能用于單遍掃描的算法。支持如下操作：
- 相等(==)、不等(!=)比較。
- 用于推進迭代器的前置和后置遞增(++)。
- 解引用(*)，只能出現在賦值運算的右側；箭頭運算符(->)，it->member等價于(*it).member。
算法find要求輸入迭代器；而類型istream_iterator是一種輸入迭代器。
輸出迭代器(output iterator)
只寫，不讀；單遍掃描，只能遞增?？梢钥醋鬏斎氲鞴δ苌系难a集。
只能向解引用的輸出迭代器賦值一次，類似輸入迭代器，輸出迭代器也只能用于單遍掃描的算法，通常用作算法的目標位置。支持如下操作：
- 用于推進迭代器的前置和后置遞增(++)。
- 解引用(*)，只能出現在賦值運算的左側。
算法fill要求輸出迭代器；而類型ostream_iterator是一種輸出迭代器。
前向迭代器(forward iterator)
可讀寫；多遍掃描，只能遞增。
可以讀寫元素，只能在序列中沿著一個方向移動，支持所有輸入迭代器和輸出迭代器的操作，而且可以多次讀寫同一個元素。因此，可以保存前向迭代器的狀態，使用前向迭代器的算法可以進行多遍掃描。
算法replace要求前向迭代器；容器forward_list上的迭代器是前向迭代器。
雙向迭代器(bidrectional iterator)
可讀寫；多遍掃描，能遞增遞減。
可正向/反向讀寫序列中的元素。除支持所有前向迭代器的操作之外，雙向迭代器還支持前置和后置遞減(--)。
算法reverse要求雙向迭代器；除了forward_list之外，其他標準庫容器上的迭代器都是雙向迭代器。
隨機訪問迭代器(random-access iterator)
可讀寫；多遍掃描，支持全部迭代器運算。
提供在常數時間內訪問序列中任意元素的能力，除支持雙向迭代器的所有操作外，還支持：
- 用于比較兩個迭代器的相對位置(>、<、>=、<=)。
- 迭代器和一個整數值的加減運算(+、+=、-、-=)，計算結果迭代器在序列中前進或后退給定整數后的迭代器。
- 迭代器之間的減法(-)，得到兩個迭代器之間的距離。
- 下標運算符([])，it[n]與*(it+n)等價。
算法sort要求隨機訪問迭代器；容器vector上的迭代器和用于訪問內置數組的指針是隨機訪問迭代器。
2. 迭代器失效
圖片來源 cppreference
3. 迭代器實現
以下都是迭代器的簡單實現，要看對容器的完整實現，請去我的 Github，鏈接如下：
https://github.com/hairrrrr/Cpp-Primer
記得留下你的 star 喲~
deque
簡單實現：
template<class?T,...>struct?__deque_iterator{????...
????T*?cur;
????T*?first;
????T*?last;
????map_pointer?node;//map_pointer?等價于?T**
}
//當迭代器處于當前連續空間邊緣的位置時，如果繼續遍歷，就需要跳躍到其它的連續空間中，該函數可用來實現此功能
void?set_node(map_pointer?new_node){
????node?=?new_node;//記錄新的連續空間在?map?數組中的位置
????first?=?*new_node;?//更新?first?指針
????//更新?last?指針，difference_type(buffer_size())表示每段連續空間的長度
????last?=?first?+?difference_type(buffer_size());
}
//重載?*?運算符
reference?operator*()?const{return?*cur;}
pointer?operator->()?const{return?&(operator?*());}
//重載前置?++?運算符
self?&?operator++(){
????++cur;
????//處理?cur?處于連續空間邊緣的特殊情況
????if(cur?==?last){
????????//調用該函數，將迭代器跳躍到下一個連續空間中
????????set_node(node+1);
????????//對?cur?重新賦值
????????cur?=?first;
????}
????return?*this;
}
//重置前置?--?運算符
self&?operator--(){
????//如果?cur?位于連續空間邊緣，則先將迭代器跳躍到前一個連續空間中
????if(cur?==?first){
????????set_node(node-1);
????????cur?==?last;
????}
????--cur;
????return?*this;
}
list
/**?*?ListNode:?鏈表的節點類型
?*/
template<class?T>struct?ListNode
{
?T?_value;
?ListNode*?_next;
?ListNode*?_prev;
?ListNode(const?T&?val?=?T())
??:_value(val)
??,_next(nullptr)
??,_prev(nullptr)
?{}
};
/**
?*?ListIterator:?鏈表的迭代器
?*?類類型的迭代器不是指針，而是一個類。
?*?各種操作其實本質是操作?ListNode?中的某個成員
?*/
template<class?T,?class?Ref,?class?Ptr>struct?ListIterator
{
?typedef?ListNode?Node;typedef?ListIterator?Self;
?ListIterator(Node*?node)
??:_node(node)
?{}
?Ref?operator*()
?{return?_node->_value;
?}/**?
??*?->?當作單目運算符處理
??*?類類型中的元素訪問模式：ListNode->_val->某一個元素
??*?中間的?->_val?被編譯器優化
??*/
?Ptr?operator->()
?{return?&_node->_value;
?}
?Self&?operator++()
?{
??_node?=?_node->_next;return?*this;
?}
?Self&?operator--()
?{
??_node?=?_node->_prev;return?*this;
?}bool?operator!=(const?Self&?it)
?{return?_node?!=?it._node;
?}
?Node*?_node;
};
因為 map & set & multimap & multiset 底層都是用紅黑樹實現的，因此，我們有必要看一下紅黑樹的迭代器如何實現。
紅黑樹
template<class?Value>struct?RBNode{
?typedef?RBNode*?Ptr_RBNode;
?Value?_data;
?Color?_color;
?Ptr_RBNode?_left;
?Ptr_RBNode?_right;
?Ptr_RBNode?_parent;
?RBNode(const?Value&?data?=?Value())
??:_data(data)
??,_color(RED)?//?節點顏色默認初始化為?red
??,_left(nullptr)
??,_right(nullptr)
??,_parent(nullptr)
?{}
};template<class?Value>struct?RBIterator
{typedef?RBNode?Node;typedef?RBIterator?Self;
?Node*?_node;
?RBIterator(Node*?node)
??:_node(node)
?{}
?Value&?operator*()
?{return?_node->_data;
?}
?Value*?operator->()
?{return?&_node->_data;
?}bool?operator==(const?Self&?it)
?{return?_node?==?it._node;
?}bool?operator!=(const?Self&?it)
?{return?_node?!=?it._node;
?}
?Self&?operator++()
?{//?如果當前節點有右節點if?(_node->_right)
??{
???_node?=?_node->_right;//?讓?_node?設為最右節點while?(_node->_left)
????_node?=?_node->_left;
??}//?向上回溯，如果當前節點為父節點的右節點，繼續向上回溯else
??{
???Node*?parent?=?_node->_parent;while?(_node?==?parent->_right)
???{
????_node?=?parent;
????parent?=?parent->_parent;
???}//?當?parent?為?_header?,_node?為整個樹的根節點時，//?一定會退出上面的?while?循環,此時應該將?_node?置為?_header//?如果?_node?不在父節點的左側，也應該單獨執行一次，將?_node?指向下一次訪問的節點/*_node?=?parent;*///?上面的寫法有一個問題，如果整個樹只有一個節點。_header->right ==?_node//?_node?會走到?_header,?parent?走到?_node?此時退出循環//?_node?再被賦值為?_node?,?所以迭代器的遍歷會陷入循環if?(_node->_right?!=?parent)
????_node?=?parent;
??}return?*this;
?}
};
map 和 set 的迭代器只是對紅黑樹的迭代器進行了封裝，然后給出了 begin() 和 end() 方法。
哈希表
template<class?K,?class?V,?class?keyOfValue,?class?HashFun>struct?HashIterator{
?typedef?HashNode?Node;typedef?HashTable?_HashTable;typedef?HashIterator?Self;
?Node*?_node;
?_HashTable*?_ht;
?HashIterator(?Node*?node,??_HashTable*?ht)
??:_node(node)
??,_ht(ht)
?{}
?V&?operator*()?const?
?{return?_node->_value;
?}
?V*?operator->()?const
?{return?&_node->_value;
?}bool?operator!=(const?Self&?it)?const
?{return?_node?!=?it._node;
?}
?Self&?operator++()??
?{//?如果?_node._next?存在if?(_node->_next?!=?nullptr)
??{
???_node?=?_node->_next;
??}//?在哈希表中向后尋找非空鏈表else
??{
???keyOfValue?kov;
???HashFun?hf;int?idx?=?hf(kov(_node->_value))?%?_ht->_table.size();
???idx++;for?(;?idx?_table.size();?idx++)
???{if?(_ht->_table[idx])
????{
?????_node?=?_ht->_table[idx];break;
????}
???}//?哈希表已遍歷完if?(idx?==?_ht->_table.size())
????_node?=?nullptr;return?*this;
??}
?}
};
四 仿函數
priority_queue 默認是一個“大根堆”，使用如下代碼測試：
int?main(void){?priority_queue<int>?pq;
?pq.push(9);
?pq.push(5);
?pq.push(2);
?pq.push(7);
?while?(!pq.empty())
?{
??cout?<endl;
??pq.pop();
?}
}
輸出：
97
5
2
如果我們想要堆中最小的元素，也就是建立一個“小根堆”，可以通過這種方式定義 pq：
priority_queue<int,?vector<int>,?greater<int>>?pq;第二個參數表示 priority_queue 內部的實現方式，第三個參數定義了比較規則
我們也可以自己來定義比較規則：
template<class?T>struct?MyGreater?:?public?binary_functionbool>{bool?operator()(const?T&?lhs,?const?T&?rhs){return?lhs?>?rhs;
?}
};
然后通過如下方式調用：
priority_queue<int,?vector<int>,?MyGreater<int>>?pq;五 空間配置器
未完待續。。。
六 算法
未完待續。。。
參考文章：
C++ STL deque容器底層實現原理(深度剖析)
http://c.biancheng.net/view/6908.html
競賽常用STL容器詳解
https://blog.csdn.net/weixin_43844677/article/details/104902417
Stl整理
https://wu-kan.cn/_posts/2019-04-20-STL%E6%95%B4%E7%90%86/#%E7%AE%97%E6%B3%95%E6%A6%82%E8%A7%88
關注公眾號 不會編程的程序圓，看更多干貨
C++ 學習代碼倉庫：https://github.com/hairrrrr/Cpp-Primer
C 語言學習代碼倉庫：https://github.com/hairrrrr/C-CrashCourse
公眾號ID：不會編程的程序圓學習編程，看更多干貨?你們的在看就是對程序圓最大的鼓勵！總結
以上是生活随笔為你收集整理的stl 基于哈希的map c++_【C++】一文带你入门 STL的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： stm32 定时器_如何计算STM32定
- 下一篇： 线性回归csv数据集_数据科学的基石：统