上一篇博客：C++ STL詳解（1）

?寫在前面：大家好！我是AC-fun,我的昵稱來自兩個單詞Accepted和fun，我是一個熱愛ACM的蒟蒻，如果博客中有不足或者的錯誤的地方歡迎在評論區或者私信我指正，感謝大家的不吝賜教，我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/，非常感謝大家的支持，一起加油，沖鴨！
?用知識改變命運，用知識成就未來！加油 (? ??o??)? (? ??o??)?

刷題時常用的STL

string

?之前寫過一篇 string 的簡介：C++ String類學習總結 以及一篇有關輸入問題的解決： 連著使用cin和getline()只能輸入一次的問題 但是不是特別全面，這里再補充說明一下，

size()

?回傳字串中字符的數量

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str = "AC-fun";
	cout << str.size();
	// 輸出結果：6
	return 0;
}

clear()

?清空一個字串

#include<iostream>
#include<string>

using namespace std;

int main() {
	string s = "string";
	cout << s;
	s.clear(); // 清空一個字串 
	cout << endl;
	cout << "清空后字串的長度為：" << s.size() << endl;
	cout << "清空后字串的內容為：" << s;
	return 0;
}

運算子(Operators)

?你可以用 ==, >, <, >=, <=, != 比較字串，可以用 + 或者 += 運算子連接兩個字串，并且可以用 [] 獲取特定的字符，

compare()

?compare() 函式以多種方式比較本字串和 str，按照 字典序 進行排序，使用 this 代表當前字串，str 代表與 this 比較的字串，那么如果 this > str 則 回傳值大于零；如果 this = str 那么 回傳值等于零；如果 this < str 那么 回傳值小于零，此函式也有多種比較方式，下面分別進行介紹，

• 比較自己 (this) 和 str

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str1 = "aaa", str2 = "ab";
	if (str1.compare(str2) > 0) cout << "str1 > str2";
	else if (str1.compare(str2) == 0) cout << "str1 = str2";
	else cout << "str1 < str2";
	
	// 輸出結果：str1 < str2 
	return 0;
}

• 比較 自己的子串 和 str
  ?子串以 index 索引開始(從 0 開始），長度為 length， 形式為：str1.compare(index, length, str2) 表示比較 str1 的子串與 str2 的大小，

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str1 = "abcdef", str2 = "ef";
	int flag = str1.compare(4, 2, str2);
	if (flag) cout << "str1 > str2";
	else if (flag == 0) cout << "str1 = str2";
	else cout << "str1 < str2";
	
	// 輸出結果：str1 = str2 
	return 0;
}

• 比較 自己的子串 和 str的子串
  ?比較形式為：str1.compare(index, length, str2, index2, length2)，其中 index2 和 length2 參考 str，index 和 length 參考str1， 如果不寫 index2 則 str2 的子串以索引 0 開始，長度為 length2，str1 的子串以 index 開始，長度為 length，

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str1 = "abcdef", str2 = "abef";
	int flag = str1.compare(4, 2, str2, 2, 2);
	if (flag) cout << "str1 > str2";
	else if (flag == 0) cout << "str1 = str2";
	else cout << "str1 < str2";
	
	// 輸出結果：str1 = str2 
	return 0;
}

substr()

?substr()回傳本字串的一個子串，從index開始，長num個字符，形式為：str.substr(index, length)，如果不寫引數 length 或者引數 length 超過了 str 的長度，那么就將從 index 開始之后的所有字符輸出，

#include<iostream>
#include<string>

using namespace std;

int main() {
	string str = "AC-fun";
	cout << str.substr(3, 3);
	
	// 輸出結果：fun
	return 0;
}

c_str()

?c_str() 函式回傳一個指向正規 C 字串的指標，即回傳存盤字串的字符陣列的起始地址，利用這個函式可以使用 printf() 函式來輸出 string 字串，

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

int main() {
	string str = "AC-fun";
	printf("%s", str.c_str());
	
	// 輸出結果：AC-fun
	return 0;
}

find()

?在字串中查找字串，此函式有三種多載方式，下面分別進行介紹，

• str1.find(string str2, int index)
  ?回傳 str2 在字串 str1 中第一次出現的位置（從index開始查找）如果不寫 index 引數，則直接從 str1 的開頭開始查找，如果找到了回傳 **str2 ** 第一次出現的位置（下標從 0 開始）；如果沒找到則回傳 string::npos，對于 string::npos C++ 的官方檔案對它的解釋為：

?static const size_t npos = -1; npos是一個靜態成員常量值，對于 size_t 型別的元素，該常量的最大值可能，該值在字串成員函式中用作len（或sublen）引數的值時，表示“直到字串結尾”， 作為回傳值，通常用于表示沒有匹配項， 該常量定義為值 -1，這是因為 size_t 是無符號整數型別，因此它是此型別可能的最大可表示值，

?因此，在判斷字串有沒有時，可以直接判斷是否等于 string::npos，也可以判斷是否等于 -1，

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

int main() {
	string str1 = "AC-fun", str2 = "fun", str3 = "good";
	if (str1.find(str2, 0) != -1) cout << "Yes" << endl;
	if (str1.find(str3, 0) == string::npos) cout << "No";
	// 輸出結果：Yes
	//			 No
	return 0;
}

• str1.find(char ch, int index)
  ?回傳字符 ch 在字串中第一次出現的位置（從 index 開始查找），如果沒找到就回傳 string::npos，

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

int main() {
	string str1 = "AC-fun";
	if (str1.find('-', 0) != -1) puts("Yes");
	else puts("No");
	// 輸出結果：Yes
	return 0;
}

關于string的更多用法

?string還有很多函式，但是一般常用的函式就是以上提到的，想要學習更多用法請看：C++ API string

priority_queue

?priority_queue 優先佇列總能 保證優先級最高的元素位于隊頭，最重要的原因是其底層采用 堆 資料結構存盤結構，STL 的優先佇列默認是 大根堆，即最大的元素總是位于隊頭，其操作方式與佇列 queue 基本相同，優先佇列的頭檔案也是 #include<queue>，時間復雜度為：O(n l o g n logn logn)，

push()

?插入元素，并對底層容器排序，

#include<iostream>
#include<queue>

using namespace std;

int main() {
	priority_queue<int> heap;
	heap.push(1);
	heap.push(2);
	heap.push(3);
	
	// 使用 top() 訪問堆頂元素
	cout << heap.top();
	// 輸出結果：3 
	return 0;
}

top()

?訪問堆頂元素，演示代碼同 push()，

empty()

?檢查底層的容器是否為空，若底層容器為空則為 true ，否則為 false ，

size()

?回傳呼層容器中的元素個數，即 heap.size()，

#include<iostream>
#include<queue>

using namespace std;

int main() {
	priority_queue<int> heap;
	heap.push(1);
	heap.push(2);
	heap.push(3);
	cout << heap.size(); 
	// 輸出結果：3 
	return 0;
}

pop()

?彈出堆頂元素，

#include<iostream>
#include<queue>

using namespace std;

int main() {
	priority_queue<int> heap;
	heap.push(1);
	heap.push(2);
	heap.push(3);
	cout << "當前堆頂元素為:" << heap.top() << endl; 
	// 彈出堆頂元素 
	heap.pop();
	cout << "當前堆頂元素為:" << heap.top();
	return 0;
}

如何定義小根堆

?第一種方式是可以直接插入 -x，那么就可以直接利用大根堆創建了小根堆，輸出的時候輸出 -x 即可，
?第二種方式是使用 priority_queue 提供的方法，

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int main() {
	// 定義一個小根堆 
	priority_queue<int, vector<int>, greater<int> > heap; 
	heap.push(1);
	heap.push(2);
	heap.push(3);
	cout << "當前堆頂元素為:" << heap.top() << endl; 
	return 0;
}

堆排序

?堆是一棵 完全二叉樹 ，可以使用陣列模擬堆的實作，可以使用一維陣列 h[] 來進行存盤，對于根節點 x ，它的左兒子的下標為 x ? * ? 2，右兒子的下標為 x ? * ? 2 + 1，

?構建一個小跟堆其中最關鍵的一個函式就是 down() 函式，只要當前的根節點不是最小的元素那么就將其向下移動，直到當前的根節點是最小的元素，代碼及主要思路如下：

void down(int u) {
    int t = u;
    //  找出根、左、右三個點做小的那個點
    if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u; 
    // 首先判斷一下當前的根節點有沒有左孩子，如果有判斷一下根節點和左孩子的大小
    if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    // 然后再判斷一下當前根節點有沒有右孩子，如果有判斷一下上一步比較出來的做小值和當前右孩子的值的大小
    if (u != t) {
        swap(h[u], h[t]);
        // 此時原來的元素 h[u] 就被換到了下標為 t 的陣列中，所以繼續 down(t)
        down(t);
    }
}

?那么如何彈出堆疊頂元素呢？只要將第一個元素與最后一個元素交換，然后將指向堆中最后一個指標向前移動一個，再 down(1) 即可，這樣就可以在洗掉時一直保證堆頂元素時最小的元素，

完整代碼：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;
int n, m;
int h[N], cnt;  // 最好不要使用 size 作為變數，因為有的頭檔案里會有size函式，容易沖突

void down(int u) {
    int t = u;
    //  找出根、左、右三個點做小的那個點
    if (2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u; 
    // 首先判斷一下當前的根節點有沒有左孩子，如果有判斷一下根節點和左孩子的大小
    if (2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
    // 然后再判斷一下當前根節點有沒有右孩子，如果有判斷一下上一步比較出來的做小值和當前右孩子的值的大小
    if (u != t) {
        swap(h[u], h[t]);
        // 此時原來的元素 h[u] 就被換到了下標為 t 的陣列中，所以繼續 down(t)
        down(t);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;
    for (int i = n / 2; i; i--) down(i);
    // 先輸入再維護小根堆的時間復雜度為 O(n),而一邊輸入一邊維護的時間復雜度為 Nlog(N)
    while (m--) {
        printf("%d ", h[1]);
        h[1] = h[cnt];
        cnt--;
        down(1);
    }
    return 0;
}

未完待續，持續更新中……