STL Containers

--- tags: books, note --- # STL Containers > Standard Template Library Containers ## Intro STL container是C++標準函式庫中我認為最常用的部分，跟`<algorithm>`幾乎同等級而STL container顧名思義就是容器(container) 因為是用模板(template)實作，所以可以透過更改宣告時的`<>`來裝不同的內容 STL containers在的不同容器都有不同的特性，有些功能一樣，有些不一樣接下來會分別介紹各個容器，以及介紹個容器中相同及不同的函數 --- ## Vector 使用頻率: :star: :star: :star: :star: :star: > 取代掉所有的陣列使用需先引入標頭檔```<vector>``` ```cpp #include <vector> ``` vector就像陣列，是用下標來存取的容器，與其不同的地方在於vector可變大小常用於解決存取未知資料量的窘境再加上方便又好用的成員函數使得很多人直接用它取代陣列不過陣列依舊有它的優勢在例如: 程式碼短常數小等等就看程式員該如何決定但值得注意的一點是當資料量龐大時陣列無法一次抓那麼大的記憶體區塊這時就只能用vector了 ### 特色 - 為可變大小的序列容器 - 支援隨機(用下標)存取 $O(1)$ - 尾端增刪元素很快 $O(1)$ - 中間增刪元素很費時 $O(n)$ ### 功能 - [(constructor)](#(constructor)) - [iterators](#iterators) - [size](#size) - [resize](#resize) - [empty](#empty) - [operator[]](#operator[]) - [at](#at) - [front](#front) - [back](#back) - [data](#data) - [assign](#assign) - [push_back](#push_back) - [pop_back](#pop_back) - [insert](#insert) - [erase](#erase) - [swap](#swap) - [clear](#clear) - [emplace](#emplace) - [emplace_back](#emplace_back) --- ## Deque 使用頻率: :star: :star: :star: > Double ended queue > 一般不常用，但其他很多容器都是用他當作基底使用前需引入標頭檔`<deque>` ```cpp #include <deque> ``` 基本上就是多了push_front, pop_front 的 vector 如果真的需要操作頭尾的情況時才會選則deque 不然基本上都是使用vector ### 特色 - 操作特色與vector類似時間複雜度一樣但常數較大 ### 功能 - [(constructor)](#(constructor)) - [iterators](#iterators) - [size](#size) - [resize](#resize) - [empty](#empty) - [operator[]](#operator[]) - [at](#at) - [front](#front) - [back](#back) - [data](#data) - [assign](#assign) - [push_back](#push_back) - [push_front](#push_front) - [pop_back](#pop_back) - [pop_front](#pop_front) - [insert](#insert) - [erase](#erase) - [swap](#swap) - [clear](#clear) - [emplace](#emplace) - [emplace_back](#emplace_back) - [emplace_front](#emplace_front) --- ## Stack 使用頻率: :star: :star: :star: > 進行爆搜時會用到，也可以用來取代遞迴使用需先引入標頭檔```<stack>``` ```cpp #include <stack> ``` 預設以Deque為基底的容器配接器(Container Adaptors) 主要是為了方便程式員能夠較清楚明白此容器遵守LIFO(FILO) 什麼是LIFO? 就是Last In First Out後進先出就如同堆疊盤子一般最後所疊上去的盤子一定是最先拿走的盤子 ~~不可能從中間抽出來吧~~ 因此Stack也稱作堆疊 ![](https://i.imgur.com/MONRMEr.png =500x) ### 特色 - Last In First Out ### 功能 - [(constructor)](#(constructor)) - [empty](#empty) - [size](#size) - [top](#top) - [push](#push) - [emplace](#emplace) - [pop](#pop) - [swap](#swap) --- ## Queue 使用頻率: :star: :star: > 進行爆搜時會用到，除此之外很少使用需先引入標頭檔```<queue>``` ```cpp #include <queue> ``` Queue與Stack類似皆為以Deque為基底的容器配接器(Container Adaptors) 那Queue又要遵守啥呢? 沒錯就是FIFO(LILO) First In First Out又是甚麼概念呢? 可以把Queue想像成一列隊伍先排隊的人當然會是最先出來的反之亦然 ~~一樣不可能有人插隊吧~~ 因此Queue也被稱作佇列 ![](https://i.imgur.com/4ykkoYD.png =500x) ### 特色 - First In First Out ### 功能 - [(constructor)](#(constructor)) - [empty](#empty) - [size](#size) - [front](#front) - [back](#back) - [push](#push) - [emplace](#emplace) - [pop](#pop) - [swap](#swap) --- ## Priority queue 使用頻率: :star: :star: :star: :star: > greedy常用，性質佳使用需先引入標頭檔```<queue>``` ```cpp #include <queue> ``` Priority_Queue是預設以vector做為基底經過設計的容器配接器(Container Adaptors) 那Priority_Queue又要遵守甚麼原則呢? > 容器的排序方式會讓具有最大值的項目一定在佇列中的第一個沒錯神奇吧你可能會好奇這是怎麼做到的可以上網搜尋Heap的相關概念在大概了解Heap的概念後就會知道Heap的建立是能夠自訂比較方式的而Prioriy_Queue模板也提供了參數來讓程式員能自訂比較型態預設參數為最大堆(Max-Heap) 也就是Top為最大值 ### 特色 - 超級無敵方便存取資料極值 - 插入、刪除 $O(logn)$ - 讀取極值 $O(1)$ ### 功能 - [(constructor)](#(constructor)) - [empty](#empty) - [size](#size) - [top](#top) - [push](#push) - [emplace](#emplace) - [pop](#pop) - [swap](#swap) --- ## Set 使用頻率: :star: :star: :star: > 好用，但priority_queue更常用一點使用需先引入標頭檔```<set>``` ```cpp #include <set> ``` Set是按照特定順序存取唯一元素的容器通常是拿來判斷資料中有無重複我們一般會稱存放的資料為金鑰(Keys) ### 特色 - 資料不重複 - insert/erase $O(logn)$ ### 功能 - [(constructor)](#(constructor)) - [iterators](#iterators) - [empty](#empty) - [size](#size) - [insert](#insert) - [erase](#erase) - [swap](#swap) - [clear](#clear) - [emplace](#emplace) - [find](#find) - [count](#count) - [lower_bound](#lower_bound) - [upper_bound](#upper_bound) - [equal_range](#equal_range) --- ## Map 使用頻率: :star: :star: :star: :star: > 本斥但香跟set類似只不過每一個key是對應一個type key -> 索引的資料類型 type -> 對應項目的資料類型通常也是處理資料間的關係問題 ### 特色 - 好用 :D ### 功能 - [(constructor)](#(constructor)) - [iterators](#iterators) - [empty](#empty) - [size](#size) - [operator[]](#operator[]) - [at](#at) - [insert](#insert) - [erase](#erase) - [swap](#swap) - [clear](#clear) - [emplace](#emplace) - [find](#find) - [count](#count) - [lower_bound](#lower_bound) - [upper_bound](#upper_bound) - [equal_range](#equal_range) --- ## Set跟Map的變種以下這些能用的函式都跟原版幾乎一樣但在特性上有些不同，故獨立出來解釋 ### Multiset & Multimap 使用頻率: :star: :star: #### 特色 - 同樣的鍵值可重複 ### Unordered_set & Unordered_map 使用頻率: :star: :star: #### 特色 - 利用hash table實作，內部不排序 - 插入、搜尋都是$O(1)$，但常數大，慎用 ### Unordered_multiset & Unordered_multiset 使用頻率: :star: :::success **舉一反三** 你能從名字推出這兩個容器的特色是什麼嗎? ::: :::spoiler 想完再打開 #### 特色結合以上兩種特點 - 同樣的鍵值可重複 - 內部不排序 ::: --- ## 函式介紹 ### (constructor) 建構元，如果不知道可以去[Class那篇](https://hackmd.io/@konchin/book/%2FXToC9yD-R6Oxo7-G8nMy6Q/#Constructor)參考 #### 用法一般來說有幾種不同的方式 1. **初始大小** ```cpp stl<type> container(size); // vector<int> vec(10); ``` - `size`為建構時設定的容器大小 - 可用容器清單 - [x] Vector - [x] Deque - [ ] Stack - [ ] Queue - [ ] Priority_queue - [ ] Set - [ ] Map 2. **大小+預設值** ```cpp stl<type> container(size, val); // vector<int> vec(10, 0); ``` - `val`為建構時設定的預設值 - 可用容器清單 - [x] Vector - [x] Deque - [ ] Stack - [ ] Queue - [ ] Priority_queue - [ ] Set - [ ] Map 3. **根據範圍** ```cpp stl<type> container(begin, end); // vector<int> vec2(vec.beign(), vec.end()); ``` - `begin`和`end`為左閉右開的iterator - 可用容器清單 - [x] Vector - [x] Deque - [ ] Stack - [ ] Queue - [x] Priority_queue - [x] Set - [x] Map 4. **複製** ```cpp stl<type> container(another_container); // vector<int> vec3(vec); // stack<int, vector<int>> stk(vec3); ``` - `another_container`是同型態或是其基底的另一個容器 - 可用容器清單 - [x] Vector - [x] Deque - [x] Stack - [x] Queue - [x] Priority_queue - [x] Set - [x] Map --- ### iterators 中文來講就是迭代器，與指標差不多 (指標不熟的人要去[Pointer](/@konchin/book/%2FNbR3-VgcTOemy93z6H25QA)複習喔) 不過不同的是兩者不能混用且有些iterator不能用加法運算取得後幾位的元素而關於STL container的迭代器有許多函式在這就一組一組介紹 #### begin & end 為容器第一個位置與**最後一個位置後一格**的迭代器 ![](https://i.imgur.com/oiPKDyB.png) ##### 用法 ```cpp stl<type>::iterator l = container.begin(); stl<type>::iterator r = container.end(); // vector<int>::iterator it; // for(it = vec.begin(); it != vec.end(); ++it) // cout << *it << ' '; ``` #### rbegin & rend 為容器最後一個位置與**第一個位置前一格**的迭代器 ![](https://i.imgur.com/HGdfcMR.png) ##### 用法 ```cpp stl<type>::reverse_iterator l = container.rbegin(); stl<type>::reverse_iterator r = container.rend(); ``` #### cbegin& cend 與begin & end相同，不過只能讀不能修改 ##### 用法 ```cpp stl<type>::const_iterator l = container.cbegin(); stl<type>::const_iterator r = container.cend(); ``` #### crbegin & crend :::success **舉一反三** 你能從名字推出這兩個函式是什麼嗎? 對應的iterator型態又是什麼呢? ::: :::spoiler 想完再打開同時具有rbegin & rend和cbegin & cend的性質為容器最後一個位置與**第一個位置前一格**，不能修改值的迭代器 ##### 用法 ```cpp stl<type>::const_reverse_iterator l = container.crbegin(); stl<type>::const_reverse_iterator r = container.crend(); ``` ::: --- ### size 取得容器的大小，型態為`size_t`(與`unsigned long`相同) #### 用法 ```cpp size_t n = container.size(); // vector<int> vec = {1, 2, 3}; // cout << vec.size(); //Print: 3 ``` --- ### resize 重設容器的大小 #### 用法 1. **以預設值為 0 重設大小** 如果設定的容器大小比原本大多出來的部分會預設為0 ```cpp container.resize(size); ``` - `size`為欲設定之大小 2. **以自訂預設值重設大小** 如果設定的容器大小比原本大多出來的部分會預設為自訂值 ```cpp container.resize(size, val); ``` - `val`為自訂預設值 --- ### empty 檢查容器是否為空 #### 用法 ```cpp bool b = container.empty(); // if(vec.empty()) // cout << "Vector is empty" << endl; ``` --- ### operator[] 根據下標存取容器第$n$項的參照 #### 用法 ```cpp data_type& x = container[position]; //int last_element = vec[vec.size() - 1]; ``` - `data_type`為`container`內容物的型態 - `position`為一個`size_t`代表下標 ### at 根據下標存取容器第$n$項的參照 #### 用法 ```cpp data_type& x container.at(position); // int last_element = vec.at(vec.size() - 1); ``` - `data_type`為`container`內容物的型態 - `position`為一個`size_t`代表下標 :::danger **重點** 當`position`超出`container`範圍的時候 `operator[]`和`at`會有不同的反應 **operator[]** Undefine Behavior ```cpp #include<iostream> #include<vector> using namespace std; int main() { vector<int> container(5); cout << container[5] << endl; return 0; } ``` 基本上會是系統殘值 e.g. 7953 **at** 執行錯誤 ```cpp #include<iostream> #include<vector> using namespace std; int main() { vector<int> container(5); cout << container.at(5) << endl; return 0; } ``` terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 5) >= this->size() (which is 5) --- 因此如果懶得自己檢查有沒有超出邊界範圍可以用`at`幫你找 :poop: ::: --- ### front 存取第一個元素 #### 用法 ```cpp data_type& x = container.front(); // int first_element = vec.front(); ``` - `data_type`為`container`內容物的型態 --- ### back 存取最後一個元素 #### 用法 ```cpp data_type& x = container.back(); // int first_element = vec.back(); ``` - `data_type`為`container`內容物的型態 --- ### top 存取最上面的元素 #### 用法 ```cpp data_type& x = container.top(); // deque<int> dq = {1, 4, 5, 3}; // stack<int> stk(dq); // cout << stk.top(); // Print: 3 ``` - `data_type`為`container`內容物的型態 --- ### data 存取第一項元素的指標 #### 用法 ```cpp data_type* p = container.data(); // vector<int> vec = {1, 4, 5, 3}; // int* ptr = vec.data(); // for(size_t i = 0; i < vec.size(); ++i) // cout << *(ptr + i) << ' '; // Print: 1 4 5 3 ``` - `data_type`為`container`內容物的型態 --- ### assign 分配容器新的內容替換當前內容並修改大小 #### 用法一般來說有幾種不同的方式 1. **大小+預設值** ```cpp container.assign(size, val); // vector<int> vec; // vec.assign(5, 87); // vec -> 87, 87, 87, 87, 87 ``` - `size`為設定的容器大小 - `val`為設定的預設值 2. **根據範圍** ```cpp container.assign(begin, end); // vector<int> vec1 = {1, 5, 4, 2}; // vector<int> vec2 = {0, 0}; // vec2 -> 0, 0 // vec2.assign(vec1.begin(), vec1.end()); // vec2 -> 1, 5, 4, 2 ``` - `begin`和`end`為左閉右開的`iterator` 3. **initializer_list** ```cpp container.assign(list); // vector<int> vec; // vec.assign({87, 48763, 0}) // vec -> 87, 48763, 0 ``` - `list`為一個`initializer_list` --- ### push 從容器中增加元素 [Stack](#Stack)會加在[top](#top) [Queue](#Queue)會加在[back](#back) #### 用法 ```cpp container.push(); ``` --- ### pop 從容器中移除元素 [Stack](#Stack)會移除[top](#top) [Queue](#Queue)會移除[front](#front) #### 用法 ```cpp container.pop(); ``` --- ### push_back 在容器後面增加元素 #### 用法 ```cpp container.push_back(val); // vector<int> vec; // vec.push_back(87); ``` - `val`為與`container`內容物型態相同的一元素 --- ### push_front 在容器前面增加元素 #### 用法 ```cpp container.push_front(val); ``` - `val`為與`container`內容物型態相同的一元素 --- ### pop_back 從容器後面減少元素 #### 用法 ```cpp container.pop_back(); ``` --- ### pop_front 從容器前面減少元素 #### 用法 ```cpp container.pop_front(); ``` --- ### insert 在位置上插入元素 #### 用法 1. **Set** ```cpp container.insert(val); ``` - `val`為與`container`內容物型態相同的一元素 2. **Map** ```cpp container.insert(pval); container.insert({key, val}); ``` - `pval`為一個`pair` - `key`為和鍵值同型態的一元素 - `val`為和資料同型態的一元素 :::success **想想看** 為什麼`{key, val}`可以當作`pair`? > :::spoiler 想完再打開 > `pair`的`initializer_list`建構 > ::: ::: 3. **其他容器** ```cpp container.insert(position, val); ``` - `position`為表示插入位置的`iterator` - `val`為欲插入之元素 --- ### erase 刪除特定位置的元素 #### 用法 1. **Set** ```cpp container.erase(val); ``` - `val`為欲刪除的值 2. **Map** ```cpp container.erase(val); ``` - `val`為欲刪除的鍵值 3. **其他容器** ```cpp container.erase(position); ``` - `position`為欲刪除元素的位置 --- ### swap 將兩個容器交換 #### 用法 ```cpp container.swap(another_container); ``` - `another_container`為另一個同型態的容器 --- ### clear 清空容器 #### 用法 ```cpp container.clear(); ``` --- ### emplace 與 [insert](#insert) 相同，不過在傳入時呼叫建構元 #### 用法 1. **Set** ```cpp container.emplace(args...); ``` - `args`為`container`內容物型態建構元所需的元素 2. **Map** ```cpp container.emplace(key, val); ``` - `key`為和鍵值同型態的一元素 - `val`為和資料同型態的一元素 3. **其他容器** ```cpp container.emplace(position, args...); ``` - `position`為表示插入位置的`iterator` - `args`為`container`內容物型態建構元所需的元素 --- ### emplace_back 與 [push_back](#push_back) 相同，不過在傳入時呼叫建構元 #### 用法 ```cpp container.emplace_back(args...); // vector<pair<int, int>> vec; // vec.emplace_back(87, 54); ``` - `args`為`container`內容物型態建構元所需的元素 --- ### emplace_front 與 [push_front](#push_front) 相同，不過在傳入時呼叫建構元 #### 用法 ```cpp container.emplace_front(args...); ``` - `args`為`container`內容物型態建構元所需的元素 --- ### find 找尋容器內資料(或鍵值)，有則回傳該元素之iterator，若無則回傳 [container.end()](#iterators) #### 用法 ```cpp stl<type>::iterator it = container.find(val); ``` - `val`為欲尋找之值 --- ### count 回傳數值在範圍內出現次數 #### 用法 ```cpp size_type cnt = container.count(val); // 因為set內元素唯一若且為若cnt = 1, 則set含此元素 ``` - `val`為欲查詢之值 - `size_type`為一無號整數型態 --- ### lower_bound 回傳第一個大於等於詢問值元素之iterator #### 用法 ```cpp stl<type>::iterator it = container.lower_bound(val); //auto it = myset.lower_bound(87); //if(it != myset.end()) // cout << *it << '\n'; ``` - `val`為欲查詢之值 --- ### upper_bound 跟lower_bound類似不過是換成大於而已回傳第一個大於詢問值元素之iterator #### 用法 ```cpp stl<type>::iterator it = container.upper_bound(val); //auto it = myset.upper_bound(87); //if(it != myset.end()) // cout << *it << '\n'; ``` - `val`為欲查詢之值 --- ### equal_range 也跟前兩個類似只不過回傳的是等值範圍 $[begin, end)$ #### 用法 ```cpp pair<stl<type>::iterator, stl<type>::iterator> range = container.equal_range(val); //auto p = myset.equal_range(87); //for(auto it = p.first; it != p.second; ++it) // cout << *it << ' '; ``` - `val`為欲查詢之值 --- ## 外部連結如果你覺得講義不夠詳細或是覺得夠電想看英文的詳細說明 [cplusplus.com](http://www.cplusplus.com/reference/stl/) 這是可以參考的地方基本上講義大部分內容內容都跟上面一樣，但網站講得更深入一點 > [color=#1f1e33][name=9th進階教學][time=Sun, Jun 21, 2020 12:29 PM] > [color=#FF0000][name=9th教學顧問][time=Fri, Jun 26, 2020 15:03]