STL

在C++裡面的函式中，有一些內建好用資料結構，這些資料結構都是用一種叫型別模板(template)的東西去包裝，而這些資料結構包裝起來就變成了標準模板庫(standard template library)

那STL裡面有什麼呢？

首先我們先來講解STL的三大容器 vector、deque跟list

vector

vector介紹

原生C++的陣列是使用一連串的記憶體位置來儲存資料，但是當我們宣告完陣列大小後就沒辦法再修改了。

這時候我們就可以用STL裡的vector!!

vector簡單來講就是一個可以變長變短的陣列。在某些情況下，可以伸縮的陣列在解題上可以方便許多。

首先，我們來宣告一個vector，以下是一些常見的vector宣告方法

vector<int> vec; //一般的宣告

vector<int> vec = {1, 2, 3}; //宣告一個有1,2,3的vector

vector<int> vec(10); //宣告長度為10的vector

vector<int> vec(10,1); //宣告長度為10的vector，並將全部填為1，如果後面沒有參數，則填入0

如果我們已經知道資料的大小是多少的話，就可以把vector當一般陣列一樣。

那如果我們不知道要輸入多大的資料，我們可以使用push_back(emplace_back)來自動新增元素並配置記憶體到vector的尾端

vector<int> vec;

vec.push_back(1);

vec.emplace_back(1);

push_back跟emplace_back是差不多的東西，但在某些地方上有些微的不同
以pair當作例子來看

vector<pair<int,int>> v; //before C++11 

v.push_back(make_pair(1, 1));
v.push_back({1, 1}); //C++11

v.emplace_back(1, 1);

push_back是先建構一個臨時的物件，複製到容器尾端裡後再釋放臨時物件的記憶體
而emplace_back是直接呼叫建構函式建構在容器尾端
所以通常emplace_back的效率會比push_back還來的好

以下是vector常用的操作

vec.size() 回傳vector的大小

$O(1)$
vec.reserve(size)預留size大小的空間 如果要重新配置記憶體

$O(n)$，否則

$O(1)$
vec.empty() 回傳一個布林值，如果vector是空的就回傳true，否則回傳false，

$O(1)$
vec.clear() 清空vector，

$O(n)$

vector常見用途

以下兩種是vector的遍歷方式

vector<int> vec = {1, 2, 3};

for(int i=0;i<v.size();i++) cout << v[i] << ' ';

for(int i: vec) cout << i << ' '; // C++11 以上

可以看個人喜好或是情況來決定要用哪一種遍歷方式

vector的迭代器是屬於隨機存取迭代器，所以說我們可以把兩個vector的指標做運算，再搭配二分搜求出任一個數字在第幾個位置

vector<int> vec;

vec.begin() //vector的第一個位置
vec.end() //vector最後一個位置的後一位
int N = vec.end() - vec.begin(); //算出vec的size

迭代器也可以拿來遍歷vector

for(auto it = vec.begin(); it != vec.end(); it++) cout << *it;

vector也可以拿來當作連接串列，用來存圖上的邊和權重

vector<int> vec1[N];

for (int i = 0; i < m; ++i) { //無權單向
    int a, b;
    cin >> a >> b;
    vec[a].push_back(b);
}


vector<pair<int,int>> vec2[N];

for (int i = 0; i < m; ++i) { //有權雙向
    int a, b, w;
    cin >> a >> b >> w;
    vec2[a].push_back(make_pair(b, w));
    vec2[b].push_back(make_pair(a, w));
}

注意事項

vector在配置記憶體時蠻花時間的，如果確定好大小的話，先reserve()後再用push_back，效率會比較好

習題

TOJ 575
zerojudge b298

解答

TOJ 575

#include <bits/stdc++.h>
using namespace std;

#define bobotou ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second

using pii = pair<int, int>;

const int MAXN = 1000005;
vector<int> vec[MAXN];
vector<pii> peo;

signed main(){
	bobotou;
	int N, K;
	cin >> N >> K;
	for (int i = 0; i < K; i++){
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		peo.emplace_back(tmp1, tmp2);
	}
	for(int i = 0; i < K; i++){
		vec[peo[i].F].emplace_back(peo[i].S);
		vec[peo[i].S].emplace_back(peo[i].F);
	}

	for(int i = 1; i <= N; i++){
		sort(vec[i].begin(),vec[i].end());
		for(int j = 0; j < vec[i].size(); j++){
			if(j != 0) cout << ' ';
			cout << vec[i][j];
		}
		cout << '\n';
	}
}

zerojudge b298 (vector + queue)

#include <bits/stdc++.h>
using namespace std;

#define bobotou ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb(x) push_back(x)
#define F first
#define S second

const int MAXN = 100005;
vector<int> vec[MAXN];
bool poll[MAXN];

signed main(){
	bobotou;
	int N, M , L , Q;
	int tmp1, tmp2;
	cin >> N >> M >> L >> Q;
	for(int i = 0; i < M; i++){
		cin >> tmp1 >> tmp2;
		vec[tmp1].pb(tmp2);
	}
	queue<int> q;
	for(int i = 0; i < L; i++){
		cin >> tmp1;
		q.push(tmp1);
		while(!q.empty()){
			int x = q.front();
			q.pop();
			if(poll[x]) continue;
			poll[x] = true;
			for(auto i : vec[x]) q.push(i);
		}
	}
	for(int i = 0; i < Q; i++){
		cin >> tmp1;
		cout << (poll[tmp1] ? "TUIHUOOOOOO\n" : "YA~~\n");
	}
}

deque

deque 念法(ㄉㄟˋㄎㄜˇ )
中文叫雙向隊列

宣告寫法

deque<int> dq;

簡單來講就是可以在首尾新增、刪除元素的vector
大致上跟vector差不多，所以就直接講用途

dq.push_front() 在最前面放入元素

dq.push_back() 在最後面放入元素

dq.pop_front() 移除前面的元素

dq.pop_back() 移除後面的元素

dq.front() 回傳最前面的元素

dq.back() 回傳最後面的元素

dq.size() 回傳deque的大小

dq.empty() 回傳一個bool，如果為空true，否則false

同樣的也可以像vector一樣用emplace來壓常數

跟vector一樣也是隨機存取迭代器，所以也可以把兩個迭代器指標做運算

deque常見用途

sliding window
DP的單調對列優化

注意事項

deque雖然比vector的功能還要來的多，但是deque卻比vector還要慢很多，所以能用vector達成的盡量用vector來達成。
後面提到的適配器(Container Adapters)很多內建也都是deque，所以我們可以把那適配器容器改成vector來增加效率。

例題

list

STL的list是由一種叫連結串列(linked-list)來包裝
但是list其實在競程中沒有很常用到
而且在解題時我們也可以用陣列+struct來取代list
如果想要知道更多list的內容的話可以看這篇文章

例題

stack

一種先進後出的資料結構，由資料的同一端開口加入資料(push)或刪除資料(pop)。

實作

生活上的例子:賣場的推車(由同個方向加入推車或拿走推車)

queue

與stack語法類似，最大的不同是stack是後進先出，而queue則是先進先出

priority_queue

set

map

pair

bitset