Try   HackMD

Intro

學完 C++ 基礎語法之後，接著就該進入資料結構的世界了！
本篇筆記要介紹的是 C++ STL，彙整了許多基礎資料結構的概念與用法，文章內容較多，部分內容為收集資料擷取後並經過修改整理而成，文章內容若有任何錯誤或需要補充的地方都歡迎使用右側聊天室傳送訊息給我，我將會儘速修改，謝謝

先備知識

標準模板庫(Standard Template Library)，簡稱 STL 為 C++ 內建的函式庫
為了應對各種資料型態，因此採用 模板 template 來實作，分為六大部分：

  1. 容器 Containers
  2. 演算法 Algotithm
  3. 迭代器 Iterator
  4. 適配器 Adaptor
  5. 仿函數 Function object
  6. 空間配置器 allocator

本篇文章內容著重於前四大部分

符號解釋

對於本篇文章中各種符號的解釋

  • C：某種容器(container)
  • T：某種資料型態(type)
  • S：長度(size)
  • i：索引(index)
  • val：值(value)
  • K：鍵值(key)
  • it：迭代器(iterator)

迭代器(iterator)

C++ STL 為每個容器提供一個成員型別：迭代器 Iterator，我們可以用 指標 pointer 的概念來理解迭代器(實際上，指標算是一種迭代器)

假設現在有個迭代器 it，如果要存取 it 所指向的內容，那就是在前面加上星號 *it，與指標相同

以下有迭代器的三種分類：

  1. 隨機存取迭代器：這種迭代器能夠和整數的加減法，往 後移 x 項、往 前移 x 項 皆可，也可以 遞增 (++) 和 遞減 (−−)，可以把指標當作這種迭代器
  2. 雙向迭代器：只能做 遞增 (++) 和 遞減 (−−) 的運算，也就是 後一項 和 前一項
  3. 單向迭代器：只能做 遞增 (++) 的運算，也就是 後一項

利用迭代器可遍歷容器中的元素，分為 iterator 和 reverse_iterator（反向迭代器）
可用 C.begin(), C.end() 取得容器的 起始 和 尾端
而 reverse_iterator 則是 C.rbegin(), C.rend()

iterator 示意圖 (圖片來源)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

資料結構的詳細介紹

本篇介紹以下 C++ STL 內建基礎資料結構：

  • 動態陣列 vector
  • 字串 string
  • 數對 pair
  • 數組 tuple
  • 堆疊 stack
  • 佇列 queue
  • 雙端佇列 deque
  • 優先佇列 ptiority_queue
  • 集合 set
  • 映射 map
  • 多重集合 multiset
  • 多重映射 multimap
  • 無序集合 unordered_set
  • 無序映射 unordered_map
  • bitset

vector 動態陣列

像是 C++ 陣列 array 的升級版，可動態新增元素且能改變長度，不用事先宣告固定大小，且能支援原有的操作，基本上學完 vector 可直接取代 array

可支援的操作方法

操作方法 功能介紹
v[i] 讀取 v 的第 i 項，複雜度
O(1)
v.empty() 回傳一個 bool，表示 v 是否為空的，複雜度
O(1)
v.clear() 清空 v，但原本的空間不會被釋放掉，複雜度
O(n)
v.size() 回傳 v 目前的長度，複雜度
O(1)
v.resize(S,val) 強制將 v 的長度變為 S，若比原本長，則後面加 val 直到長度為 S，若比原本短則將多出的部分捨去，複雜度
O(n)
v.reserve(S) 預留 S 個空間，若 S > v.size()，此函數不造成任何影響
v.capacity() 取得容量（預分配的內存空間）
v.insert(it,val) 在 it 位置插入 val，必須向後搬動其餘元素，複雜度
O(n)
v.erase(it) 刪除 it 位置元素，也須向前搬動其餘元素，複雜度
O(n)
v.front() / v.back() 容器的首個元素或最後一個元素
v.push_back(val) / v.emplace_back(val) 在 v 的結尾加一個 val，均攤複雜度
O(1)
v.pop_back() 刪除 v 的最末項，若 v 為空，會發生無法預期的結果，複雜度
O(1)
v.begin() / v.end() 首個元素或最後一個元素的 iterator
v.shrink_to_fit() 將 v 的容量縮成剛好 size 的大小

可支援的演算法函數

演算法函數 功能介紹
swap(v1,v2) / v1.swap(v2) 交換兩 vector
find(v.begin(), v.end(), val) 在 v 中查找 val，找到返回指定元素的迭代器，找不到返回结束迭代器 end()
count(v.begin(), v.end(), val) 計算 v 中 val 出現的次數
replace(v.begin(), v.end(), val, new_val) 將 v 中的 val 全部替換成 new_val
sort(v.begin(), v.end()) 排序 v
reverse(v.begin(), v.end()) 反轉 v
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()) 將 v1 與 v2 合併到 v3
binary_search(v.begin(), v.end(), val) 二分搜，如果在 v 中有找到 val 回傳 1，否則回傳 0
lower_bound(v.begin(), v.end(), val) 回傳在 v.begin() 位置(包含)到 v.end() 位置(不含)之間第一個 >= val 的元素的位置
upper_bound(v.begin(), v.end(), val) 回傳在 v.begin() 位置(包含)到 v.end() 位置(不含)之間第一個 > val 的元素的位置
next_permutation(v.begin(),v.end()) 下一个排列组合
prev_permutation(v.begin(),v.end()) 上一个排列组合

lower_bound / upper_bound 可透過 * 取值，需在由小到大排列好的陣列中才可使用，若回傳的值是 v.end()，代表沒有符合的元素

常用基本操作 Code












































































// 宣告
vector<int> v;    // 長度為 0 的空 vector
vector<int> v(5); // 長度為 5 的 vector
vector<int> v(5,10); 
// 長度為 5 且每個元素皆被初始化為 10 的 vector，複雜度為 O(n)
vector<int> v = {1,2,3};

// 宣告雙層 vector
vector< vector<int> > vv;
// 可想像成二維陣列，但每一列長度可以不一樣

// 取值
int n = v[0];
// 與陣列一樣可使用 index 取值

// 取得長度
int s = v.size();

// 更改大小
v.resize(5);    // 將 v 的長度更改為 5

// 在尾端加入元素
int n = 10;
v.push_back(n);
v.emplace_back(n);

// 移除尾端元素
v.pop_back();

// 尋找
vector<int> v = {1,3,5,7,9};
int val; cin >> val
if(find(v.begin(), v.end(), val) == v.end()) {
    cout << "Not find\n";
} else cout << "Find!";
// input : 5 , output : Find!
// input : 6 , output : Not Find

// 排序(升序 由小到大)
sort(v.begin(), v.end());
sort(v, v+v.size());

// 排序(降序 由大到小)
sort(v.rbegin(), v.rend());
sort(v.begin(), v.end(),greater<int>());

// 反轉
reverse(v.begin(), v.end());

// 二分搜
binary_search(v.begin(), v.end(), val)
upper_bound(v.begin(), v.end(), val);
lower_bound(v.begin(), v.end(), val);

// 合併
vector<int> v1 = {1,3,5},
            v2 = {2,4,6},
            v3(6);
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for(auto i : v3) cout << i << " ";
// output : 1 2 3 4 5 6

// 全排列
vector<int> v = {1,3,5};
while(next_permutation(v.begin(),v.end())) 
{
    for(auto i : v) cout << i << " ";
    cout << "\n";
}
// output : 
// 1 5 3 
// 3 1 5 
// 3 5 1 
// 5 1 3 
// 5 3 1

注意：vector 不支援對前端元素使用 新增 或 刪除 的操作

補充

push_back() 與 emplace_back() 功能相同，但如果以效能為優先，emplace_back() 通常比 push_back() 更快一點，因為是直接呼叫 constructor 不會複製 object，所以有時候執行效率會比較快。
延伸閱讀：codingninjas - emplace_back() vs push_back() in C++ Vectors

在知道需要多少元素後，可以先對 vector 做 reserve() 擴充 capacity 再 emplece_back() ，會比 空 vector 慢慢 emplece_back() 快
延伸閱讀：ping 不見路 - STL vector 效率小記
示意圖 (圖片來源)
vector 示意圖

string 字串

由連續的字元組成，用法很像 vector<char>，非常方便

可支援的操作方法

vector 有的 string 幾乎都有

常用基本操作 Code
































// 宣告
string s;    // 預設為空字串
string s1 = "ABC";

// 賦值
cin >> s;        // 以空白作為輸入分隔
getline(cin,s);  // 以換行作為輸入分隔
s = "ShiYu";
s = s1;

// 串接
s = "ShiYu";
s1 = "ABC";
s += s1;
cout << s;
// output : ShiYuABC

// 刪除最後一個字元
s.pop_back();

// 讀取
cout << s[3];
// output : Y

// 擷取子字串
cout << s.substr(0,3);
// output : Shi

// 取得長度
cout << s1.size();
// output : 5

注意：取得字串長度請不要用 strlen()，應該要用 size()，因為前者複雜度為 O(n)，後者為 O(1)

pair 數對

可將兩個型態的資料合併，透過成員 first 和 second 來存取元素，pair 也可以元素字典序來比較或排序，以 first 為優先

常用基本操作 Code





















































// 宣告
pair<int, double> p;

// 賦值
p = {1, 2.5};
p = make_pair(1, 2.5);

// 取值
int f = p.first();    // 1
double s = s.second();// 2.5

// 比較
pair<int, double> a, b;
a = {1, 2.5};
b = {1, 2.6};
cout << (a < b) << "\n"; 
// output : 1 (true)

// 交換兩 pair
pair<int, int> a,b;
a = {1, 3};
b = {2, 4};
swap(a, b); // or a.swap(b)
cout << a.first << " " << a.second << "\n"; 
// output : 2 4

// pair 搭配 vector 新增元素
vector< pair<int,int> > vp;
vp.push_back(make_pair(1,2));
vp.emplace_back(3,4); // 用 emplace_back 可以不用 make_pair
for(auto i : vp) {
    cout << i.first << " " << i.second << "\n";
}
// output : 
// 1 2
// 3 4

// 使用 vector 排序多個 pair
pair<int,int> a = {1,3},
              b = {2,4},
              c = {1,2};
vector< pair<int, int> > v{a, b, c};

sort(v.begin(), v.end());

for(auto i : v) {
    cout << v[i].first << " " << v[i].second << "\n";
}
// output : 
// 1 2
// 1 3
// 2 4

tuple 數組

與 pair 相似，但可以同時組合多個不同型別的元素( pair 只能 2 個)

常用基本操作 Code

































// 宣告
tuple<string, int, bool> tp;

// 初始化
tuple<string, int, bool> tp("ShiYu", 16, true); 

// 賦值
tp = {"ShiYu", 16, true};
tp = make_tuple("ShiYu", 16, true);
tie("ShiYu", 16, true) = tp;

// 取值
int age = get<1>(tp); // 16

// 修改值
get<2>(tp) = false;

// 取得元素個數
cout << tuple_size<decltype(tp)>::value << "\n"; 
// output : 3

// tuple 搭配 vector 新增元素
vector< tuple<int, int, int> > vt;
vt.push_back(make_tuple(1, 2, 3));
vt.emplace_back(4, 5, 6); // 用 emplace_back 可以不用 make_tuple

for(auto& [a,b,c] : s) {
    cout << a << " " << b << " " << c << "\n";
}
// output : 
// 1 2 3
// 4 5 6

stack 堆疊

可以想像成一疊書本，每次只能在最上面 放置 或 拿走 一本書
有著 後進先出 Last In First Out 的規則
預設以 Deque 為基底的 容器適配器 Container Adaptors

可支援的操作方法

操作方法 功能介紹
s.size() 取得 s 大小
s.empty() 回傳 s 是否為空
s.top() 取得 s 頂端元素
s.push(val) / s.emplace(val) 將 val 放入 s 頂端
s.pop() 移除 s 頂端元素

複雜度皆為 O(1)

示意圖

stack 示意圖

(圖片來源)

常用基本操作 Code

依照示意圖實作













stack<int> stk;
for(int i=1;i<=3;++i) {
    stk.push(i);
}
while(!stk.empty()) {
    cout << stk.top() << "\n";
    stk.pop();
}
// output : 
// 3
// 2
// 1

常見應用

維護單調序列

queue 佇列

可以想像為排隊的人群，有可能是新的一個人來排在隊伍的尾端，或是最前面一個人結完帳離開隊伍
有著 先進先出 First In First Out 的規則

可支援的操作方法

操作方法 功能介紹
q.size() 取得 q 長度
q.empty() 回傳 q 是否為空
q.front() 取得 q 最前端(第一個加入的)元素
q.back() 取得 q 最尾端(最後加入的)元素
q.push(val) / q.emplace(val) 將 val 加入 q 尾端
q.pop() 移除 q 最前端元素

複雜度皆為 O(1)

示意圖

queue 示意圖

(圖片來源)

常用基本操作 Code













queue<int> q;
q.emplace(1);
q.emplace(2);
q.emplace(3);
while(!q.empty()) {
    cout << q.size() << " " << q.front() << " " << q.back() << "\n";
    q.pop();
}
// output : 
// 3 1 3
// 2 2 3
// 1 3 3

常見應用

圖論中的 BFS

deque 雙端佇列

為 double ended queue 的縮寫，一般的 queue 只能從尾端加入元素、從前端移除元素，而 deque 的前後都可以使用加入和移除的操作，基本上就是多了 emplace_front()、pop_front() 的 vector，雖然方便但由於常數較大，r競技賽中非必要不會去使用

示意圖

deque 示意圖

(圖片來源)

可支援的操作方法

vector 有的 deque 幾乎都有

操作方法 功能介紹
dq.push_front(val) / dq.emplace_front(val) 將 val 加入 dq 前端
dq.push_back(val) / dq.emplace_back(val) 將 val 加入 dq 尾端
dq.pop_front() 移除 dq 最前端元素
dq.pop_back() 移除 dq 最尾端元素

複雜度皆為 O(1)

常用基本操作 Code















deque<int> dq;
dq.emplace_front(1);
dq.emplace_back(2);
for(auto i : dq) cout << i << " ";
cout << "\n";
dq.pop_front();
for(auto i : dq) cout << i << " ";
cout << "\n";
dq.pop_back();
cout << dq.size() << "\n";
// output : 
// 1 2 
// 2 
// 0

priority_queue 優先佇列

priority_queue 利用幾個內建函式實現 堆積 heap 結構，它可以維持最頂端的元素永遠是最大或最小的，所以可以很方便快速的存取極值

示意圖

priority queue 示意圖

(圖片來源)

可支援的操作方法

操作方法 功能介紹
pq.size(),pq.empty() 同 vector，複雜度
O(1)
pq.top() 回傳 pq 中最大或最小的元素，複雜度
O(1)
pq.push(val) / pq.emplace(val) 將 val 加入 pq 中，複雜度
O(log⁡n)
pq.pop() 將 pq 中最大或最小的元素移除，複雜度
O(log⁡n)

常用基本操作 Code














priority_queue<int> pq;
pq.emplace(3);
pq.emplace(5);
pq.emplace(9);
cout << pq.top();
// output : 9

priority_queue< int, vector<int>, greater<int> > pq;
pq.emplace(3);
pq.emplace(5);
pq.emplace(9);
cout << pq.top();
// output : 3

補充

priority_queue 有三個型別參數 T、C、Cmp
T 是內容物的型別，C 是所採用的容器，Cmp 是比大小的依據
priority_queue 能使用的容器有 vector 和 deque
Cmp 的預設值是 less<T>，此時的 priority_queue 是最大堆 max heap
若改成 greater<T>，則 priority_queue 為 最小堆 min heap
建構式如上方 Code 第 8 行，而 output 為最小值

延伸閱讀

set 集合

set 實現了 紅黑樹(二元平衡樹) RB tree，也就是說可以用 O(log n) 的複雜度插入、刪除或查詢一個值是否在其中

內部自動有序且與數學的集合概念一樣不含重複元素，具有很方便地去重功能，且通常會稱元素的值為 鍵值 Key

示意圖

image

(圖片來源)

可支援的操作方法

操作方法 功能介紹
s.size() / s.empty() 同 vector
s.insert(K) 在 s 中放入一個鍵值為 k 的元素，若本來就有，則什麼事都不會做，複雜度
O(log⁡n)
s.erase(K) 刪除鍵值為 k 的元素，並回傳刪除的個數。複雜度
O(log⁡n)
s.erase(it first,it last) 刪除 [first,last)，若沒有指定 last 則只刪除 first，複雜度與刪除的個數呈線性
s.find(K) 回傳指向鍵值為 k 的迭代器，若 k 值不存在，則回傳 s.end()。複雜度
O(log⁡n)
s.count(K) 回傳有幾個鍵值為 k 的元素，複雜度
O(log⁡n)
s.lower_bound(K) 回傳迭代器指向第一個鍵值大於等於 k 的項。複雜度
O(log⁡n)
s.upper_bound(K) 回傳迭代器指向第一個鍵值大於 k 的項。複雜度
O(log⁡n)

常用基本操作 Code




















// 宣告
set<int> s;

// 插入
s.insert(10);

// 刪除
s.erase(10);
s.erase(s.begin());

// 回傳該元素的 iterator，若 set 內部無該元素，則回傳 end()
s.find(10);

// 問一個元素在不在 set 裡。可透過 find 的 return 值，或使用 s.count
if(s.find(10) != s.end()) cout << "In!\n";
if(s.count(10)) cout << "In!\n";

// 遍歷 set 元素
for(auto &i : s) cout << i << " ";

延伸閱讀

map 映射

類似於 python 中的 字典 dict，內部為 鍵值對 key-value，所以 map 中每一個元素其實是 pair，可以修改 value 值，但不能修改 key 值
map 可以用 O(log n) 的複雜度插入、刪除或查詢一個鍵值對應的值

示意圖

image

(圖片來源)

可支援的操作方法

set 有的 map 幾乎都有

操作方法 功能介紹
m[k] 存取鍵值 k 對應的值，若 k 沒有對應的值，會插入一個元素，使 k 對應到預設值並回傳之，複雜度
O(log⁡n)
m.insert(pair<K,T> k) 若沒有鍵值為 k.first 的值，插入一個鍵值為 k.first 的值對應到 k.second，並回傳一個 pair，first 是指向剛插入的元素的迭代器、second 是 true；若已經有了，回傳一個 pair，first 是指向鍵值為 k.first 的元素的迭代器，second 是 false。

multiset 多重集合 & multimap 多重映射

兩者用法與 set、map 用法一樣，但允許有重複元素，且 multimap 中一個鍵值可能對應到不同的值，所以不支援下標

示意圖

multiset 示意圖

(圖片來源)

unordered_set 無序集合 & unordered_map 無序映射

兩者用法也與 set、map 用法一樣，但利用 雜湊表 hash table 實作，內部不排序，因為沒有排序，所以當然沒有 lower_bound()、upper_bound()
插入、搜尋都是 O(1)，但常數大，不常使用

示意圖

image

(圖片來源)

延伸閱讀

unordered_multiset 無序多重集合 & unordered_multimap 無序多重映射

依名稱即可知道為前兩者的結合，內部不排序且可允許重複元素

bitset

可以將 bitset 當成是一個效率很快的 bool 陣列，因為 bool 這個型別明明只能表示 true 或 false，但通常卻佔了 1 byte 的記憶體空間，用 bitset 可以宣告固定長度的 bits，可以想像為一堆 0 和 1 的陣列，並且 bitset 的位元運算是被優化過的，對常數優化及空間壓縮有不錯的效用，速度大約是 bool 的 32 倍

可支援的操作函數

操作方法 功能介紹
b[i] 存取第 i 位。複雜度
O(1)
b.count() 回傳 b 有幾個位元是 1。複雜度
O(N)
b.size() 回傳 b 有幾個位元。複雜度
O(1)
b.set() 將所有位元設為 1。複雜度
O(N)
b.reset() 將所有位元設為 0。複雜度
O(N)
b.flip() 將所有位元的 0、1 互換 (反白)。複雜度
O(N)
b.any() / b.none() 檢查 b 中全 0 的情況，若 b 全 0，any() 返回 false、b.none() 返回 true，若 b 至少有一個 1，則結果相反
b.to_string() 回傳一個字串和 b 的內容一樣。複雜度
O(N)
b.to_ulong() 回傳一個 unsigned long 和 b 的內容一樣 (在沒有溢位的範圍內)。複雜度
O(N)

常用基本操作 Code













// 宣告
bitset<5> b; // 大小為 5，初始值 00000

// 賦值
b[0] = 1; // 00001 以右邊為低位

// 設置
b.set();	// 11111
b.reset();  // 00000

// 計數
b.count(); // 計算 b 裡有幾個 1

題單

看完這篇教學相信大家對 STL 有一定的瞭解了，不過還是要實際練習才能掌握，所以我把曾經寫過的題目整理成資料庫，來自各大 Online Judge，有依照不同的難度及不同資料結構分類好，歡迎大家自行運用，能讓你更加熟練。

STL 題單連結 - Notion

Outro

這篇文章只用了兩天的時間，從收集資料、整理資訊、規劃架構，再來開始寫每個資料結構的內容，製作表格、寫 Code、找圖片(每張圖片皆有附上來源)、找補充資料，到最後不斷地重複新增和修改內容，直到整篇文章逐漸完整，我從中學習到的不只有這篇文章所呈現的知識，還有很多重要的能力，也感受到了學習的快樂，日後會不斷地學習新知識，也會針對各主題寫成一篇筆記發佈，感謝大家的閱讀

下回預告：{% btn https://4yu.dev/post/Data-Structures-Advanced/,點擊前往,fa-solid fa-hand-point-right,blue %} C++ 進階資料結構實作

參考資料

點擊回到導覽頁面

Last changed by 
 
ShiYu
文章撰寫暫存區 建議至我的 Blog 查看此處所有公開筆記 > https://4yu.dev/
0
4
2119

Read more

南九校資訊社聯合寒訓 資得其樂 籌辦心得

在 2023/11/25 這次的寒訓總召其實

Mar 1, 2024
排序演算法 Sort Algorithm (C++)

現今社會，資料量不斷地增加，因此排序演算法的重要性日益提升。

Feb 23, 2024
訓練神經網路計算過程

image

Feb 23, 2024
Read more from ShiYu
Published on HackMD