【PAT】第六章 C++标准模板库介绍

2022-08-03 21:00:56

第六章 C++标准模板库介绍

6.3 string的常见用法

头文件：#include 和 using namespace std;

6.3.1 string的访问

1. 通过下标直接访问

2. 通过迭代器访问

string和vector的迭代器，支持对迭代器直接进行加减某个数字。

【注意】end()指向的是最后一个元素的下一个，而非最后一个元素。

string::iterator it;

#include <cstdio>
#include <string>
using namespace std;

int main()
{
	string str="abcd";
	for(string::iterator it=str.begin();it!=str.end();it++)
		printf("%c",*it);
	return 0;
}

6.3.2 `string`常用函数

1. operator+=

拼接两个string。

2. compare operator

两个string可以直接用==、!=、<、<=、>、>=比较大小。默认按字典序比较。

3. length()/size()

length()返回string的长度，即存放的字符数，时间复杂度为O(1)。size()与length()基本相同。

4. insert()

复杂度：O(n)

insert(pos,string)：在pos的位置处插入字符串string。
insert(it,it2,it3)：it为插入位置，it2和it3为要插入字符串的首尾迭代器，表示将串[it2,it3)插入到it位置上。

#include <cstdio>
#include <string>
using namespace std;

int main()
{
	string str="abcxyz",str2="opq";
	str.insert(str.begin()+3,str2.begin(),str2.end());
	return 0;
}

5. erase()

复杂度：O(n)

删除单个元素:erase(it)。it为需要删除的元素的迭代器。

#include <cstdio>
#include <string>
using namespace std;

int main()
{
	string str="abcxyz";
	str.erase(str.begin()+4);
	return 0;
}

删除一个区间内所有的元素：erase(first,last)。first和last为区间的首尾迭代器，即删除[first,last)。

#include <cstdio>
#include <string>
using namespace std;

int main()
{
	string str="abcxyz";
	str.erase(str.begin()+4,str.end());
	return 0;
}

删除一个区间内所有的元素：erase(pos,length)。pos为删除的起始地址，length为删除的字符个数。

#include <cstdio>
#include <string>
using namespace std;

int main()
{
   string str="abcxyz";
   str.erase(3,2);
   return 0;
}

6. clear()

清空string中的数据，时间复杂度为O(1)。

7. substr()

substr(pos,len)：返回从pos位置开始，长度为len的子串，时间复杂度为O（len）。

8 string::npos

string::npos是一个常数，本身值为-1。unsigned_int类型数据，可以认为是unsigned_int类型的最大值。

9. find()

str.find(str2)：当str2是str的子串时，返回其在str中第一次出现的位置，否则返回string::npos。
str.find(str2,pos)：从pos位置开始匹配str2，返回其在之后第一次出现的位置，否则返回string::npos。

10.replace()

str.replace(pos,len,str2)：把str从pos位置开始的长度为len的字串替换成str2。
str.replace(it1,it2,str2)：把str的迭代器[it1,it2)范围的子串替换为str2。时间复杂度为O(str2.length())。

【例】A1060

6.4 map的常用函数

将任意基本类型（包括STL）映射到任意基本类型（包括STL）上，形成有序键值对。键唯一。
头文件：#include 和 using namespace std;

6.4.1 map的定义

map<typename1,typename2> mp;
字符串必须使用string，不能使用字符数组。

6.4.2 map内元素的访问

1. 下标访问

map<char,int> mp;
mp['c']

2. 迭代器访问

map<typename1,typename2> ::iterator it;
it->first访问键，it->second访问值。

6.4.3 map常用函数

1. find()

find(key)返回键为key的映射的迭代器，时间复杂度为O(logn)。

2. erase()

删除单个元素
mp.erase(it)
mp.erase(key)
删除一个区间内的元素
mp.erase(first,last)

3.size()

获得map中键值对的对数。

4. clear()

清空map。

6.4.4 map的常见用途

6.9 algorithm头文件下的常见函数

6.9.6 sort()

头文件：#include <algorithm> 和 using namespace std;

1. 具体使用

sort(首元素地址,尾元素元素地址的下一个地址(首元素地址+数组大小),比较函数(非必填,默认递增排序));

2. 比较函数cmp

2.1 基本数据类型：

递减排序

bool cmp(int a,int b)
{
	return a>b; 	//左大右小
}

2.2 结构体数组的排序

#include <cstdio>
#include <algorithm>
using namespace std;

struct node{
	int x,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相等时按从小到大排序 
}
int main()
{
	...
	sort(ssd,ssd+10;cmp); 
}

2.3 容器的排序

只有vector、string、deque可以使用sort。


#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(T a,T b)
{
	return a>b;
}
int main()
{
	
	vector<T> vi;
	...
	sort(vi.begin(),vi.end(),cmp);
}

码农公寓