vector 动态数组 数组长度可以动态变化 (倍增思想)
头文件 #include<vector>
{
用法
vector <int> a;//定义一个数组名为a的动态数组,数据类型为整形
vector <int> a(n);//数组长度为n,n可以是数字
vector <int> a(n,3)//数组长度为n,其中每个数都初始化成3
vector <int> a[10]//定义了十个vector(二维,其中一维固定,一维可变长)
支持函数
a.size()//返回a的元素个数
a.empty()//判断a是否为空,空则返回true,否则返回false
//size,empty函数stl容器均拥有,时间复杂度为O(1)
a.clear()//清空容器(并非所有容器都有 如队列就没有)
a.front()//返回a中的第一个元素
a.back()//返回a中的最后一个元素
a.push_back()//在a最后插入一个元素
a.pop_back()//删除啊的最后一个元素
a.begin()//a的第0个数
a.end()//a最后一个数的后一个数
支持随机选址(同数组)
支持比较运算(按字典序)
}
优化目标:减少申请次数(系统为某一程序分配空间时,所需时间与空间大小无关,与申请次数有关)————倍增思想,每次当数组空间不够时,就将空间大小乘以二。
遍历
1.朴素遍历
for(i=0;i<a.size();i++)cout<<a[i]<<endl;
2.迭代器遍历
for(vector<int>::iterator i=a.begin();i!=a.end();i++)cout<<*i<<endl;
3.范围遍历(代码略短,效率略高,c++11新增)
for(auto x:a)cout<<x<<endl;
pair<int,int>可以存储一个二元组
{
定义
pair<int,string>p//可以前后不同数据类型
用法
first,第一个元素
second,第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字,按字典序排序。
p=make_pair(10,"yxc");
p={20,"abc"};
}
string 字符串数组
{
用法
substr(a,b)//返回下标a开始长度为b的子串,没有b则返回从a开始到最后的子串
c_str()//返回数组头地址
size()/length()//返回元素个数
empty()//返回是否为空
clear()//清空字符串
a+=b//把字符或字符串b接到字符串a后面
}
queue 队列–先进先出
头文件 #include <queue>
{
queue<int>q;
push()//往队尾插入
front()//返回队头元素
pop()//弹出队头元素
q=queue<int>//清空q元素
}
priority_queue 优先队列(堆)
文件头 #include <queue>
{
定义
priority_queue<int>heap;//默认大根堆
用法
push()//向栈顶插入元素
top()//返回栈顶元素
pop()//弹出栈顶元素
}
stack 栈–先进后出
头文件#include <stack>
{
push()//向栈顶插入元素
top()//返回栈顶元素
pop()//弹出栈顶元素
}
deque 双端队列 对头队尾都支持插入弹出,可以支持随机访问(加强版vector)
缺点(速度慢)
头文件 #include<deque>
{
size()
empty()
clear()
front()
back()
push_back()
pop_back()
push_front()
pop_front()
}
set,map,multiset,multimap 基于平衡二叉树的一种实现(红黑树),本质上是动态维护有序序列
{
set,multiset
头文件 #include<set>
{
set<int>S;
//set中不含重复元素,如果插入重复元素会被忽略
insert()//插入一个数
find()//查找一个数
count()//返回一个元素出现次数(0或1)
erase(x)//删除所有x
lower_bound()//返回大于等于x最小的数
upper_bound()//返回大于x最小的数
//multiset中可以含有重复元素
insert()//插入一个数
find()//查找一个数
count()//返回一个元素出现次数
erase(x)//删除所有x
lower_bound()//返回大于等于x最小的数
upper_bound()//返回大于x最小的数
}
map,maltimap
操作大多时间复杂度O(logn)
头文件 #include <map>
{
map<string,int>a//将string型映射到整形
a["yxc"]=1;
insert()//插入的数是一个pair
earse()//输入的是pair或者迭代器
find()
}
}
unordered_set,unordered_map,unordered_multiset,unordered_multimap 基于哈希表实现
类似上面,增删改查时间复杂度O(1)
不支持lower_bound()/upper_bound(),不支持和排序有关的操作
头文件#inxlude<unordered_map>
bitset 压位
bool一个元素1字节,压位后为8位
{
bitset<10000>s;//长度10000的容器
支持所有位运算
~,&,|,^
<<,>>
==,!=
count()//返回有多少个1
any()//判断有没有1
none()//判断是否均为0
set()//把所有位置1
set(k,v)//把k变成1
reset()//把所有位置0
flip()//所有位取反
flip(k)//k位取反
}
爱了