C++中常⽤函数以及类型总结
记录在刷题过程中经常⽤到的,总结⼀下加深印象,⽅便以后查询。
⽬录
vector(动态数组)
需要头⽂件<vector>
构造函数
vector<int> nums; //构造数据元素类型为int的空动态数组
vector<int> nums2(nums1); //构造元素与nums相同的动态数组(拷贝)
vector<int> nums(size); //数据元素类型为int,个数为size的动态数组
vector<int> nums(size,val); //数据元素类型为int,个数为size,初始值为val的动态数组
vector<int> nums[arraySize]; //定义长度为arraySize的vector动态数组数组。
访问 vector内元素有两种访问⽅式,通过下标或迭代器访问。
通过下标访问时和普通数组差不多,范围为(0到nums.size()-1)
通过迭代器访问如下:
vector<typename>::iterator it; //typename是类型名,通过*it 来访问
注意:
(nums[i]和*(it.begin()+i)等价)(it.end()是尾元素的下⼀个地址)
排序 需要头⽂件<algorithm>(具体细节见algorithm)
sort(nums.begin(),d());
nums.push_back(val); //在数组末尾插⼊⼀个值为val的 元素
string
头⽂件为<string>
⼦串
string s;
s.substr(begin,len) //返回字符串s从begin位置开始长度为len的⼦串。
list(双向链表)
头⽂件为<list>,list⽆法通过下标访问。
双向链表的每⼀个元素中都有⼀个指针指向后⼀个元素,也有⼀个指针指向前⼀个元素。
在 list 容器中,在已经定位到要增删元素的位置的情况下,增删元素能在常数时间内完成。(⽐vector要快)。
注意:list⽆法⽤algorithm中的sort进⾏排序,可以⽤⾃⼰的成员函数进⾏排序。
构造函数:
list<int> lst; //创建空list
list<int> lst1(5,5); //创建含有5个值为5的元素的list
list<int> lst2(lst); //⽤lst初始化lst2
常⽤函数:
list.begin()、d()
list.front()、list.back()
list.push_back(val)、list.push_front(val)
list.pop_back()、list.pop_front()
algorithm头⽂件下的常⽤函数
sort
sort(⾸元素地址(必须填),尾元素地址的下⼀个地址(必填),⽐较函数(⾮必填))
如果不写⽐较函数,默认对区间递增排序,实例如下(参考《算法笔记》)
注意: 在写cmp函数时,针对两个⽐较的对象,如果相等⼀定要返回false
数组的排序
#include<cstdio>
#include<algorithm>
using 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]);
return 0;
}
对于排序的指定规则,也可以⾃⼰定义,这时候就要⽤到sort的第三个可选参数cmp.使⽤sort对数组升序排列时,cmp函数的构造如下。
结构体数组的排序
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
return a > b; //可以理解为当a>b时,把a放在前⾯
}
int main(){
int a[6] = {9,4,2,5,6,-1};
//将a[0]~a[3]从⼤到⼩排序
sort(a,a+4,cmp);
for(int i = 0;i <6;i++)
printf("%d ",a[i]);
return 0;
}
使⽤sort也可以对结构体数组进⾏排序,使⽤⽅法见下例。
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int x,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; //{2,2}
ssd[1].x = 1;ssd[1].y = 3; //{1,3}
ssd[2].x = 3;ssd[2].y = 1; //{3,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;
}
容器的排序
在STL标准容器中,只有vector、string、deque是可以使⽤sort的,这是因为像map、set这种容器是⽤红⿊树实现的,元素本⾝有序,故不允许⽤sort排序.对vector排序的例⼦如下:
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){
return a >= b ; //降序
}
int main(){
vector<int> nums;
nums.push_back(3);
nums.push_back(1);
nums.push_back(2);
sort(nums.begin(),d(),cmp); //对整个vector排序
for(int i = 0;i <3;i++)
printf("%d ",nums[i]);
return 0;
}
如string等,其余类似。
next_permutation()
next_permutation()给出⼀个序列在全排列的下⼀个序列。
prev_permutation()给出⼀个序列在全排列的上⼀个序列。
例题:
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int nums[10000];
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&nums[i]);
字符串比较函数实现while(m--)
next_permutation(nums,nums+n);
for(int i=0;i<n;i++)
printf("%d ",nums[i]);
return 0;
}
max(),min(),abs(),reverse(),swap()
这些函数⽐较常⽤也⽐较容易,略。(使⽤reverse()也注意左闭右开)
fill()
int a[5] = {1,2,3,4,5};
fill(a,a+5,233); //将a[0]~a[4]均赋值为233。
set
set(集合)是⼀个内部⾃动有序且不含重复元素的容器。只能通过迭代器访问。
set<typename> name;
set<typename>::iterator it; //只能it++不能it+1的⽅式访问
常⽤函数:insert(),find(),erase(),size(),clear().
注意:
find(value)返回set中对应值为value的迭代器。set中没有该值时为.end(); map
需要头⽂件<map>
map的原理为红⿊数,查询复杂度为log(N)
map可以通过下标访问,或者通过迭代器访问。
map<typename1,typename2>::iterator it;
通过it->first来访问键,使⽤it->second来访问值。
构造函数
map<int,int> hashmap; //构造⼀个map对象hashmap,键:int型,值:int型插⼊
map<string,int> hashmap;
hashmap[“asd”] = 1; //直接插⼊,如果已经有键为"asd"的结点,则直接覆盖。
hashmap.insert(pair<string, int>(“aaa”,1)); //使⽤insert函数插⼊,如果结点已经存在,则⽆法插⼊(不会改变原来的值)删除
map<string,int> hashmap;
map<string,int>::iterator iter;
查
map<string,int> hashmap;
map<string,int>::iterator iter;
iter = hashmap.find(“asd”); //迭代器返回当前元素的位置,如果map中⽆该元素,则返回d()
int n = unt(“asd”); //因为map中不存在相同的元素,因此只能返回0或1.
queue
queue为队列(先进先出),需要头⽂件<queue>
queue<typename> name;
访问
只能通过front()来访问队⾸元素,通过back()来访问队尾元素。
push()⼊队,pop()出队。
通过empty(),queue为空返回true;
priority_queue
priority_queue(优先队列),头⽂件也是<queue>。
底层⽤堆来实现,队⾸元素是队列中优先级最⾼的⼀个。
priority_queue<typename> name;
访问
和queue队列不同,priority_queue优先队列没有front()和back()函数,只能通过top()函数来访问队⾸元素。
优先级设置
当优先队列的类型为可⽐较的类型时候,下列两种写法等价,以int类型为例。
priority_queue<int> q;
priority_queue<int,vector<int>,less<int> > q;
如果想把最⼩的元素放在队列⾸
priority_queue<int, vector<int>, greater<int> > q;
结构体的优先级设置。按price⾼为优先级⾼
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论