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()有两种用法：删除单个元素、删除一个区间内的所有元素。时间复杂度均为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.删除一个区间内的所有元素：有两种方法：

• str.erase(first, last), 其中first为需要删除的区间的起始迭代器，而last为需要删除的区间的末尾迭代器的下一个地址，即为删除[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为删除的字符个数。

示例如下：

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

(6).clear()

clear()可以清空string中的数据，时间复杂度一般为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是一个常数，其本身的值为-1 ，但由于是unsigned int 类型，因此实际上也可以认为是unsigned int 类型的最大值，可认为是4,294,967,295。string::npos 用以作为 find 函数失配时的返回值。

(9).find()

str.find(str) 当str2 是str 的子串时，返回其在str 中第一次出现的位置，如果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中主要则是实现一个先进先出的容器，当需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用queue代替，以提高程序的准确性。

1.queue的定义

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

其定义的写法和其他STL容器相同，typename 可以是任意基本数据类型和容器：

queue name;

2.queue容器内元素的访问

由于队列（queue）本身就是一种先进先出的限制性数据结构，因此在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常用函数实例解析

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

(1).push()

push(x) 将x 进行入队，时间复杂度为O(1)

(2).front(), back()

front(), back()可以分别获得队首元素和队尾元素，时间复杂度为O(1)

注意哦，使用front() 和 pop() 函数之前，必须用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内元素的个数，时间复杂度为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) 和优先队列(priority_queue) ，前者是首尾皆可插入和删除的队列，后者是使用堆实现的默许将当前队列最大元素置于队首的容器，这里暂时先不介绍，后期如果需要再进行补充。

三、stack的常见用法详解

stack 翻译为栈，是STL中实现的一个先进后出的容器，stack 用来模拟实现一些递归，防止程序对栈内存的限制而导致程序运行出错。

1.stack的定义

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

其定义的写法和其他STL容器相同，typename可以是任意基本数据类型或容器：

stack name;

2.stack容器内元素的访问

由于栈(stack) 本身就是一种先进后出的数据结构，在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常用函数实例解析

• 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 内元素的个数，时间复杂度为O(1)

四、algorithm头文件下的常用函数

使用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中的最大值和最小值，且参数必须是两个，可以是浮点数，如果想返回三个数x,y,z的最大值，可以使用max(x, max(y, z)) 的写法；abs(x) 返回x的绝对值。注意：此时的x 必须是整数，浮点数的绝对值请用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) 可以将数组指针在[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;}

在上述的代码中，使用循环是因为next_permutation在已经到达全排列的最后一个时会返回false, 这样会方便退出循环。而使用do...while语句而不使用while语句是因为序列1 2 3本身也需要输出，如果使用while会直接跳到下一个序列再输出，这样的话结果会少一个123

5.fill()

fill()可以把数组或容器中的某一段区间赋为某个相同的值。和memset 不同，这里的赋值可以是数组类型对应范围中的任意值

示例如下：

#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()就是用来排序的函数，它根据具体情形使用不同的排序方法，效率较高。一般来说，不推荐使用C语言中的qsort函数，原因是qsort 用起来比较繁琐，涉及很多指针的操作。

• 如何使用sort排序？

sort函数的使用必须加上头文件"#include" 和 "using namespace std;"，其使用的方式如下：

sort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数（非必填）);

可以看到，sort的参数有三个，其中前两个是必填的，而比较函数则可以根据需要填写，如果不写比较函数，则默认对前面给出的区间进行递增排序。

示例如下：

#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数组进行排序：

#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型数组进行排序（默认是字典序）

示例如下：

#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;}

我们需要知道的是，如果对序列进行排序，那么序列中的元素一定要有可比性，因此需要制定排序规则来建立这种可比性。特别是像结构体，本身并没有大小关系，需要认为制定比较的规则。sort 的第三个可选参数就是cmp函数，用来实现这个规则。

• 如何实现比较函数cmp

下面介绍对基本数据类型、结构体类型、STL容器进行自定义规则排序时cmp的写法。

<1>.基本数据类型数组的排序

若比较函数不填，则默认按照从小到大的顺序排序。

示例如下：

#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;}

如果想要从大到小来排序，则要使用比较函数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;}

这样就可以让数值较大的元素放在前面，也就达到了从大到小排序的要求。

同样的，对double型数组从大到小排序的代码如下：

#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型数组从大到小排序如下：

#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;}

【记忆方法】：

如果要把数据从小到大排列，那么就用"<", 因为"a", 因为"a>b" 就是左大右小。而当不确定或者忘记的时候，不妨两种都试一下，就会知道该用哪种了。

<2>.结构体数组的排序

现在定义了如下结构体：

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

如果想将ssd数组按照 x 从大到小排序（即进行一级排序），那么可以这样写cmp函数：

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值从大到小对结构体数组进行排序}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函数首先判断结构体内的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这种容器是用红黑树实现的（了解即可），元素本身有序，故不允许使用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数组按字典树从小到大输出	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() 需要用在一个有序数组或容器中

lower_bound(first, last, val) 用来寻找在数组或容器的[first, last) 范围内第一个值大于等于val元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

upper_bound(first, last, val) 用来寻找在数组或容器的[first, last) 范围内第一个值大于val 的元素的位置，如果是数组，则返回该位置的指针；如果是容器，则返回该位置的迭代器。

显然，如果数组或容器中没有需要寻找的元素，则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;}

显然，如果只想获得欲查元素的下标，就可以不使用临时指针，而直接令返回值减去数组首地址即可。

【敲黑板】：这里补充一条知识点，指针 - 指针  = 两指针之间的元素个数

示例如下：

#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;}

五、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿！

希望能给大家带来帮助，码字不易，如果可以动动小手来个三连那就更好啦，hh，咱们下次再见。

·