变长数组

头文件 vector

1. 初始化

vector<int> a(10); //也可不定义数量
vector<int> a(10,1); //每个元素给初值
vector<int> a(b); //用b来初始化a，拷贝构造
vector<int> a(b.begin(),b.bengin()+3);//部分元素拷贝
int b[3]={1,2,3}; vector<int> a(b,b+2);//数组构造

2. 赋值

a.push_back(x)//在a的最后插入元素x
a.back() //返回最后一个元素
a.front() //返回第一个元素
a.clear() //清空
a.empty() //是否为空
a.pop_back() //删除最后一个元素
a.erase(a.begin()+i,a.begin()+j)//删除任意区间元素
a.insert(a.begin()+i,x)//在位置i插入元素x
a.insert(a.begin()+i,m,x)//在位置i插入m个x
a.size() //返回a的元素个数
a.resize(10)//将a的数量调整为10，多删少补
a.resize(10,2)//将a的数量调整为10，多删少补,补的值为2
a.swap(b) //a，b交换
a==b //a,b是否相等   

3. 排序

voctor排序：

sort(s.begin(),s.end(),[](vector<int> a,vector<int> b){
      return a[1]<b[1]; 
    });//按照s[i][1]升序排序

sort(s.begin(),s.end(),[](vector<int> a,vector<int> b){
      return a[0]>b[0]; 
    });//按照s[i][0]降序排序

结构体排序

struct Node{
    int a,b;
    bool operator< (const Node& t)const{
        return b<t.b;
    }
}q[N];//之后调用sort(q,q+N)按照q[i].b升序排序

当排序数量很大时，结构体排序比vector排序快很多，示例如下：

vector<vector<int>> s(N);
for(int i=0;i<N;i++)
{
    s[i].resize(2);
    s[i][0]=rand()%100;
    s[i][1]=rand()%100;
}

start=clock();
sort(s.begin(),s.end(),[](vector<int> a,vector<int> b){
  return a[1]<b[1]; 
});
end=clock();
double endtime=(double)(end-start)/CLOCKS_PER_SEC;//t=670ms

start=clock();
for(int i=0;i<N;i++)
{
    q[i].a=s[i][0];
    q[i].b=s[i][1];
}
sort(q,q+N);
end=clock();
double endtime=(double)(end-start)/CLOCKS_PER_SEC;//t=28ms

4. 其他用法

reverse(a.begin(),a.end()) //从后往前排列vector 并不是倒序排序
all.erase(unique(all.begin(),all.end()),all.end());//去重。unique将相邻且重复的元素放到末尾，所需要先排序

队列

头文件 queue

基本操作

q.empty()               如果队列为空返回true，否则返回false
q.size()                返回队列中元素的个数
q.pop()                 删除队列首元素但不返回其值
q.push()                在队尾压入新元素
q.front()               返回队首元素的值，但不删除该元素
q.back()                返回队列尾元素的值，但不删除该元素

优先队列

• 定义：priority_queue< Type, Container, Functional >
• 基本操作和普通队列一致

//升序队列，小根堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大根堆,默认情况
priority_queue <int,vector<int>,less<int> >q;
priority_queue<int> q; //同上
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

// 当有自己的结构体时
struct node{
    int v;
    // 和less配合，实现大根堆
    bool operator <(const node& t){
        return v < t.v;
    }
    // 和greater配合，实现小根堆
    bool operator >(const node& t){
        return v > t.v;
    }
}
priority_queue<node, vector<node>, less<node>> A // 大根堆
priority_queue<node, vector<node>, greater<node>> B // 小根堆

// 当没有结构体时，需要自己重载()运算符
struct cmp{
    bool operator()(node a, node b){
        return a.v > b.v;// 小根堆
        // return a.b < b.v; // 大根堆
    }
};
priority_queue<node, vector<node>, cmp> C;

哈希表

头文件 unordered_map

1.基本操作

unordered_map内部无序排列，和插入顺序无关

unordered_map<char,int> s={{'c',1},{'d',2}}//初始化，常用数类型都可以当作键和值
s['c']=1//通过数组的方式直接插入
s.insert({{'a',1},{'c',3}})//插入多组数据
s['c']//取值,如果不存在则输出空，如果值的类型是int、float、double则会输出0
s.empty()//判空
s.erase('c')//通过键值删除
s.count('c')//查询键是否存在
bool flag=s.find('c')!=s.end()//查找，flag=1,存在键值
for(auto& [k,v]:s) //遍历
    cout<<k<<' '<<v<<endl; 

头文件 unordered_set

1.基本操作

unordered_set内部无序排列，和插入顺序无关

unordered_set<int> s={1,2,3}//初始化
s.insert(1)//插入单个数据
s.insert({1，2，3})//插入多组数据
s.count(1)//查询1在set中是否存在
s.erase(1)//删除元素1
bool flag=s.find(1)!=s.end()//查询1在set中是否存在

头文件 list

其本质为双向链表

1.基本操作

// 初始化
list<int> l;
list<pair<int, int>> l;
// 插入元素
l.push_front(3); // 在表头插入元素
l.push_back(3); // 在表尾插入元素
// 拼接
l.splice(l.begin(), l, l.end()); // 参数1：想插入的位置，插在该位置之前；参数2：待操作的链表；参数3：要被移动的元素