vector

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的三种方式

1
2
3
4
5
6
7
8
9
10
11
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

pair<int, string> p;

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

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

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

pair 初始化

1
2
3
4
5
6
7
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常用函数

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常用函数

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

queue,priority_queue和stack没有clear函数，其他stl容器都有

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

priority_queue

priority_queue

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

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

1
2
3
4
5
6
7
priority_queue<int> heap;//默认是大根堆

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

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

优先队列常用函数

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

stack

stack

stack常用函数

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

deque

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

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位取反

常用库函数

bitset

常用库函数都在algorithm里

reverse

翻转数组或vector数组

reverse(首元素位置，尾元素的下一个位置)

1
2
3
4
5
int a[] = {1, 2, 3, 4, 5};
reverse(a, a + 5);

vector<int> a({1, 2, 3, 4, 5});
reverse(a.begin(), a.end());

unique

去重

返回去重之后的尾迭代器，即去重后尾元素的下一个位置

将其余元素放到最后

1
2
3
4
int m = unique(a.begin(), a.end()) - a.begin();//求得数组中不同元素的数量

//同时通过erase函数，将最后多余的元素删去
a.erase(unique(a.begin(), a.end()), a.end());//最后a中剩下的就是不重复的元素

random_shuffle

把数组打乱

1
2
3
4
random_shuffle(a.begin(), a.end());
//如果想要每次运行时的随机数都不同
#include <ctime>
srand(time(0));

sort

给数组排序

1
2
3
4
5
6
7
sort(a.begin(), a.end());//默认从小到大排序
sort(a.begin(), a.end(), greater<int>());//从大到小排序
sort(a.begin(), a.end(), cmp);//自定义排序方式

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

给结构体排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//法一：写cmp函数
struct Rec{
		int x, y;
	}a[5];

bool cmp(Rec a, Rec b){
	return a.x > b.x;
}

sort(a, a + 5, cmp);

//法二：重载小于号
struct Rec{
	int x, y;
	bool operator< (const Rec &t) const{
		return x < t.x;
      //return x > t.x;当x大于t.x，排在前面
	}
}a[5];

lower_bound/upper_bound

1
2
3
vector<int> a{1, 2, 3, 4, 5};
int t = lower_bound(a.begin(), a.end(), 3) - a.begin();
cout << a[t] << endl;//3

next_permutation

next_permutation(begin(), end());

将传入排列转换成字典序加一的下一个排列，如果排不了了， 返回false