2.insert(it, it2, it3), it 為原字符串的欲插入位置，it2 和 it3 為待插字符串的首尾迭代器，用來表示串[it2, it3)將被插在it 的位置上

示例如下：

#include#includeusing namespace std;int main(){	string str = "abcxyz", str2 = "opq";//str為原字符串，str2為待插字符串	//在str的3號位（即c和x之間）插入str2	str.insert(str.begin() + 3, str2.begin(), str2.end());	cout << str << endl;//輸出abcopqxyz	return 0;}

(5).erase()

erase()有兩種用法：刪除單個元素、刪除一個區(qū)間內的所有元素。時間復雜度均為O(N)

1.刪除單個元素：str.erase(it) 用于刪除單個元素，it為需要刪除的元素的迭代器

示例如下：

#include#includeusing namespace std;int main(){	string str = "abcdefg";	str.erase(str.begin() + 4);//刪除4號位（即e）	cout << str << endl;//輸出abcdfg	return 0;}

2.刪除一個區(qū)間內的所有元素：有兩種方法：

• str.erase(first, last), 其中first為需要刪除的區(qū)間的起始迭代器，而last為需要刪除的區(qū)間的末尾迭代器的下一個地址，即為刪除[first, last)

示例如下：

#include#includeusing namespace std;int main(){	string str = "abcdefg";	//刪除在[str.begin() + 2, str.end() - 1)內的元素，即cdef	str.erase(str.begin() + 2, str.end() - 1);	cout << str << endl;//輸出abg	return 0;}

• str.erase(pos, length), 其中pos為需要開始刪除的起始位置，length為刪除的字符個數(shù)。

示例如下：

#include#includeusing namespace std;int main(){	string str = "abcdefg";	str.erase(3, 2);//刪除de	cout << str << endl;//輸出abcfg	return 0;}

(6).clear()

clear()可以清空string中的數(shù)據(jù)，時間復雜度一般為O(1)

示例如下：

#include#includeusing namespace std;int main(){	string str = "abcd";	str.clear();//清空字符串	cout << str.length() << endl;//輸出0	return 0;}

(7).substr()

substr(pos, len) 返回從pos號位開始、長度為len的子串，時間復雜度為O(len)

示例如下：

#include#includeusing namespace std;int main(){	string str = "Thank you for your smile.";	cout << str.substr(0, 5) << endl;//輸出Thank	cout << str.substr(14, 4) << endl;//輸出your	cout << str.substr(19, 5) << endl;//輸出smile	return 0;}

(8).string::npos

string::npos是一個常數(shù)，其本身的值為-1 ，但由于是unsigned int 類型，因此實際上也可以認為是unsigned int 類型的最大值，可認為是4,294,967,295。string::npos 用以作為 find 函數(shù)失配時的返回值。

(9).find()

str.find(str) 當str2 是str 的子串時，返回其在str 中第一次出現(xiàn)的位置，如果str2 不是str 的子串，那么返回string::npos

str.find(str2, pos), 從str 的pos 號位開始匹配str2，返回值與上相同。時間復雜度為O(M*N)，M和N 分別是str2 和str的長度

示例如下：

#include#includeusing namespace std;int main(){	string str = "Thank you for your smile";	string str2 = "you";	string str3 = "me";	if (str.find(str2) != string::npos)	{		cout << str.find(str2) << endl;//輸出6	}	if (str.find(str2, 7) != string::npos)	{		cout << str.find(str2, 7) << endl;//輸出14	}	if (str.find(str3) != string::npos)	{		cout << str.find(str3) << endl;	}	else	{		cout << "I know there is no position for me." << endl;	}	return 0;}

(10).replace()

str.replace(pos,len,str2) 把str 從pos 號位開始、長度為len 的子串替換為上str2

str.replace(it1,it2,str2) 把str 的迭代器[it1, it2)范圍的子串替換為str2

示例如下：

#include#includeusing namespace std;int main(){	string str = "Maybe you will turn around.";	string str2 = "will not";	string str3 = "surely";	cout << str.replace(10, 4, str2) << endl;	cout << str.replace(str.begin(), str.begin() + 5, str3) << endl;	return 0;}

二、queue的常見用法詳解

queue翻譯為隊列，在STL中主要則是實現(xiàn)一個先進先出的容器，當需要實現(xiàn)廣度優(yōu)先搜索時，可以不用自己手動實現(xiàn)一個隊列，而是用queue代替，以提高程序的準確性。

1.queue的定義

要使用queue， 需要先添加頭文件#include, 并在頭文件下面加上"using namespace std;" ，然后就可以使用了。

其定義的寫法和其他STL容器相同，typename 可以是任意基本數(shù)據(jù)類型和容器：

queue name;

2.queue容器內元素的訪問

由于隊列（queue）本身就是一種先進先出的限制性數(shù)據(jù)結構，因此在STL中只能通過front() 來訪問隊首元素，或是通過back() 來訪問隊尾元素。

示例如下：

#include#includeusing namespace std;int main(){	queue q;	for (int i = 1; i <= 5; i++)	{		q.push(i);//push(i)用以將i壓入隊列，因此依次入隊1 2 3 4 5 	}	printf("%d %d/n", q.front(), q.back());//輸出結果為1 5	return 0;}

3.queue常用函數(shù)實例解析

• push()
• front()
• back()
• pop()
• empty()
• size()

(1).push()

push(x) 將x 進行入隊，時間復雜度為O(1)

(2).front(), back()

front(), back()可以分別獲得隊首元素和隊尾元素，時間復雜度為O(1)

注意哦，使用front() 和 pop() 函數(shù)之前，必須用empty() 判斷隊列是否為空，否則可能會因為隊列空導致錯誤

(3).pop()

pop()令隊首元素出隊，時間復雜度為O(1)

示例如下：

#include#includeusing namespace std;int main(){	queue q;	for (int i = 1; i <= 5; i++)	{		q.push(i);	}	for (int i = 0; i < 3; i++)	{		q.pop();//出隊列元素3次，依次出隊1 2 3	}	printf("%d/n", q.front());//輸出4	return 0;}

(4).empty()

empty()檢測queue是否為空，返回true則為空，返回false則非空，時間復雜度為O(1)

示例如下：

#include#includeusing namespace std;int main(){	queue q;	if (q.empty() == true)//一開始隊列里沒有元素，所以是空	{		printf("Empty/n");	}	else	{		printf("Not Empty/n");	}	q.push(1);	if (q.empty() == true)	{		printf("Empty/n");	}	else	{		printf("Not Empty/n");	}	return 0;}

(5).size()

size()返回queue內元素的個數(shù)，時間復雜度為O(1)

示例如下：

#include#includeusing namespace std;int main(){	queue q;	for (int i = 1; i <= 5; i++)	{		q.push(i);	}	printf("%d/n", q.size());//輸出5	return 0;}

【延伸】：STL容器中還有兩種容器跟隊列有關，分別是雙端隊列(deque) 和優(yōu)先隊列(priority_queue) ，前者是首尾皆可插入和刪除的隊列，后者是使用堆實現(xiàn)的默許將當前隊列最大元素置于隊首的容器，這里暫時先不介紹，后期如果需要再進行補充。

三、stack的常見用法詳解

stack 翻譯為棧，是STL中實現(xiàn)的一個先進后出的容器，stack 用來模擬實現(xiàn)一些遞歸，防止程序對棧內存的限制而導致程序運行出錯。

1.stack的定義

要使用stack，應先添加頭文件#include, 并在頭文件下面加上" using namespace std;"，然后就可以使用了。

其定義的寫法和其他STL容器相同，typename可以是任意基本數(shù)據(jù)類型或容器：

stack name;

2.stack容器內元素的訪問

由于棧(stack) 本身就是一種先進后出的數(shù)據(jù)結構，在STL的stack 中只能通過top() 來訪問棧頂元素

示例如下：

#include#includeusing namespace std;int main(){	stack st;	for (int i = 1; i <= 5; i++)	{		st.push(i);//依次入棧1 2 3 4 5	}	printf("%d/n", st.top());//輸出5	return 0;}

3.stack常用函數(shù)實例解析

• push()
• top()
• pop()
• empty()
• size()

(1).push()

push(x) 將x 入棧，時間復雜度為O(1)，

(2).top()

top()獲得棧頂元素，時間復雜度為O(1)

(3).pop()

pop()用以彈出棧頂元素，時間復雜度為O(1)

示例如下：

#include#includeusing namespace std;int main(){	stack st;	for (int i = 1; i <= 5; i++)	{		st.push(i);	}	for (int i = 0; i < 3; i++)	{		st.pop();	}	printf("%d/n", st.top());//輸出2	return 0;}

(4).empty()

empty()可以檢測stack 內是否為空，返回true 為空，返回false 為非空，時間復雜度為O(1)

(5).size()

size()返回stack 內元素的個數(shù)，時間復雜度為O(1)

四、algorithm頭文件下的常用函數(shù)

使用algorithm 頭文件，需要在頭文件下面加上一行"using namespace std;"，才能正常使用

• max()、min()、abs()
• swap()
• reverse()
• next_permutation()
• fill()
• sort()
• lower_bound() 和 upper_bound()

1.max()、min()和abs()

max(x,y)和min(x,y) 分別返回x, y中的最大值和最小值，且參數(shù)必須是兩個，可以是浮點數(shù)，如果想返回三個數(shù)x,y,z的最大值，可以使用max(x, max(y, z)) 的寫法；abs(x) 返回x的絕對值。注意：此時的x 必須是整數(shù)，浮點數(shù)的絕對值請用math 頭文件下的fabs

示例如下：

#include#includeusing namespace std;int main(){	int x = -1;	int y = -2;	printf("%d %d/n", max(x, y), min(x, y));//輸出-1 -2	printf("%d %d/n", abs(x), abs(y));//輸出1 2	return 0;}

2.swap()

swap(x, y) 用來交換x 和 y 的值

示例如下：

#include#includeusing namespace std;int main(){	int x = 10;	int y = 20;	swap(x, y);	printf("%d %d/n", x, y);//輸出20 10	return 0;}

3.reverse()

reverse(it, it2) 可以將數(shù)組指針在[it, it2) 之間的元素或容器的迭代器在[it, it2) 范圍內的元素進行反轉

示例如下：

#include#includeusing namespace std;int main(){	int arr[10] = { 10,11,12,13,14,15 };	reverse(arr, arr + 4);//將arr[0]~arr[3]反轉	for (int i = 0; i < 6; i++)	{		printf("%d ", arr[i]);//輸出13,12,11,10,14,15	}	return 0;}

如果要是對容器中的元素（例如string 字符串）進行反轉，結果也是一樣

示例如下：

#include#include#includeusing namespace std;int main(){	string str = "abcdefghi";	reverse(str.begin() + 2, str.begin() + 6);//對str[0]~str[5]反轉	for (int i = 0; i < str.length(); i++)	{		printf("%c", str[i]);//輸出abfedcghi	}	return 0;}

4.next_permutation()

next_permutation() 給出一個序列在全排列中得下一個序列

例如，當n == 3 時的全排列為：

123

132

213

231

312

321

這樣231的下一個序列就是312

示例如下：

#include#includeusing namespace std;int main(){	int a[10] = { 1,2,3 };	//a[0]~a[2]之間的序列需要求解next_permutation	do	{		printf("%d%d%d/n", a[0], a[1], a[2]);	} while (next_permutation(a, a + 3));	return 0;}

在上述的代碼中，使用循環(huán)是因為next_permutation在已經(jīng)到達全排列的最后一個時會返回false, 這樣會方便退出循環(huán)。而使用do...while語句而不使用while語句是因為序列1 2 3本身也需要輸出，如果使用while會直接跳到下一個序列再輸出，這樣的話結果會少一個123

5.fill()

fill()可以把數(shù)組或容器中的某一段區(qū)間賦為某個相同的值。和memset 不同，這里的賦值可以是數(shù)組類型對應范圍中的任意值

示例如下：

#include#includeusing namespace std;int main(){	int a[5] = { 1,2,3,4,5 };	fill(a, a + 5, 133);//將a[0]~a[4]均賦值為133	for (int i = 0; i < 5; i++)	{		printf("%d ", a[i]);//輸出133 133 133 133 133	}	return 0;}

6.sort()

顧名思義，sort()就是用來排序的函數(shù)，它根據(jù)具體情形使用不同的排序方法，效率較高。一般來說，不推薦使用C語言中的qsort函數(shù)，原因是qsort 用起來比較繁瑣，涉及很多指針的操作。

• 如何使用sort排序？

sort函數(shù)的使用必須加上頭文件"#include" 和 "using namespace std;"，其使用的方式如下：

sort(首元素地址（必填），尾元素地址的下一個地址（必填），比較函數(shù)（非必填）);

可以看到，sort的參數(shù)有三個，其中前兩個是必填的，而比較函數(shù)則可以根據(jù)需要填寫，如果不寫比較函數(shù)，則默認對前面給出的區(qū)間進行遞增排序。

示例如下：

#include#includeusing namespace std;int main(){	int a[6] = { 9,4,2,5,6,-1 };	//將a[0]~a[3]進行從小到大排序	sort(a, a + 4);	for (int i = 0; i < 6; i++)	{		printf("%d ", a[i]);//輸出2 4 5 9 6 -1	}	putchar("/n");	//將a[0]~a[5]進行從小到大排序	sort(a, a + 6);	for (int i = 0; i < 6; i++)	{		printf("%d ", a[i]);//輸出-1 2 4 5 6 9	}	return 0;}

【敲黑板】：特別需要注意理解的是尾元素地址的下一個地址！

對double數(shù)組進行排序：

#include#includeusing namespace std;int main(){	double a[] = { 1.4,-2.1,9 };	sort(a, a + 3);	for (int i = 0; i < 3; i++)	{		printf("%.1lf ", a[i]);	}	return 0;}

對char型數(shù)組進行排序（默認是字典序）

示例如下：

#include#includeusing namespace std;int main(){	char c[] = { "T", "W","A", "K" };	sort(c, c + 4);	for (int i = 0; i < 4; i++)	{		printf("%c", c[i]);//輸出AKTW	}	return 0;}

我們需要知道的是，如果對序列進行排序，那么序列中的元素一定要有可比性，因此需要制定排序規(guī)則來建立這種可比性。特別是像結構體，本身并沒有大小關系，需要認為制定比較的規(guī)則。sort 的第三個可選參數(shù)就是cmp函數(shù)，用來實現(xiàn)這個規(guī)則。

• 如何實現(xiàn)比較函數(shù)cmp

下面介紹對基本數(shù)據(jù)類型、結構體類型、STL容器進行自定義規(guī)則排序時cmp的寫法。

<1>.基本數(shù)據(jù)類型數(shù)組的排序

若比較函數(shù)不填，則默認按照從小到大的順序排序。

示例如下：

#include#includeusing namespace std;int main(){	int a[] = { 3,1,4,2 };	sort(a, a + 4);	for (int i = 0; i < 4; i++)	{		printf("%d ", a[i]);//輸出1 2 3 4	}	return 0;}

如果想要從大到小來排序，則要使用比較函數(shù)cmp 來“告訴”sort 何時要交換元素（讓元素的大小比較關系反過來）

示例如下：

#include#includeusing namespace std;bool cmp(int a, int b){	return a > b;//可以理解為當a>b時把a放在b前面}int main(){	int a[] = { 3,1,4,2 };	sort(a, a + 4, cmp);	for (int i = 0; i < 4; i++)	{		printf("%d ", a[i]);//輸出4 3 2 1	}	return 0;}

這樣就可以讓數(shù)值較大的元素放在前面，也就達到了從大到小排序的要求。

同樣的，對double型數(shù)組從大到小排序的代碼如下：

#include#includeusing namespace std;bool cmp(double a, double b){	return a > b;//同樣是a>b}int main(){	double a[] = { 1.4,-2.1,9 };	sort(a, a + 3, cmp);	for (int i = 0; i < 3; i++)	{		printf("%.1lf ", a[i]);//輸出9.0 1.4 -2.1	}	return 0;}

對char型數(shù)組從大到小排序如下：

#include#includeusing namespace std;bool cmp(char a, char b){	return a > b;//可以理解為當a>b時把a放在b之前}int main(){	char c[] = { "T","W","A","K" };	sort(c, c + 4, cmp);	for (int i = 0; i < 4; i++)	{		printf("%c", c[i]);//輸出WTKA	}	return 0;}

【記憶方法】：

如果要把數(shù)據(jù)從小到大排列，那么就用"<", 因為"a", 因為"a>b" 就是左大右小。而當不確定或者忘記的時候，不妨兩種都試一下，就會知道該用哪種了。

<2>.結構體數(shù)組的排序

現(xiàn)在定義了如下結構體：

struct node{    int x, y;}ssd[10];

如果想將ssd數(shù)組按照 x 從大到小排序（即進行一級排序），那么可以這樣寫cmp函數(shù)：

bool cmp(node a, node b){    return a.x > b.x;}

示例如下：

#include#includeusing namespace std;struct node{	int x;	int y;}ssd[10];bool cmp(node a, node b){	return a.x > b.x;//按x值從大到小對結構體數(shù)組進行排序}int main(){	ssd[0].x = 2;	ssd[0].y = 2;	ssd[1].x = 1;	ssd[1].y = 3;	ssd[2].x = 3;	ssd[2].y = 1;	sort(ssd, ssd + 3, cmp);	for (int i = 0; i < 3; i++)	{		printf("%d %d/n", ssd[i].x, ssd[i].y);	}	return 0;}

而如果想先按x 從大到小排序，但當x相等的情況下，按照y的大小從小到大來排序（即進行二級排序），那么cmp的寫法是：

bool cmp(node a, node b){    if(a.x != b.x)    {        return a.x > b.x;    }    else    {        return a.y < b.y;    }}

這里的cmp函數(shù)首先判斷結構體內的x 元素是否相等，如果不相等則直接按照x 的大小來排序，否則，按照y 的大小來排序。

示例如下：

#include#includeusing namespace std;struct node{	int x;	int y;}ssd[10];bool cmp(node a, node b){	if (a.x != b.x)	{		return a.x > b.x;//x 不等時按x 從大到小排序	}	else	{		return a.y < b.y;//x 相等時按y 從小到大排序	}}int main(){	ssd[0].x = 2;	ssd[0].y = 2;	ssd[1].x = 1;	ssd[1].y = 3;	ssd[2].x = 3;	ssd[2].y = 1;	sort(ssd, ssd + 3, cmp);//排序	for (int i = 0; i < 3; i++)	{		printf("%d %d/n", ssd[i].x, ssd[i].y);	}	return 0;}

<3>.容器的排序

在STL標準容器中，只有vector、string、deque是可以使用sort的。這是因為像set、map這種容器是用紅黑樹實現(xiàn)的（了解即可），元素本身有序，故不允許使用sort排序

vector示例如下：

#include#include#includeusing namespace std;bool cmp(int a, int b)//因為vector中的元素為int型，因此仍然是int的比較{	return a > b;}int main(){	vector vi;	vi.push_back(3);	vi.push_back(1);	vi.push_back(2);	sort(vi.begin(), vi.end(), cmp);	for (vector::iterator it = vi.begin(); it != vi.end(); it++)	{		printf("%d ", *it);//輸出3 2 1	}	return 0;}

再來看string 的排序，示例如下：

#include#include#includeusing namespace std;int main(){	string str[3] = { "bbbb", "cc", "aaa" };	sort(str, str + 3);//將string數(shù)組按字典樹從小到大輸出	for (int i = 0; i < 3; i++)	{		cout << str[i] << endl;	}	return 0;}

如果上面這個例子中，需要按照字符串長度從小到大排序，那么可以這樣寫：

#include#include#includeusing namespace std;bool cmp(string str1, string str2){	return str1.length() < str2.length();//按照string 的長度從小到大排序}int main(){	string str[3] = { "bbbb", "cc", "aaa" };	sort(str, str + 3, cmp);	for (int i = 0; i < 3; i++)	{		cout << str[i] << endl;	}	return 0;}

7.lower_bound()和upper_bound()

lower_bound() 和 upper_bound() 需要用在一個有序數(shù)組或容器中

lower_bound(first, last, val) 用來尋找在數(shù)組或容器的[first, last) 范圍內第一個值大于等于val元素的位置，如果是數(shù)組，則返回該位置的指針；如果是容器，則返回該位置的迭代器。

upper_bound(first, last, val) 用來尋找在數(shù)組或容器的[first, last) 范圍內第一個值大于val 的元素的位置，如果是數(shù)組，則返回該位置的指針；如果是容器，則返回該位置的迭代器。

顯然，如果數(shù)組或容器中沒有需要尋找的元素，則lower_bound() 和 upper_bound() 均返回可以插入該元素的位置的指針或迭代器（即假設存在該元素時，該元素應當在的位置）。

示例如下：?

#include#includeusing namespace std;int main(){	int a[10] = { 1,2,2,3,3,3,5,5,5,5 };	//尋找-1	int* lowerPos = lower_bound(a, a + 10, -1);	int* upperPos = upper_bound(a, a + 10, -1);	printf("%d %d/n", lowerPos - a, upperPos - a);//輸出0 0	//尋找1	lowerPos = lower_bound(a, a + 10, 1);	upperPos = upper_bound(a, a + 10, 1);	printf("%d %d/n", lowerPos - a, upperPos - a);//輸出0 1	//尋找3	lowerPos = lower_bound(a, a + 10, 3);	upperPos = upper_bound(a, a + 10, 3);	printf("%d %d/n", lowerPos - a, upperPos - a);//輸出3 6	//尋找4	lowerPos = lower_bound(a, a + 10, 4);	upperPos = upper_bound(a, a + 10, 4);	printf("%d %d/n", lowerPos - a, upperPos - a);//輸出6 6	//尋找6	lowerPos = lower_bound(a, a + 10, 6);	upperPos = upper_bound(a, a + 10, 6);	printf("%d %d/n", lowerPos - a, upperPos - a);//輸出10 10	return 0;}

顯然，如果只想獲得欲查元素的下標，就可以不使用臨時指針，而直接令返回值減去數(shù)組首地址即可。

【敲黑板】：這里補充一條知識點，指針 - 指針? = 兩指針之間的元素個數(shù)

示例如下：

#include#includeusing namespace std;int main(){	int a[10] = { 1,2,2,3,3,3,5,5,5,5 };	//尋找3	printf("%d %d/n", lower_bound(a, a + 10, 3) - a, upper_bound(a, a + 10, 3) - a);//輸出3 6	return 0;}

五、藍橋結語：遇見藍橋遇見你，不負代碼不負卿！

希望能給大家?guī)韼椭a字不易，如果可以動動小手來個三連那就更好啦，hh，咱們下次再見。

·