STL Containers

Standard Template Library Containers

Intro

STL container是C++標準函式庫中我認為最常用的部分，跟<algorithm>幾乎同等級

而STL container顧名思義就是容器(container)
因為是用模板(template)實作，所以可以透過更改宣告時的<>來裝不同的內容

STL containers在的不同容器都有不同的特性，有些功能一樣，有些不一樣
接下來會分別介紹各個容器，以及介紹個容器中相同及不同的函數

---

Vector

使用頻率:

取代掉所有的陣列

使用需先引入標頭檔<vector>

#include <vector>

vector就像陣列，是用下標來存取的容器，與其不同的地方在於vector可變大小
常用於解決存取未知資料量的窘境 再加上方便又好用的成員函數
使得很多人直接用它取代陣列 不過陣列依舊有它的優勢在
例如: 程式碼短 常數小等等
就看程式員該如何決定

但值得注意的一點是 當資料量龐大時
陣列無法一次抓那麼大的記憶體區塊 這時就只能用vector了

特色

• 為可變大小的序列容器
• 支援隨機(用下標)存取
  $O(1)$
• 尾端增刪元素很快
  $O(1)$
• 中間增刪元素很費時
  $O(n)$

功能

• (constructor)
• iterators
• size
• resize
• empty
• operator[]
• at
• front
• back
• data
• assign
• push_back
• pop_back
• insert
• erase
• swap
• clear
• emplace
• emplace_back

---

Deque

使用頻率:

Double ended queue
一般不常用，但其他很多容器都是用他當作基底

使用前需引入標頭檔<deque>

#include <deque>

基本上就是多了push_front, pop_front 的 vector
如果真的需要操作頭尾的情況時 才會選則deque
不然基本上都是使用vector

特色

• 操作特色與vector類似 時間複雜度一樣但常數較大

功能

• (constructor)
• iterators
• size
• resize
• empty
• operator[]
• at
• front
• back
• data
• assign
• push_back
• push_front
• pop_back
• pop_front
• insert
• erase
• swap
• clear
• emplace
• emplace_back
• emplace_front

---

Stack

使用頻率:

進行爆搜時會用到，也可以用來取代遞迴

使用需先引入標頭檔<stack>

#include <stack>

預設以Deque為基底的容器配接器(Container Adaptors)
主要是為了方便程式員能夠較清楚明白此容器遵守LIFO(FILO)
什麼是LIFO? 就是Last In First Out後進先出
就如同堆疊盤子一般
最後所疊上去的盤子 一定是最先拿走的盤子
不可能從中間抽出來吧
因此Stack也稱作堆疊

特色

• Last In First Out

功能

• (constructor)
• empty
• size
• top
• push
• emplace
• pop
• swap

---

Queue

使用頻率:

進行爆搜時會用到，除此之外很少

使用需先引入標頭檔<queue>

#include <queue>

Queue與Stack類似 皆為以Deque為基底的容器配接器(Container Adaptors)
那Queue又要遵守啥呢? 沒錯就是FIFO(LILO)
First In First Out又是甚麼概念呢?
可以把Queue想像成一列隊伍
先排隊的人當然會是最先出來的 反之亦然
一樣 不可能有人插隊吧
因此Queue也被稱作佇列

特色

• First In First Out

功能

• (constructor)
• empty
• size
• front
• back
• push
• emplace
• pop
• swap

---

Priority queue

使用頻率:

greedy常用，性質佳

使用需先引入標頭檔<queue>

#include <queue>

Priority_Queue是預設以vector做為基底 經過設計的容器配接器(Container Adaptors)
那Priority_Queue又要遵守甚麼原則呢?

容器的排序方式會讓具有最大值的項目一定在佇列中的第一個

沒錯神奇吧
你可能會好奇這是怎麼做到的 可以上網搜尋Heap的相關概念

在大概了解Heap的概念後 就會知道Heap的建立是能夠自訂比較方式的
而Prioriy_Queue模板也提供了參數來讓程式員能自訂比較型態
預設參數為最大堆(Max-Heap) 也就是Top為最大值

特色

• 超級無敵方便存取資料極值
• 插入、刪除
  $O(logn)$
• 讀取極值
  $O(1)$

功能

• (constructor)
• empty
• size
• top
• push
• emplace
• pop
• swap

---

Set

使用頻率:

好用，但priority_queue更常用一點

使用需先引入標頭檔<set>

#include <set>

Set是按照特定順序存取唯一元素的容器
通常是拿來判斷資料中有無重複
我們一般會稱存放的資料為金鑰(Keys)

特色

• 資料不重複
• insert/erase
  $O(logn)$

功能

• (constructor)
• iterators
• empty
• size
• insert
• erase
• swap
• clear
• emplace
• find
• count
• lower_bound
• upper_bound
• equal_range

---

Map

使用頻率:

本斥但香

跟set類似 只不過每一個key是對應一個type
key -> 索引的資料類型
type -> 對應項目的資料類型

通常也是處理資料間的關係問題

特色

• 好用 :D

功能

• (constructor)
• iterators
• empty
• size
• operator[]
• at
• insert
• erase
• swap
• clear
• emplace
• find
• count
• lower_bound
• upper_bound
• equal_range

---

Set跟Map的變種

以下這些能用的函式都跟原版幾乎一樣
但在特性上有些不同，故獨立出來解釋

Multiset & Multimap

使用頻率:

特色

• 同樣的鍵值可重複

Unordered_set & Unordered_map

使用頻率:

特色

• 利用hash table實作，內部不排序
• 插入、搜尋都是
  $O(1)$，但常數大，慎用

Unordered_multiset & Unordered_multiset

使用頻率:

舉一反三
你能從名字推出這兩個容器的特色是什麼嗎?

想完再打開

特色

結合以上兩種特點

• 同樣的鍵值可重複
• 內部不排序

---

函式介紹

(constructor)

建構元，如果不知道可以去Class那篇參考

用法

一般來說有幾種不同的方式

1. 初始大小

stl<type> container(size);
// vector<int> vec(10);

• size為建構時設定的容器大小
• 可用容器清單
  • Vector
  • Deque
  • Stack
  • Queue
  • Priority_queue
  • Set
  • Map

2. 大小+預設值

stl<type> container(size, val);
// vector<int> vec(10, 0);

• val為建構時設定的預設值
• 可用容器清單
  • Vector
  • Deque
  • Stack
  • Queue
  • Priority_queue
  • Set
  • Map

3. 根據範圍

stl<type> container(begin, end);
// vector<int> vec2(vec.beign(), vec.end());

• begin和end為左閉右開的iterator
• 可用容器清單
  • Vector
  • Deque
  • Stack
  • Queue
  • Priority_queue
  • Set
  • Map

4. 複製

stl<type> container(another_container);
// vector<int> vec3(vec);
// stack<int, vector<int>> stk(vec3);

• another_container是同型態或是其基底的另一個容器
• 可用容器清單
  • Vector
  • Deque
  • Stack
  • Queue
  • Priority_queue
  • Set
  • Map

---

iterators

中文來講就是迭代器，與指標差不多
(指標不熟的人要去Pointer複習喔)
不過不同的是兩者不能混用
且有些iterator不能用加法運算取得後幾位的元素

而關於STL container的迭代器有許多函式
在這就一組一組介紹

begin & end

為容器第一個位置與最後一個位置後一格的迭代器

用法

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

為容器最後一個位置與第一個位置前一格的迭代器

用法

stl<type>::reverse_iterator l = container.rbegin();
stl<type>::reverse_iterator r = container.rend();

cbegin& cend

與begin & end相同，不過只能讀不能修改

用法

stl<type>::const_iterator l = container.cbegin();
stl<type>::const_iterator r = container.cend();

crbegin & crend

舉一反三
你能從名字推出這兩個函式是什麼嗎?
對應的iterator型態又是什麼呢?

想完再打開

同時具有rbegin & rend和cbegin & cend的性質
為容器最後一個位置與第一個位置前一格，不能修改值的迭代器

用法

stl<type>::const_reverse_iterator l = container.crbegin();
stl<type>::const_reverse_iterator r = container.crend();

---

size

取得容器的大小，型態為size_t(與unsigned long相同)

用法

size_t n = container.size();
// vector<int> vec = {1, 2, 3};
// cout << vec.size(); //Print: 3

---

resize

重設容器的大小

用法

1. 以預設值為 0 重設大小
   如果設定的容器大小比原本大
   多出來的部分會預設為0

container.resize(size);

• size為欲設定之大小

2. 以自訂預設值重設大小
   如果設定的容器大小比原本大
   多出來的部分會預設為自訂值

container.resize(size, val);

• val為自訂預設值

---

empty

檢查容器是否為空

用法

bool b = container.empty();
// if(vec.empty())
//     cout << "Vector is empty" << endl;

---

operator[]

根據下標存取容器第

$n$項的參照

用法

data_type& x = container[position];
//int last_element = vec[vec.size() - 1];

• data_type為container內容物的型態
• position為一個size_t代表下標

at

根據下標存取容器第

$n$項的參照

用法

data_type& x container.at(position);
// int last_element = vec.at(vec.size() - 1);

• data_type為container內容物的型態
• position為一個size_t代表下標

重點

當position超出container範圍的時候
operator[]和at會有不同的反應

operator[]
Undefine Behavior

#include<iostream>
#include<vector>
using namespace std;
int main() {
	vector<int> container(5);
	cout << container[5] << endl;
	return 0;
}

基本上會是系統殘值
e.g. 7953

at
執行錯誤

#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幫你找

---

front

存取第一個元素

用法

data_type& x = container.front();
// int first_element = vec.front();

• data_type為container內容物的型態

---

back

存取最後一個元素

用法

data_type& x = container.back();
// int first_element = vec.back();

• data_type為container內容物的型態

---

top

存取最上面的元素

用法

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

存取第一項元素的指標

用法

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. 大小+預設值

container.assign(size, val);
// vector<int> vec;
// vec.assign(5, 87); // vec -> 87, 87, 87, 87, 87

• size為設定的容器大小
• val為設定的預設值

2. 根據範圍

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

container.assign(list);
// vector<int> vec;
// vec.assign({87, 48763, 0}) // vec -> 87, 48763, 0

• list為一個initializer_list

---

push

從容器中增加元素
Stack會加在top
Queue會加在back

用法

container.push();

---

pop

從容器中移除元素
Stack會移除top
Queue會移除front

用法

container.pop();

---

push_back

在容器後面增加元素

用法

container.push_back(val);
// vector<int> vec;
// vec.push_back(87);

• val為與container內容物型態相同的一元素

---

push_front

在容器前面增加元素

用法

container.push_front(val);

• val為與container內容物型態相同的一元素

---

pop_back

從容器後面減少元素

用法

container.pop_back();

---

pop_front

從容器前面減少元素

用法

container.pop_front();

---

insert

在位置上插入元素

用法

1. Set

container.insert(val);

• val為與container內容物型態相同的一元素

2. Map

container.insert(pval);
container.insert({key, val});

• pval為一個pair
• key為和鍵值同型態的一元素
• val為和資料同型態的一元素

想想看
為什麼{key, val}可以當作pair?

想完再打開

pair的initializer_list建構

3. 其他容器

container.insert(position, val);

• position為表示插入位置的iterator
• val為欲插入之元素

---

erase

刪除特定位置的元素

用法

1. Set

container.erase(val);

• val為欲刪除的值

2. Map

container.erase(val);

• val為欲刪除的鍵值

3. 其他容器

container.erase(position);

• position為欲刪除元素的位置

---

swap

將兩個容器交換

用法

container.swap(another_container);

• another_container為另一個同型態的容器

---

clear

清空容器

用法

container.clear();

---

emplace

與 insert 相同，不過在傳入時呼叫建構元

用法

1. Set

container.emplace(args...);

• args為container內容物型態建構元所需的元素

2. Map

container.emplace(key, val);

• key為和鍵值同型態的一元素
• val為和資料同型態的一元素

3. 其他容器

container.emplace(position, args...);

• position為表示插入位置的iterator
• args為container內容物型態建構元所需的元素

---

emplace_back

與 push_back 相同，不過在傳入時呼叫建構元

用法

container.emplace_back(args...);
// vector<pair<int, int>> vec;
// vec.emplace_back(87, 54);

• args為container內容物型態建構元所需的元素

---

emplace_front

與 push_front 相同，不過在傳入時呼叫建構元

用法

container.emplace_front(args...);

• args為container內容物型態建構元所需的元素

---

find

找尋容器內資料(或鍵值)，有則回傳該元素之iterator，若無則回傳 container.end()

用法

stl<type>::iterator it = container.find(val);

• val為欲尋找之值

---

count

回傳數值在範圍內出現次數

用法

size_type cnt = container.count(val);

// 因為set內元素唯一 若且為若cnt = 1, 則set含此元素

• val為欲查詢之值
• size_type為一無號整數型態

---

lower_bound

回傳第一個大於等於詢問值元素之iterator

用法

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

用法

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)$

用法

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

這是可以參考的地方
基本上講義大部分內容內容都跟上面一樣，但網站講得更深入一點

9th進階教學Sun, Jun 21, 2020 12:29 PM

9th教學顧問Fri, Jun 26, 2020 15:03