STL 容器

STL是C++的核心組成部分，其主要包括了容器、迭代器、算法三大組件。

其中容器負責存儲數據，迭代器是容器和算法的橋梁，負責對容器中的元素進行操作。本文重點介紹容器部分內容。

`STL`主要容器

STL容器根據特性進行分類，可以分為序列式容器、關聯容器、容器適配器

序列容器

序列容器重點在于根據元素的插入順序而進行線性排列。

常見的序列容器有5種，分別是vector,list,deque,array,forward_list，這5種序列容器的底層實現原理和核心特性總結如下：

容器	底層原理	核心特性
`vector`	擁有連續存儲空間的動態數組，底層由3個指針，分別是:`start`,`finish`,`end_of_stroage`，通過這三個底層指針可以實現一些常規操作；具備動態擴容機制（一般為2倍）	支持隨機訪問（`[]`/`at()`），尾插和刪除的復雜度為`O(1)`，中間插入/頭插/刪除元素 `O(n)`
`list`	底層數據結構是雙向鏈表（內存空間不連續），每個節點都有數據，前驅指針和后繼指針	不支持隨機訪問，在任意位置插入/刪除為 `O(1)`，遍歷元素效率`O(n)`
`deque`	分段連續內存，有一個指針數組，存放每一段連續存儲空間的地址	支持雙端高效插入/刪除 `O(1)`，隨機訪問效率略低于`vector`，整體來說集成了`vector`和`list`的優點
`array`	固定大小的靜態數組，內存分配在棧上	大小不可變，隨機訪問高效，適合存儲已知固定數量的元素
`forward_list`	單向鏈表（僅包含后繼指針）	內存占用比`list`更小，僅支持單向遍歷，插入/刪除 `O(1)`

關聯式容器

關聯容器重點在于鍵值對的關聯，元素根據按照鍵Key排序，元素的插入順序不會影響到元素所處的位置，可以分為有序關聯容器和無序關聯容器。

有序關聯容器

有序關聯容器以鍵為核心，元素會自動按照鍵的大小進行排序（默認情況下是升序排列std::less<key>，降序std::greater<int>）。這一類容器的底層數據結構是采用的紅黑樹（Red-Black Tree)，紅黑樹是一種自平衡的二叉搜索樹，紅黑樹的插入、刪除、查找的時間復雜度都是**O(logn)**.

有序關聯容器主要分為4種：set、map、multiset、multimap。它們的核心區別在于鍵是否唯一以及是否存儲鍵值對.

1、set

存儲唯一鍵的有序容器，其元素本身就是鍵(鍵=值)，并且這里也不允許鍵重復，新插入的元素會按照鍵的大小自動排序，同時set種的元素是常量，不能直接修改（可能會破壞紅黑樹的性質），修改的正確操作過程應該是先刪除舊元素，再插入新元素。由于紅黑樹的性質，在set插入或刪除元素時，除被刪除元素的迭代器外，其他迭代器均不會失效。

常見的接口操作：

insert(key)返回的是pair<iterator, bool>，標識是否插入成功
erase(key)/erase(iterator)刪除匹配鍵的元素和迭代器指向的元素
find(key)查找某個key
count(key)計算某個key出現的次數
lower_bound(key)找到第一個不小于key（≥key)的迭代器，upper_bound(key)返回第一個大于key的元素迭代器

2、multiset

可以在set的基礎上允許插入重復的鍵，元素按照鍵的大小有序排列。

常見的接口操作：

insert(key)返回新插入元素的迭代器
erase(key)刪除所有匹配鍵的元素
count(key)計算某個key出現的次數
equal_range(key)返回是一個pair包含所有匹配鍵的元素范圍[first, second)，左閉右開區間

3、map

map 是存儲鍵值對（key-value） 的有序容器，鍵（key）唯一，值（value）可修改。元素按鍵的大小自動排序，通過鍵可以快速訪問對應的值。

底層基于紅黑樹，樹的每個節點存儲一個pair<const key, value>，所以鍵不可修改，值可以通過迭代器和[]修改

在插入時，不允許插入重復的鍵，insert會忽略重復鍵的插入；鍵一般用來查找和排序，值用來存儲實際的元素，并且按照默認升序排列。

常見接口：

insert(pair<key, value>)（返回pair<iterator, bool>）、map[key] = value（若鍵存在則修改值，否則插入新鍵值對）。
erase(key)（刪除鍵對應的鍵值對）、erase(iterator)。
find(key)（返回指向鍵值對的迭代器）。
at(key)（安全訪問，鍵不存在時拋異常）、map[key]（非安全訪問，鍵不存在時插入默認值）。
lower_bound、upper_bound和set一樣

4、multimap

在map的基礎上允許插入重復的鍵，鍵值對按照鍵的大小有序排列。多個鍵值對可以有相同的鍵，按鍵有序排列（相同鍵的鍵值對相鄰），由于鍵不唯一，所以不能使用[]操作符號，只能使用find或者equal_range

常見接口：

insert(pair<key, value>)總是成功，返回新元素迭代器
equal_range(key)返回包含所有相同鍵的鍵值對范圍
erase(key)、find(key)返回第一個匹配鍵的迭代器，與map類似

所以有序管理容器的總結如下：

容器	底層原理	核心特點
`set`	紅黑樹，鍵值唯一，元素就是值	元素自動按鍵升序排列，插入 / 刪除 / 查找復雜度為 `O (log n)`
`multiset`	紅黑樹，鍵可以重復插入	特性同`set`，但支持鍵重復，插入 / 刪除 / 查找仍為 `O (log n)`
`map`	紅黑樹，存儲鍵值對，鍵唯一	按鍵升序排列，通過鍵快速訪問值（`[]`/`at()`），鍵不可重復
`mutlimap`	紅黑樹，鍵值對，鍵可以重復，插入到相鄰位置	特性同`map`，但鍵可重復，不支持`[]`操作符（需用`find()`/`equal_range()`）

無序關聯容器

無序關聯容器以鍵（key） 為核心的容器，其元素不按鍵的大小排序，而是通過哈希表（Hash Table）實現存儲和訪問。插入/刪除/查找的平均時間復雜度為O(1)。

底層的核心原理是哈希表（hashtable)，重點包含以下三個部分：

桶（Buckets）：一個動態數組，每個元素（桶）是一個鏈表或紅黑樹的頭指針，用于存儲哈希值相同的元素（處理哈希沖突）
哈希函數（Hash Function）：將鍵（key）映射為桶的索引（整數），決定元素應該放入哪個桶
相等比較器（Equality Comparator）：判斷兩個鍵是否 “相等”（用于處理哈希沖突時，區分不同鍵但哈希值相同的元素）

在插入新元素時，通過哈希函數計算鍵的哈希值，得到桶的索引，將元素放入對應桶中；查找元素時，先通過哈希函數定位桶索引，然后在桶內遍歷比較鍵，找到目標元素；當元素過多，超過負載因子時，觸發重hash，分配更大的桶數組，重新計算哈希值，并且遷移到新的桶中。

1、unordered_set

存儲唯一鍵的無序容器，元素本身就是鍵（“鍵 = 值”），鍵不允許重復，元素無序排列。適用于需要快速去重但是不需要關注元素順序的場景

在插入重復鍵時，insert會被忽略，并且元素的順序由哈希函數和插入順序決定，于鍵的大小無關；由于鍵是常量，所有更新鍵的信息，需要刪除舊元素插入新元素；插入時可能導致rehash導致所有迭代器失效，刪除時只有被刪除的元素的迭代器失效。

常見接口：

insert(key)返回pair<iterator, bool>，bool表示是否插入成功
erase(key)刪除所有匹配鍵的元素，返回刪除數量、erase(iterator)
find(key)返回指向鍵的迭代器，不存在則返回end()
count(key)返回鍵的出現次數，只能是 0 或 1
bucket_count()當前桶數量、load_factor()當前負載因子、rehash(n)強制將桶數量設置為≥n

2、unordered_map

存儲鍵值對（key-value） 的無序容器，鍵（key）唯一，值（value）可修改，元素無序排列，適用于需要通過唯一鍵快速查詢值且不關心鍵順序的場景，例如：緩存（鍵為 ID，值為緩存數據）、字典（無需按字母排序的鍵值映射）

插入重復鍵時，insert操作忽略，[]操作符會覆蓋舊值;鍵用于哈希和查找，值存儲實際數據，值可通過迭代器或[]修改；鍵值對順序由哈希函數決定，與插入順序和鍵大小無關。

常見接口：

insert(pair<key, value>)、map[key] = value鍵不存在則插入，存在則修改值
at(key)安全訪問，鍵不存在拋異常、map[key]不安全訪問，鍵不存在插入默認值
find(key)、erase(key)等與unordered_set類似

3、unordered_multiset

unordered_set的 “多重” 版本，允許存儲重復的鍵（鍵可以不唯一），元素無序排列（相同鍵的元素相鄰），適用于需要存儲重復元素且不關心順序的場景，例如：統計元素出現頻率（如詞頻統計）、存儲多個相同優先級的任務

4、unordered_multimap

unordered_map的 “多重” 版本，允許存儲重復的鍵（鍵值對的鍵可以不唯一），元素無序排列（相同鍵的鍵值對相鄰），多個鍵值對可擁有相同的鍵，相同鍵的鍵值對在同一桶中相鄰，適用于需要通過重復鍵映射多個值且不關心順序的場景。

無序關聯容器總結：

容器	底層原理	核心特性
`unordered_set`	哈希表（數組 + 鏈表 / 紅黑樹），鍵唯一	元素無序，插入 / 刪除 / 查找平均復雜度 `O (1)`（最壞 `O (n)`，取決于哈希沖突），鍵唯一。
`unordered_map`	哈希表，存儲鍵值對，鍵唯一	無序，通過鍵快速訪問值，平均 `O (1)` 操作，鍵唯一
`unordered_multiset`	哈希表，鍵可重復	無序，支持鍵重復，平均 `O (1)` 操作
`unordered_multimap`	哈希表，鍵值對，鍵可重復	無序，鍵可重復，平均`O (1)` 操作

容器適配器

容器適配器是一類特殊的容器，它們不直接實現數據存儲，而是通過封裝底層容器（如vector，deque，list等）來提供特定的接口和功能。核心作用是：限制對底層容器的訪問方式，只暴露符合特定數據結構邏輯的操作

主要特點：

本身不存儲數據，數據實際上存儲在底層容器中，適配器僅僅提供上層的接口
屏蔽底層容器的大部分操作，只保留符合自身發展邏輯的接口（stack僅允許棧頂操作）
適配器沒有迭代器，不支持遍歷或者隨機訪問
默認使用特定的容器作為底層實現（如stack使用deque），但是也可以通過模板參數指定其他符合要求的容器

主要的容器適配器類型

1、`stack`

stack遵循后進先出規則，僅僅允許在棧頂進行操作，插入、刪除和訪問等。

其底層的容器為deque，主要原因是：

deque的尾部插入和刪除的效率都是O(1)
deque可以減少頻繁擴容導致的內存重分配
跟list相比，deque的內存連續性更好，緩存利用率更高

核心操作有：

push(val)：在棧頂插入元素（調用底層容器的push_back）。
pop()：刪除棧頂元素（調用底層容器的pop_back，不返回元素）。
top()：返回棧頂元素的引用（調用底層容器的back）。
empty()：判斷棧是否為空。
size()：返回元素個數。

實現

template <typename T, typename Sequence = std::deque<T>> 
class stack {
public:using value_type = typename Sequence::value_type;using size_type = typename Sequence::size_type;using reference = typename Sequence::reference;using const_reference = typename Sequence::const_reference;using container_type = Sequence;// 各類接口bool empty() const {return container_.empty();}size_type size() const {return container_.size();}const_reference top() const {return container_.back();}void push(const value_type &v)  {container_.push_back(v);}void pop() {container_.pop_back();}template<typename... Args>void emplace(Args&& ...args) {container_.emplace_back(std::forward<Args>(args)...);}void swap(stack& other) {container_.swap(other.container_);}private:// 唯一的成員變量就是底層的容器containter_type container_;
}

2、`queue`

queuq遵循FIFO規則，允許在隊尾插入，隊頭刪除和訪問。

底層的默認容器還是deque，主要原因是：

deque支持隊尾插入（push_back）和隊頭刪除（pop_front），兩者效率均為 O (1)
若用vector作為底層，pop_front操作需移動所有元素（O (n)，效率低）
list雖支持 O (1) 的頭尾操作，但內存連續性差，緩存命中率低

核心操作有：

push(val)：在隊尾插入元素（調用push_back）。
pop()：刪除隊頭元素（調用pop_front，不返回元素）。
front()：返回隊頭元素的引用（調用front）。
back()：返回隊尾元素的引用（調用back）。
empty()/size()：判斷空或返回元素個數。

實現

template <typename T, typename Sequence = std::deque<T>>
class queue {
public:using value_type = typename Sequence::value_type;using size_type = typename Sequence::size_type;using reference = typename Sequence::reference;using const_reference = typename Sequence::const_reference;using container_type = Sequence;bool empty() const {return container_.empty();}size_type size() const {return container_.size();}reference front() const {return container_.front();}const_reference front() const {return container_.front();}reference_back() {return container_.back();}const_reference back() const {return container_.back();}void push(value_type& v) {container_.push_back(v);}void pop() {container_.pop_front();}template<typename ...Args>void emplace_back(Args&& ...args) {container_.emplace_back(std::forward<Args>(args)...);}void swap(queue& other) {container_.swap(other.container_);}private:container_type container_;
}

3、`priority_que`

priority_que是優先級隊列，也是一種適配器，每次刪除的其中的優先級最高的元素（默認最大元素），插入時會自動調整元素的位置以維持優先級順序。

priority_que底層使用的容器是vector，主要原因是：

priority_que邏輯是一個二叉堆，需要隨機訪問定位父子節點的位置（如父節點的下標為i，那么其左孩子的下標為2*i + 1，右孩子的下標為2*i + 2)
vector隨機訪問的效率最好，內存連續，具有局部性原理，并且堆的上浮和下沉操作效率更高

它默認使用std::less<T>作為比較器（大頂堆），std::greater<T>為小頂堆

如priority_queue<int, vector<int>, std::greater<int>> min_heap

核心操作有

push(val)：插入元素并調整堆結構（確保優先級最高的元素在頂部，復雜度 O (log n)）。
pop()：刪除頂部（優先級最高）的元素并調整堆（復雜度 O (log n)，不返回元素）。
top()：返回頂部元素的引用（調用底層容器的front）。
empty()/size()：判斷空或返回元素個數。

實現

template<typename T, typename Container = std::vector<int>,typename Comp = std::less<typename Container::value_type>>class priority_queue {public:using value_type = T;using size_type = typename Container::size_type;/// 構造函數explicit priority_queue(const Container& container = Container(), const Comp& comp = Comp())  : comp_(comp), container_(container){/// 利用容器的頭尾迭代器構造一個堆std::make_heap(container_.begin(), container_.end(), comp_);}// 拷貝構造和移動構造，賦值，移動賦值都是默認priority_queue(priority_queue &&) noexcept = default;priority_queue &operator=(priority_queue &&) noexcept= default;priority_queue(const priority_queue &) = default;priority_queue &operator=(const priority_queue &) = default;/// 輸入迭代器版本的構造函數template<typename InputIterator>priority_queue(InputIterator first, InputIterator last, const Comp& comp = Comp(), const Container& container = Container()) : container_(container), comp_(comp) {std::make_heap(container_.begin(), container_.end(), comp_);}// 下面是常見的接口bool empty() const {return container_.empty();}size_type size() const {return container_.size();}const value_type& top() const {return container_.front();}value_type& top() {return container_.front();}void push(const valye_type& value) {container_.push_back(value);std::push_heap(container_begin(), container_.end(), comp_);}void push(valye_type&& value) {container_.push_back(std::move(value));std::push_heap(container_begin(), container_.end(), comp_);}void pop() {std::pop_heap(container_.begin(), container_end(), comp_);container_.pop_back();}void swap(priority_que& other) {std::swap(comp_, other.comp_);std:;swap(container_, other.container_);}template<typename ...Args>void emplace_back(Args&& ...args) {container_.emplace_back(std::forward<Args>(args)...);std::push_heap(container_.begin(), container_.end(), comp_);}private:// 成員變量主要有比較器和容器Container container_;Comp comp_;}