vector

变长数组，支持随机访问，但是不支持任意位置O(1)插入，只能在头或末尾插入

为了保证效率，元素增删一般在末尾进行

声明
#include<vector>
vector<int> a;//int类型的数组
vector<int> b[233];//第一维度长233（列数）固定，第二维度可以改变（列数）
struct tec{
    int x,y;
}
vector<rec> c;
//vector后面<>中添加类型,定义为结构体

函数

a.size()返回数组的大小
a.empty()返回数组是否为空，true or false
clear()//把当前数组清空

迭代器

类型于stl容器中的指针，可以用操作符解除引用（用即可返回具体的值）
```
vector<int>::iterator it;
```
随机访问迭代器，可以把vector的迭代器与一个整数相加减，行为和指针的移动类似
两个迭代器相减，结果与指针相减类似，得到两个迭代器之间的距离
*a.begin()和a[0]效果一样
初始化
```
vector<int> a({1,2,3});
```
begin/end
begin函数返回指向vector中的第一个元素的迭代器
*a.begin() == a[0]
所有的容器都可以视作一个前闭后开的结构
end函数返回vector的尾部，即vector数组的末尾的下一个位置
*a.end() == a[n] 都是越界访问，其中n = a.size()

front/back

front返回vector的第一个元素，a.front() == a[0] == *a.begin()
back返回vector的最后一个元素，a.back() == a[a.size()-1] == *a.end()

push_back() / pop_back()

a.push_back(x)将x插入到vector的尾部
b.pop_back(),删除vector a的最后一个元素

queue 循环队列

先进先出

priority queue 优先队列

会优先往外弹最大值

声明
queue<int> q;
priority_queue<int> a;//大根堆
priority_queue<int,vector<int>,greater<int>> b;//小根堆
priority_queue<pair<int,int>> a;//定义的是二元组

重载大于号

struct Rec
{
    int a,b;
    bool operator > (const Rec& t) const{
        return a > t.a;
    }
}
priority_queue(Rec) d;

循环队列queue

如果越界了会从头开始循环
push //从队尾插入
pop //从队头弹出
front //返回队头元素
back //返回队尾元素

优先队列priority_queue

push //把元素插入堆
pop //删除堆顶元素(优先队列中队头即为最大值)
top //查询堆顶元素

注意：除了队列，栈，其余都有clear函数

清空队列直接初始化
q = queue();

栈stack

头文件stack,和队列相反，先进后出

stack<int> stk;
stk.push(1);
stk.top();
stk.pop();

双端队列

头文件
支持在两端高效插入或删除元素的连续线性存储空间
相当于是一个拓展版的vector
二者在队尾插入元素时间复杂度都是O(1)

在队头插入，vector是O(n),deque是O(n)

deque<int> a;//定义
a.begin()
a.end()
a.front()
a.back()
a.push_back()//在队尾插入一个元素
a.push_front()//在对头插入一个元素
a[0]//支持取下标随机访问一个元素
a.pop_front()//在对头弹出一个元素
a.pop_back()//在队尾弹出一个一元素

为了避免边界处理问题，都从0开始遍历，存到n-1

循环队列，优先队列，栈，双端队列都没有迭代器

循环队列，优先队列和栈没有clear()函数，其他都有

set

包括set和multiset两个容器，分别是有序集合和有序多重集合

有序集合(set)的元素不能重复，但是有序多重集合(multiset)可以包含若干个相等的元素

set<int> s;
struct Rec{
    ...
};
set<Rec> s;//rec中必须重载小于号
multiset<double> s;

size()

empty()

clear()

迭代器

set

set<int> a;
multiset<double> b;
struct Rec{
    int a,b;
}
set<Rec> c;//注意这个地方需要重载小于号

支持size,empty,clear
迭代器，双向访问迭代器,支持*接触引用，仅支持++和–两个与算数有关的操作
不支持随机访问操作，类似于
```
set<int>::iterator itt = a.begin()
cout << *(itt+3) << endl;
```
会报错，因为仅支持上一个或下一个的操作，一次跳转多个的算是随机访问
插入一个元素,因为是集合，具有无序性，所以insert的时候是无序的
```
a.insert(x)
```
查找
```
s.find(x)
```
在集合中查找等于x的元素，并返回该元素的迭代器，如果不存在则返回s.end()
lower_bound/upper_bound
s.lower_bound(x),查找大于等于x的元素的最小的一个，并且返回该元素的迭代器
s.upper_bound(x),查找大于x的元素中最小的一个，并且返回该元素的迭代器
erase
如果it是一个迭代器，s.erase(it)从it中删除迭代器it指向的元素
如果x是一个元素，s.erase(x)从s中删除所有等于x的元素
count()
返回s中等于x的元素个数，因为是集合，所以只有0和1会返回，但如果是multiset(x),则会返回x在multiset中存在的个数，因为multiset允许重复

map

一个键值对的key-value的映射

map的key和value可以是任意类型，其中key

a[1] = 2;//在a[1]的位置插入2
a[1000000] = 3;//在key所在的位置插入3

和数组的区别：前后两个结构体是可以自由定义的
```
a["abc"] = 2;
cout << a["abc"] << endl;
结果是2
```
size,empty,clear,begin,end都和set类似
insert’erase,参数必须是pair<key_type,value_type>,即插入的时候必须令键的类型和值的类型相匹配

pair

二元组

pair<int,string> a;
a = {3,"yxc"};
cout << a.first << ' ' << a.second << endl;

pair支持比较运算，先比较first,再比较second

位运算

与 &

0&0 == 0
0&1 == 0
1&1 == 1

或 |

0|0 == 0
1 | 0 == 1
0 | 1 == 1
1 | 1 == 1

非 ~

~0 == 1
~1 == 0

异或 ^ XOR

不进位加法
0 ^ 0 == 0
1 ^ 1 =0
1 ^ 0 == 1
0 ^ 1 == 1
按照每一位进行按位异或

右移 >>

求x的第k位数字:x >> k & 1
右移k位相当于除以2的k次方

左移 <<

左移k位相当于乘以2的k次方

求一个数的二进制表示方法：

int a = 13;
for(int i = n;i >= 0;i --){
    cout << (a >> i & 1)
}
这里的5是最大求到2的多少次方的位数，0是2的0次方，从n到2的0次方依次提出来

返回x的最后一位1:

lowbit(x) = x & -x

常用库函数

在算法库中

reverse

反转数组

vector<int> a;
reverse(a.begin(),a.end());
//反转数组
reverse(a,a+a.size()+1);//a的首部位置和a的最后一个元素的下一个位置

unique

数组判重，然后将元素放到数组开头的位置,但是重复的元素只是放到后面，不是删除
返回值：不同元素的下一个位置的指针

注意：只是去掉相邻的相同元素，必要时需要sort排序

int m = unique(a.begin(),a.end()) - a.begin()
//返回的差值是数组中不同元素的个数

random_shuffle()

参数和reverse()函数一样
```
random_shuffle(a.begin(),a.end());
```
打乱数组
random_shuffle(a.begin(),a.end());
随机种子不一样，打乱顺序不一样
一般引用库中的time(0)函数，生成种子；

sort

sort(a.begin(),a.end())从小到大

如果希望从大到小排序，则需要加上一个参数greater()

sort(a.begin(),a.end(),greater<int>())
3. 按照自己的想法进行排序，自己写一个cmp

bool cmp(int a,int b){//a是否应该排在b的前面
    return a > b;//从大到小
    return a < b;//从小到大
    //如果a应该排在b的前面，返回true,否则返回false
}

如果需要重载大于或小于号的写法

bool opeartor< (const Rec &t) const
{
    return x < t.x;
}