STL的六大組成部分
本文章將介紹第一部分，容器的原理與特性
-
容器(Containers):包括向量(vector)、列表(list)、集合(set)、映射(map)等
-
算法(Algorithms):包括排序、搜索、合并、交換元素等很多算法
-
迭代器(Iterators):提供了一種統(tǒng)一的機制來遍歷容器中的元素
-
適配器(Adapters):如stack和queue,它們利用底層容器(vector/list等)提供的接口來實現(xiàn)棧和隊列。
-
函數(shù)對象(Function objects):實現(xiàn)了函數(shù)調(diào)用操作的類。用于提供比較功能、計算功能等給算法。
-
分配器(Allocators):管理內(nèi)存分配與釋放
主要容器分類
C++標(biāo)準(zhǔn)庫提供了豐富的容器,主要容器有:
- 序列式容器:按線性順序存儲元素
- vector:動態(tài)數(shù)組,可隨機訪問元素。
- deque:雙端隊列,效率比 vector 好,但無法隨機訪問。
- list:雙向鏈表,適用于頻繁的插入和刪除。
- array:普通數(shù)組,固定容量。
- 關(guān)聯(lián)式容器:通過鍵來訪問元素
- set/multiset:各元素唯一/不唯一,按鍵值排序。
- map/multimap:鍵值對應(yīng)值,鍵唯一/不唯一,按鍵值排序。
- 容器適配器:提供額外功能的容器
- stack:運算棧,實現(xiàn)后進先出。
- queue:隊列,先進先出。
- priority_queue:優(yōu)先級隊列。
這些容器分為序列式、關(guān)聯(lián)式以及容器適配器。
序列式容器存儲元素順序排列,元素直接按索引訪問;
關(guān)聯(lián)式容器通過鍵來訪問元素,元素之間有排序關(guān)系;
容器適配器可以把其他容器轉(zhuǎn)換為棧、隊列等形式,提供額外功能。
除此之外,還有一些標(biāo)準(zhǔn)容器:
- bitset:位集合,高效操作并存儲一個位的集合。
- forward_list:單鏈表,實現(xiàn)了 list 的子集。
- unordered_set/unordered_map:無序集合,依靠哈希表實現(xiàn)。
vector
vector 通用特性
vector 是 STL 中最常用的容器之一,與 C 語言中的數(shù)組非常相似,但提供更多功能。
主要特點:
- 動態(tài)數(shù)組:可以在運行時自由增長,不需要預(yù)先指定長度。
- 隨機訪問:支持通過[]運算符快速訪問任意元素。
- 自動擴容:當(dāng)元素超出容量時,vector 會自動重新分配內(nèi)存,大小一般翻倍。
- 順序存儲:元素依次連續(xù)存儲在內(nèi)存中。
常用 API:
- push_back():在末尾插入一個元素。
- pop_back():刪除末尾的元素。
- size():返回容器中元素的個數(shù)。
- capacity():返回當(dāng)前分配的存儲容量。
- max_size():返回允許的最大容量。
- empty():判斷容器是否為空。
- array accessor:[] 用于索引訪問。
- begin()/end():返回迭代器。
- insert():在任意位置插入元素。
- erase():刪除任意位置的元素。
- resize():調(diào)整大小,可增加或刪除元素。
優(yōu)缺點:
- 優(yōu)點:隨機訪問效率高;自動擴容,使用方便。
- 缺點:擴容和刪除效率低,平均復(fù)雜度 O(n);占用額外內(nèi)存。
初始化:
- 直接初始化:
vector<int> v1;
vector<int> v2(10); // 長度為10,元素默認(rèn)初始值為0
- 列表初始化:
vector<int> v3 = {1,2,3};
vector<int> v4(10, 8); //長度為10,元素默認(rèn)初始值為8
vector 實現(xiàn)原理
- vector 的三個關(guān)鍵成員:
- data:指向元素的首地址。
- first:指向第一個元素。
- last:指向最后一個元素的下一個位置。
其中 first 和 last 用于判斷可用元素范圍。
- 分配內(nèi)存空間:
- vector 初始化時會分配一個指定容量的內(nèi)存空間。
- 當(dāng)元素數(shù)量超過已有容量時,需重新分配兩倍容量的內(nèi)存空間。
- 重新分配內(nèi)存:
- 檢查 capacity。當(dāng) size() > capacity() 時需要重新分配。
- 分配兩倍 capacity 大小的新內(nèi)存。
- 將原有元素拷貝到新內(nèi)存。
- 釋放原有內(nèi)存。
- 更新 first、last、data 指針。
- 增刪元素:
- 插入:需要移動后續(xù)元素,時間復(fù)雜度 O(n)
- 刪除:需要移動后續(xù)元素填補 deleted 位置,時間復(fù)雜度 O(n)
- 隨機訪問:
利用 data 指針和下標(biāo) [] 實現(xiàn)。
- 迭代器:
-
begin():返回指向 first 的迭代器。
-
end():返回指向 last 的迭代器。
迭代器實際上是一個左閉右開區(qū)間，即 [begin,end) ，所以 end 是不指向一個有效的元素的
- 釋放內(nèi)存
- vector 內(nèi)存的回收只能靠 vector 調(diào)用析構(gòu)函數(shù)的時候才被系統(tǒng)收回
- 也可以使用 swap 釋放內(nèi)存，如
v1.swap(v1)
stack
stack 特性
stack 是容器適配器中的一種,它采用底層容器(通常是 vector 或 deque)實現(xiàn)的堆棧數(shù)據(jù)結(jié)構(gòu)。
主要特點:
- 遵循 LIFO(后進先出)原理。
- 提供常用的棧操作,如入棧(push)、出棧(pop)、查看堆棧頂(top)等。
常用函數(shù):
- push():向棧頂插入元素。
- pop():從棧頂移除第一個元素。
- top():返回棧頂元素。
- empty():判斷棧是否為空。
- size():返回棧中元素個數(shù)。
底層容器:
stack 默認(rèn)采用 deque 作為底層容器,deque 有效支持棧上兩端的操作。
但也可以使用 vector 作為底層容器。
堆棧實現(xiàn):
stack 的底層實際上是一個容器(通常是 deque 或 vector),并提供了面向棧的接口。
利用容器的插入和刪除操作就可以實現(xiàn)棧功能。
初始化:
stack<int> s; // 使用deque作為默認(rèn)容器
stack<int, vector<int>> s; // 使用 vector 作為容器
stack 底層實現(xiàn)
stack 可以使用兩種底層容器:
- vector: 作為底層容器的默認(rèn)實現(xiàn)。
- deque: 相比 vector,deque 支持更高效的在兩端插入和刪除操作,更適合作為底層容器。
stack 可以直接利用 vector 和 deque 中的以下三個函數(shù)實現(xiàn)
- push(): 調(diào)用 push_back() 插入元素
- pop(): 調(diào)用 pop_back() 刪除元素
- top(): 調(diào)用 back() 訪問棧頂元素
stack 本質(zhì)上是一個適配器,類似以下形式
template<class T, class Container = deque<T> >
class stack {
public:
void push(const T&);
void pop();
// ...
private:
Container c; // 底層容器
};
queue
queue 實現(xiàn)和 stack 類似,也是采用底層容器(deque 或 list)來實現(xiàn)面向隊列的接口。
底層容器:
- 默認(rèn)采用 deque 作為底層容器。
- deque 支持高效的從兩端插入和刪除。
- 也可以使用 list 作為底層容器。
時間復(fù)雜度:
- 使用 deque 作底層容器:
- push: O(1)
- pop: O(1)
- 使用 list 作底層容器:
- push: O(1)
- pop: O(1)
實現(xiàn)隊列接口:
- push():調(diào)用底層容器的 push_back()實現(xiàn)
- pop(): 調(diào)用底層容器的 pop_front()實現(xiàn)
- front():調(diào)用底層容器的 front()實現(xiàn)
- back():調(diào)用底層容器的 back()實現(xiàn)
隊列類:
大致結(jié)構(gòu)如下:
template <class T, class Container = deque<T>>
class queue {
public:
void push(const T& x) { c.push_back(x); }
void pop() { c.pop_front(); }
// ...
private:
Container c; //底層容器
};
使用 queue:
queue<int> q;
q.push(1);
q.push(2);
q.pop();
deque
deque 簡介
deque 是 STL 容器之一,雙端數(shù)組,分為嚴(yán)格意義上的雙端隊列和段雙端隊列兩種。
主要特點:
- 支持高效的在兩端插入和刪除操作。時間復(fù)雜度為 O(1)。
- 支持隨機訪問,但效率不如 vector。
- 不必在插入刪除時發(fā)生實際的數(shù)據(jù)搬移。
- 內(nèi)部數(shù)據(jù)是以一系列段數(shù)組的形式分配,在需要時再分配新段。
常用函數(shù):
- push_back():在末尾插入元素
- push_front():在隊首插入元素
- pop_back():刪除末尾元素
- pop_front():刪除隊首元素
- front():返回隊首元素
- back():返回隊尾元素
- [] :支持隨機訪問
- begin()/end():返回迭代器
- size():返回元素個數(shù)
優(yōu)缺點:
- 優(yōu)點:兩端插入刪除效率高;不需要重新分配內(nèi)存
- 缺點:隨機訪問效率低于 vector
底層實現(xiàn):
deque 內(nèi)部使用一系列連續(xù)的內(nèi)存塊來存儲元素。
每次需要時再分配新內(nèi)存塊。
初始化:
- 直接初始化:
deque<int> d;
deque<int> d(10, 1); //長度10,默認(rèn)元素1
- 列表初始化:
deque<int> d = {1,2,3};
deque 底層實現(xiàn)原理
deque（雙端隊列）是 C++標(biāo)準(zhǔn)庫中的一個容器，它是一種雙端開口的序列容器，可以在兩端進行高效的插入和刪除操作。
deque 的底層實現(xiàn)基于一種叫做“分段連續(xù)空間”的數(shù)據(jù)結(jié)構(gòu)。
它將一個大的連續(xù)空間按照一定的大小分為多個小的連續(xù)空間，每個小的連續(xù)空間叫做一個“緩沖區(qū)”，每個緩沖區(qū)內(nèi)部元素是連續(xù)存儲的。
deque 維護了一個雙向鏈表，每個節(jié)點指向一個緩沖區(qū)，同時記錄了緩沖區(qū)的起始地址、結(jié)束地址以及下一個緩沖區(qū)的指針。
頭部插入元素，deque 會在鏈表頭部添加一個新的節(jié)點，并將新的元素插入到頭部緩沖區(qū)的前面；
尾部插入元素，deque 會在鏈表尾部添加一個新的節(jié)點，并將新的元素插入到尾部緩沖區(qū)的后面。
在頭部或尾部刪除元素，deque 也會根據(jù)需要調(diào)整其內(nèi)部結(jié)構(gòu)，以保證在常數(shù)時間內(nèi)完成操作。
在實現(xiàn)上，deque 使用了一個名為 map 的中央控制器，它是一個指針數(shù)組，每個指針指向一個緩沖區(qū)。
map 的大小是固定的，每個緩沖區(qū)的大小也是固定的，這些大小都是在編譯時指定的。
當(dāng)我們需要在 deque 的頭部或尾部插入元素時，deque 會先檢查是否需要添加新的緩沖區(qū)，如果需要，就會在 map 中分配一個新的指針并指向一個新的緩沖區(qū)，以保證能夠容納新的元素。
deque 底層實現(xiàn)對性能的影響
-
兩端插入刪除性能極高。deque 通過分配一系列連續(xù)的內(nèi)存塊實現(xiàn),兩端插入刪除時不需要移動已有元素。所以時間復(fù)雜度是 O(1)。
-
隨機訪問性能不如 vector。deque 內(nèi)部元素不是順序存儲,為了隨機訪問一個元素,需要先定位到對應(yīng)內(nèi)存塊,再在內(nèi)存塊中查找。所以效率不如 vector。
-
內(nèi)存開銷較大。deque 需要維護內(nèi)存塊數(shù)組,每次分配新內(nèi)存塊也需要額外開銷?？偟膬?nèi)存開銷比 vector 多。
-
擴容方式不同。deque 每次只分配一個固定容量的內(nèi)存塊,而不是像 vector 那樣兩倍擴容。
-
迭代器 invalid。deque 的迭代器不能跨越內(nèi)存塊。一旦 deque 重新分配內(nèi)存塊,所有迭代器都會失效。
基于這些特點,我們可以得到以下性能指標(biāo):
- 插入刪除性能: deque >> vector
- 隨機訪問性能:vector >> deque
- 內(nèi)存開銷:vector < deque
- 迭代器穩(wěn)定性:vector > deque
所以:
- 如果需要頻繁兩端插入刪除,應(yīng)選擇 deque。
- 如果需要高效的隨機訪問,應(yīng)選擇 vector。
deque 的應(yīng)用場景
- 實現(xiàn)命令歷史(命令行界面)
- 基于雙端隊列實現(xiàn)的事件循環(huán)
- 作為 stack 和 queue 的底層容器
- 層次結(jié)構(gòu)(如 XML 文件)遍歷時使用
- 需要高效插入刪除的集合
deque 線程安全問題
C++標(biāo)準(zhǔn)庫中的 deque 容器是一個線程不安全的容器，它的底層實現(xiàn)不支持多線程操作
若于多線程環(huán)境下使用，可以嘗試以下幾種方式
- 使用同步機制（如互斥鎖、讀寫鎖等）來保證線程安全
- 調(diào)用 boost 庫中的線程安全的 deque 實現(xiàn)
C++11 標(biāo)準(zhǔn)引入了一些原子操作和同步機制（如 std::atomic、std::mutex 等），可以用于實現(xiàn)線程安全的數(shù)據(jù)結(jié)構(gòu)
list
list 簡述
list 是 STL 中的序列式容器之一,它實現(xiàn)了雙向鏈表。
主要特點:
- list 的元素不要求連續(xù)內(nèi)存存儲。
- 節(jié)點是分立的,用指針鏈接起來的。
- 支持高效的插入與刪除操作。
常用函數(shù):
- push_back():在尾部插入元素
- push_front():在頭部插入元素
- pop_back():刪除尾部元素
- pop_front():刪除頭部元素
- erase():刪除指定元素
- insert():在指定位置插入元素
- sort():排序
- merge():合并
- remove():刪除指定值元素
優(yōu)缺點:
- 優(yōu)點:對插入和刪除操作效率高。
- 缺點:不支持隨機訪問,效率較低。
分配方式:
list 的節(jié)點分散分配,相鄰節(jié)點通過指針鏈接在一起。
初始化:
list<int> lst;
list<int> lst = {1, 2, 3};
時間復(fù)雜度:
- 插入和刪除:O(1)
- 查找:O(n)
- 訪問:O(n)
list 實現(xiàn)
List 的底層實現(xiàn)是一個雙向鏈表，每個節(jié)點包含三個指針：一個指向前一個節(jié)點、一個指向后一個節(jié)點，以及一個指向節(jié)點中存儲的元素
List 維護了兩個指針，一個指向鏈表的頭節(jié)點，一個指向鏈表的尾節(jié)點。當(dāng)我們需要在鏈表的頭部或尾部執(zhí)行插入或刪除操作時，在對應(yīng)首尾使用 new 添加新節(jié)點，或者使用 delete 刪除節(jié)點
對于基本類型（如 int、char 等），List 會將其直接存儲在節(jié)點中；對于復(fù)雜類型（如自定義類、結(jié)構(gòu)體等），List 會存儲其指針或引用
List 的插入和刪除操作非常高效，因為它只需要對節(jié)點的指針進行修改
list 多線程
同樣的，他也不是一個線程安全的容器，若要保證線程安全，可以參考 deque 的對應(yīng)方法
priority_queue
優(yōu)先隊列簡介
優(yōu)先隊列(Priority Queue)是 STL 中的一個重要數(shù)據(jù)結(jié)構(gòu)。它與標(biāo)準(zhǔn)的隊列不同,具有以下特點:
- 隊列中的元素有優(yōu)先級,可以根據(jù)優(yōu)先級高低對元素進行排序。
- 出隊操作選擇優(yōu)先級最高的元素。
- 優(yōu)先隊列的插入和刪除操作基于堆數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。
常用接口:
- push():向隊列中插入一個元素
- pop():移除優(yōu)先級最高的元素
- top():獲取優(yōu)先級最高的元素
- empty():判斷隊列是否為空
- size():返回隊列中的元素個數(shù)
底層實現(xiàn):
STL 的優(yōu)先隊列默認(rèn)采用二叉堆實現(xiàn)。
堆也可以是其他類型,包括牛欄堆、斐波那契堆等。
二叉堆:
- 完全二叉樹。所有父節(jié)點的元素都小于或大于子節(jié)點。
- 提供高效插入和刪除操作。時間復(fù)雜度為 O(logn)。
初始化:
priority_queue<int> max_pq; // 最大堆,默認(rèn)
priority_queue<int,vector<int>,greater<int>> min_pq; // 最小堆
應(yīng)用:
優(yōu)先隊列主要用于需要高效排序的場景,例如:
- 哈夫曼編碼
- Dijkstra 最短路算法
- 單源最短路徑
- 高頻元素統(tǒng)計
優(yōu)先隊列原理
優(yōu)先隊列的底層實現(xiàn)是使用堆（Heap）數(shù)據(jù)結(jié)構(gòu)。
堆是一種完全二叉樹，可以分為兩種類型：最大堆和最小堆。
在最大堆中，每個節(jié)點的值都大于或等于其子節(jié)點的值；在最小堆中，每個節(jié)點的值都小于或等于其子節(jié)點的值。
在優(yōu)先隊列中，通常使用最大堆來維護元素的優(yōu)先級關(guān)系
當(dāng)有新元素加入優(yōu)先隊列時，它會被插入到堆的末尾，然后通過上濾（percolate up）操作將其移動到正確的位置，以保證堆的性質(zhì)不變。
當(dāng)需要提取隊列中優(yōu)先級最高的元素時，堆的根節(jié)點就是優(yōu)先級最高的元素，它會被彈出并返回。
優(yōu)先隊列通常使用 vector 或 deque 容器來實現(xiàn)堆
優(yōu)先隊列依然是線程不安全的
set
set 簡介
set 是 STL 中的一個重要的關(guān)聯(lián)式容器,具有以下特點:
特點:
- set 中不允許包含重復(fù)元素。
- 元素會自動根據(jù)其值被排序。
- 可以快速找到元素,但是不支持隨機訪問。
常用接口:
- insert():插入元素
- erase():刪除元素
- find():查找元素
- count():統(tǒng)計元素個數(shù)
- begin()/rend():返回迭代器
- size():返回元素個數(shù)
- empty():判斷是否為空
底層實現(xiàn):
set 默認(rèn)采用紅黑樹來實現(xiàn)。
時間復(fù)雜度:
- 插入和刪除:O(logN)
- 查找:O(logN)
- 遍歷: O(N)
遍歷:
set 提供了迭代器遍歷方式和內(nèi)置迭代器遍歷方式:
// 迭代器遍歷
for (auto it = s.begin(); it != s.end(); ++it){
cout << *it << endl;
}
// 內(nèi)置遍歷
for (int x : s) {
cout << x << endl;
}
初始化:
set<int> s;
set<int> s = {1, 2, 3};
set<string> s2;
set 底層實現(xiàn)
set 容器的底層實現(xiàn)通常使用紅黑樹（Red-Black Tree）數(shù)據(jù)結(jié)構(gòu)，紅黑樹是一種自平衡的二叉搜索樹，能夠保證在最壞情況下的查找、插入和刪除操作的時間復(fù)雜度為 O(log n)
set 容器中的元素是唯一的，因此在插入元素時，紅黑樹會自動去重，保證每個元素只出現(xiàn)一次
對于 Set 容器，STL 實現(xiàn)的紅黑樹是一個左偏樹（Leftist Tree）的變種，被稱為 RB-tree（Red-Black Tree）
set 容器還提供了其他一些操作，如 lower_bound()、upper_bound()、equal_range()等，這些操作都是基于 RB-tree 實現(xiàn)的
map
map 簡介
map 是 STL 中的關(guān)聯(lián)式容器之一,它支持動態(tài)初始大小,允許使用用戶定義的鍵類型。
主要特點:
- 存儲的是鍵值對(key-value 對)。
- 可以通過鍵快速定位數(shù)據(jù),同一個鍵只能出現(xiàn)一次。
- 內(nèi)部使用紅黑樹自平衡。
常用函數(shù):
- insert(): 插入元素
- erase(): 刪除元素
- find(): 查找元素
- at(): 通過鍵獲取元素
- begin()/end(): 返回迭代器
- size(): 返回元素個數(shù)
- empty(): 判斷容器是否為空
時間復(fù)雜度:
- 插入和刪除: O(logn)
- 查找: O(logn)
- 迭代: O(n)
初始化:
map<string, int> m;
map<string, int> m = {
{"apple", 1},
{"banana", 2}
};
使用:
m["apple"] = 100; // 通過鍵設(shè)置值
int appleValue = m["apple"];
map 底層實現(xiàn)
map 容器的底層實現(xiàn)通常使用紅黑樹（Red-Black Tree）數(shù)據(jù)結(jié)構(gòu)文章來源：http://www.zghlxwxcb.cn/news/detail-466117.html
在 map 容器中，元素由鍵值對組成，按照鍵的大小關(guān)系進行排序。在插入元素時，map 容器會將元素插入到紅黑樹中的合適位置，并保持紅黑樹的性質(zhì)不變文章來源地址http://www.zghlxwxcb.cn/news/detail-466117.html
到了這里，關(guān)于STL快速上手1-容器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
