vector

变长数组

因为系统为某一程序分配空间时，所需时间与空间大小无关，与申请次数有关。

所以vector时间复杂度的优化是减少申请的次数，使用了倍增的思想。每当超过vector的长度时，会申请双倍的空间。

vector的常用函数

常用函数	含义
v.size()	返回元素个数
v.empty	返回是否为空
v.clear()	清空
v.front()	返回第一个元素
v.back()	返回最后一个元素
v.push_back()	在最后插入一个数
v.pop_back()	删除最后一个数
v.begin()	返回第一个元素的迭代器
v.end()	返回尾后元素的迭代器

遍历vector的三种方式

vector<int> a;
for(int i = 0; i < 10; i++) a.push_back(i);
	
for(int i = 0; i < 10; i++) cout<<a[i]<<" ";
cout<<endl;
	
for(vector<int>::iterator i = a.begin(); i != a.end(); i++) cout<<*i<<" ";
cout<<endl;	
		
for(auto x : a) cout<<x<<" ";
cout<<endl;

vector支持比较运算

1 2	vector<int> a(4, 3), b(3, 4); if(a < b) puts("a < b");//成立，vector按照字典序进行比较

pair

pair<int, string> p;

pair前后两个元素的数据类型可以不一样

p.first()；表示第一个元素

p.second()；表示第二个元素

pair 初始化

pair<int, string> p;

p = make_pair(3, "value");
p = {3, "value"};

//pair可以嵌套，可以存储三个元素
pair<int, pair<int, int>> p;

pair支持比较运算

1	以first为第一关键字，以second为第二关键字（字典序）

string

string常用函数

string常用函数	含义
s.size()/s.length()	返回长度
s.empty()	返回是否为空
s.clear()	清空
s.substr(a, b)	返回字符串从a开始b长度的子串,b是截取长度
s.substr(a)	返回字符串从a开始到最后的子串
s.c_str()	返回字符串首字符的地址，一般来说printf不可以输出string，但用此函数就可以

1 2	string s("hello world"); printf("%s\n", s.c_str());

queue

queue常用函数

queue常用函数	含义
q.size()	返回长度
q.empty()	返回是否为空
q.push()	向队尾插入一个函数
q.front()	返回队头元素
q.back()	返回队尾元素
q.pop()	弹出队头元素

queue没有clear函数，清空操作

1 2	queue<int> q; q = queue<int>();

priority_queue

优先队列，优先队列中优先级高的元素先出队列，默认是大根堆

如何使用优先队列实现小根堆

priority_queue<int> heap;//默认是大根堆

//法一：直接定义小根堆
priority_queue<int, vector<int>, greater<int>> heap;

//法一：插入负数
heap.push(-x);

优先队列常用函数

常用函数	含义
没有clear函数
q.push()	插入一个元素
q.top()	返回堆顶元素
q.pop()	弹出堆顶元素

stack

stack常用函数

常用函数	含义
没有clear函数
empty()	返回是否为空
size()	返回长度
push()	向栈顶插入一个元素
top()	返回栈顶元素
pop()	弹出栈顶元素

deque

双端队列

优点：功能全面

缺点：慢

deque常用函数

常用函数	含义
size()	返回长度
empty()	返回是否为空
clear()	清空
front()/back()	返回第一个/最后一个元素
push_back()/pop_back()	向队尾插入/弹出一个元素
push_front()/pop_front()	向队首插入/弹出一个元素
begin()/end()	支持begin/end迭代器
[ ]	支持随机选取

set, map, multiset, multimap

详情

基于平衡二叉树（红黑树），动态维护有序序列

set, multiset

详情

set中不能有重复元素

multiset中可以有重复元素

set/multiset支持函数	含义
size()	返回长度
empty()	返回是否为空
clear()	清空
begin()/end()	支持迭代器
insert()	插入一个数
find()	查找一个数，如果不存在返回end迭代器
count()	返回某一个数的个数
erase()	如果输入是一个数x，删除所有x 如果输入一个迭代器，删除这个迭代器
lower_bound(x) upper_bound(x)	返回大于等于x的最小的数的迭代器返回大于x的最小的数的迭代器

set最核心的两个操作就是lower_bound()和upper_bound()

map, multimap

详情

map/multimap支持函数	含义
size()	返回长度
empty()	返回是否为空
clear()	清空
begin()/end()	支持迭代器
insert()	输入的参数是一个pair
erase()	输入的参数pair或迭代器
find()	查找一个数，如果不存在返回end迭代器
lower_bound(x) upper_bound(x)	返回大于等于x的最小的数的迭代器返回大于x的最小的数的迭代器
[ ]	支持随机选取，这是map最核心的操作

可以像使用数组一样使用map

但要注意时间复杂度是o(logn)

1
2
3

map<string, int> a;

a["syc"] = 1;

unordered_set, unordered_map, unordered_multiset, unordered_multimap

详情

操作和上面类似，一一对应

优点：增删改查的时间复杂度是o(1);

缺点：不支持lower_bound()/upper_bound()，也不支持迭代器++，—，和排序有关的操作都不支持

因为是unordered，无序的

bitset

压位

c++中的bool型数占用一个字节的空间，而用bitset可以将其放到一个位的空间，

也就是说，可以节省8倍空间

bitset的定义

1	bitset<10000> s;//<>中写的是个数而不是类型

bitset支持的操作

bitset支持的操作	含义
```~, &, \	, ^```	取反，与，或，异或
>>, <<	移位
== , !=
[ ]
count()	返回有多少个1
any() none()	判断是否至少有一个1 判断是否全为0
set() set(k, v)	把所有位置成1 将第k位置成v
reset()	把所有位变成0
flip() flip(k)	等价于~ 把第k位取反