欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

22/1/31STL

时间:2023-06-06
一、map(映射)

其实,数组就是一种映射。

int a[100];//定义了一个int到int的映射a[5]=25;//5映射到25

数组总是将int类型映射到其他基本类型(称为数组的基类型),同时带来一个问题:string映射成int,数组就不方便。这时就可以用map。
map可以将任何基本类型(包括STL容器)映射到任何基本类型(包括STL容器)。

(一)、map的用途

至少有以下三种情形
**1、**需要建立字符(串)与整数之间的映射,用map可以减少代码量
**2、**判断大整数(比如几千位)或者其他类型数据是否存在,可以把map当做布尔型数组使用(哈希表)
**3、**字符串与字符串之间的映射

#include //头文件using namespace std;mapname; //定义一个map

普通int数组a就是map a。
而如果是字符串到整型的映射,就必须使用string,而不能使用char,即map a。
map的键和值也可以是STL容器,比如:map mp。
当然,map的键和值都是唯一的

(二)、map 的访问

访问 map 的元素有两种方式,一种是通过下标访问;另一种是通过迭代器访问。
通过下标访问就像普通的数组元素访问,例如先定义map mp,然后就可以通过mp[‘c’]的方式来访问它对应的元素,如mp[‘c’]=124。
通过迭代器访问,先作如下定义:

map::iterator it;

因为map的每一对映射都有两个typename,所以,我们使用“it->first”来访问键,而使用“it->second”来访问值。

(三)、map 的常用函数

1、find()和 size()
find(key)是返回键为 key 的映射的迭代器,时间复杂度为 0(log2 n),n 为 map 中映射的对数。
size()用来获得map中映射的对数,时间复杂度为O(1)。
2、clear()
用来清空 map,时间复杂度为 0(n)。
3、erase()
erase()可以删除单个元素,也可以删除一个区间内的所有元素。
1)删除单个元素
①erase(it),it为要删除的元素的迭代器,时间复杂度为O(1)。
②erase(key),key为要删除的映射的键,时间复杂度为O(log2 n)。
2)删除一个区间内的所有元素
erase(first,last),first为区间的起始迭代器,last为区间的末尾迭代器的下一个地址,也就是左闭右开的区间[first,last),时间复杂度为O(last-first)。

二、pair

pair 是“二元结构体”的替代品,将两个元素捆绑在一起,节省编码时间。

#include//头文件using namespace std;pairname;//定义//两个typename均可以是任意基本数据类型或者容器

相当于以下定义

struct pair{typename1 first;typename2 second;}

三、set(集合)

set是一个内部自动有序且不含重复元素的容器。
set 最主要的作用就是自动去重并按升序排序,因此遇到需要去重但是又不方便直接开数组的情况时可以使用。
set 中的元素是唯一的,其内部采用“红黑树”实现。

#include ;using namespace std;set name;//typename 可以是任何基本类型或者容器,name 是集合的名字

(一)、set常用函数

1、insert()
插入一个元素
注意如果集合中已经存在某元素,再次插入不会产生任何效果,即集合中不会出现重复元素。
2、erase()
删除一个元素。若集合中不存在这个元素,不进行任何操作。

erase(iterator) ;//删除定位器iterator指向的值erase(first,second);//删除定位器first和second之间的值erase(key_value);//删除键值key_value的值

set s;set::const_iterator iter;set::iterator first;set::iterator second;for(int i = 1 ; i <= 200 ; ++i){s.insert(i);} s.erase(s.begin());//第一种删除first = s.begin();second = s.begin();second++; second++;s.erase(first,second);//第二种删除s.erase(18);//第三种删除

lower_bound(key_value) ,返回第一个大于等于key_value的定位器
upper_bound(key_value),返回最后一个大于等于key_value的定位器

set s;s.insert(1);s.insert(3);s.insert(4);cout<<*s.lower_bound(2)<

3、count()
判断元素是否在set中

#includeusing namespace std;int main(){sets;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"1出现的次数:"<

4、size()
获取元素个数
5、clear()
清空

(二)、set的访问

set只能通过迭代器访问

set::iterator it;for(it = s.begin() ; it != s.end() ; ++it) cout<<*it<<" ";

四、vector(向量/ 变长数组)

“长度根据需要而自动改变的数组”
需要定义很大数组时可能出现“超出内存限制”的错误,如图的顶点太多,使用邻接矩阵时会超出内存限制、使用指针实现邻接表有很容易出错,使用vector实现简洁方便且节省存储空间。

#includeusing namespace std;vectorname;

以上定义相当于定义了一个一维数组name[size],但size不确定,长度可以根据需要而变化。

(一)、访问 vector 中的元素一般有两种方式

1、通过“下标”访问。
例如,对于容器 vector v,可以使用 v[index]来访问它的第 index 个元素。其中,0≤index≤v.size()-1,v.size()表示 vector 中元素的个数。
2、通过“迭代器”访问。
可以将迭代器(iterator)理解为一种类似指针的变量。其定义为:

vector::iterator it;

例如:

vector::iterator it= v.begin();for(int i = 0; i <= 5; i++) printf("%d ",*(it + i));

(二)、vector常用函数

1、push_back()
push_back(x)用来在 vector 后面添加一个元素 x,时间复杂度为 0(1)。
2、size()
如果是一维数组,size()用来获得 vector 中元素的个数;
如果是二维数组,size()用来获得vector 中第二维的元素个数,时间复杂度为 0 (1)。
3、pop_back()
pop_back()用来删除 vector 的尾元素,时间复杂度为 0(1)。
4、clear()
clear()用来清空 vector 中的所有元素,时间复杂度为 0(n),其中 n 为 vector 中元素的个数。
5、insert ()
insert(it,x)用来向 vector 任意迭代器 it 处插入一个元素 x,时间复杂度为 0(n)。
6、erase()
erase()用来删除 vector 中的元素,有两种用法。
一种是 erase(it),删除迭代器 it 处的元素;
另一种是 erase(first,last),删除左闭右开区间[first,last)内的所有元素。

五、string

在C语言中,一般使用字符数组char str[]来存放字符串,但是操作麻烦,容易出错。C++在STL中加入了string类型,对字符串常用的需求功能进行了封装,使得操作起来更加方便,且不必担心内存是否足够、字符串的长度等问题。

#includeusing namespace std;string name;string str="hello";

(一)、string的访问

1、就像普通字符数组一样操作。

string str= “ abcd “ ;for(int i = 0; i < str.length(); i++) printf( “ %c “ ,str[i]);// 输出 abcd

如果要读入或者输出整个字符串,一般只用cin和cout。如果非要用printf,则需要用c_str()将string转换成字符数组。

string str; cin>>str; cout<

2、通过迭代器,主要与insert()、erase()等函数配合使用。
先定义string迭代器:

string::iterator it;

然后就可以通过“*it”来访问string里的每一个字符了,而且string和vector一样,支持直接对迭代器进行加减某个数字,如str.begin()+3等。例如:

string str="abcdefg";for(string::iterator it = str.begin()+2; it != str.end(); it++)printf("%c",*it);//输出cdefg

(二)、string的运算

1、“加法”运算。加法是把两个字符串直接拼接起来。例如:

string str1= “ abc “ ,str2= “ xyz “ ,str3;str3 = str1 + str2;str1 += str2;cout << str1 << endl;// 输出 abcxyzcout << str3 << endl;// 输出 abcxyz

2、“关系”运算,是按照字典序比较两个string 类型的大小。例如:

string str1= “ aa “ ,str2= “ aaa “ ,str3= “ abc “ ;if(str1 < str2) printf( "OK1");// 输出 OK1if(str1 < str3) printf( "OK2" );// 输出 OK2

(三)、string的常用函数

1、length()和size()
都是用来返回string的长度(字符个数),时间复杂度O(1)。
2、clear()
清空string中所有元素,时间复杂度O(1)。
3、substr(pos,len)
返回从pos号位置开始、长度为len的子串,时间复杂度O(n)
4、insert()
多种写法,时间复杂度都是O(n)。
insert(pos,string) 表示在pos号位置插入字符串string。
insert(it,it2,it3) it为原字符串的欲插入位置,it2和it3为待插入字符串的首尾迭代器(左闭右开区间)。
5、erase()
erase()可以删除单个元素,也可以删除一个区间内的所有元素,时间复杂度均为O (n)。
1)erase(it) 删除单个元素,it为要删除的元素的迭代器。
2)删除一个区间内的所有元素可以用两种方法。
①erase(first,last),first为区间的起始迭代器,last为区间的末尾迭代器的下一个地址,也就是左闭右开的区间[first,last)。
②erase(pos,length),pos为需要删除的字符串起始位置,length为要删除的字符个数。
6、find()
1)str.find(str2),当str2是str的子串时,返回其在str中第一次出现的位置;否则返回string::npos。string::npos是一个常数,其本身的值等于-1,但由于是unsigned int类型,因此,也可以认为是unsigned int类型的最大值(4294967295)。
2)str.find(str2,pos),是从str的pos号位开始匹配str2,返回值同str.find(str2)。
以上两种写法的时间复杂度都是O(n*m),其中n和m分别为str和str2的长度。
7、replace()
str.replace(pos,len,str2)表示把str从pos号位开始、长度为len的子串替换为str2。也可以写成str.replace(it1,it2,str2),表示把str的迭代器it1~it2范围内(左闭右开区间)的子串替换为str2。
时间复杂度都是O(str.length)。

补充函数 1、max()、min()、abs()和 swap()

max(x,y)和min(x,y)分别返回 x 和 y 中的较大值和较小值,且参数必须是两个,可以是浮点数。如果要返回 3 个数 x、y、z 的最大值,可以使用max(x,max(y,z))的方法。
abs(x)是返回 x 的绝对值,x 必须是整数。如果要求浮点数的绝对值,可以使用 math 头文件下的 fabs(x)。
swap(x,y)用来交换 x 和 y 的值。

2、reverse()

reverse(it,it2)可以将数组指针在 [it ~ it2)之间的元素,或容器的迭代器在[it ~ it2)范围内的所有元素进行反转。

int a[10] = {10,11,12,13,14,15};reverse(a,a+4);//将a[0]到a[3]这4个元素反转for(int i = 0; i < 6; i++) printf("%d ",a[i]);//输出13 12 11 10 14 15string str = "abcdefghi";reverse(str.begin()+2,str.begin()+6);for(int i = 0; i < str.length(); i++) printf("%c",str[i]);//输出abfedcghi

3、next_permutation()

求出一个序列在全排列中的下一个序列。
例如,n=3 的全排列为:123,132,213,231,312,321,所以 231 的下一个排列就是 312。

int a[10] = {1,2,3};do{printf("%d %d %dn",a[0],a[1],a[2]);}while(next_permutation(a,a+3));//a[0],a[1],a[2]三个元素的排列//next_permutation在达到全排列的最后一个时会返回false

4、fill () 和memset的区别

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

int a[5];fill(a,a+5,123);// 将 a[0] 到 a[4] 均赋值为 123for(int i = 0;i < 5;i++) printf( “ %d “ ,a[i]);

memset 只能赋值0和-1,赋值1的话,值为正整数。

5、sort(排序)

使用的排序方法类似于快排,时间复杂度为n*log2(n),效率较高。

#includesort(start,end,compare());//从小到大的排序bool compare(int a,int b){return a>b;}sort(a,a+10,compare);

compare()也可以用c++标准库的函数

less()//从小到大排序greater()//从大到小排序

6、unique(去重)

去重,即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除,指重复元素的位置被不重复的元素给占领了,重复的元素排到了后面(也就是仍然在数组中)。
由于它”删除”的是相邻的重复元素,所以在使用unique函数之前,一般都会将目标序列进行排序。
两种访问方式
1、unique(start,end)
同sort

#include #include using namespace std;int a[10]={5,8,5,12,6,8,9,5,12,3};int len;//无重复元素的数组的长度 int main(){sort(a,a+10);//先排序len=unique(a,a+10)-a;//去重,返回的是a去重后的尾地址。for(int i=0;i 2、迭代器

iterator unique(iterator it_1,iterator it_2);

对容器中[it_1,it_2)范围的元素进行去重,返回值是一个迭代器,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
和erase函数一起使用可以删除重复元素,容器的长度也发生了改变。

vector a ={1,3,3,4,4,9}; vector::iterator it1 = a.begin(); vector::iterator it2 = a.end(); vector::iterator newend; newend = unique(it1,it2); //注意unique的返回值 a.erase(newend,it2);

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。