对于C++STL及其时间复杂度的总结

由于本次在山东CCPC邀请赛中，对于堆的时间复杂度记忆不清晰，导致第4题没有做出来，与铜牌失之交臂，故觉应整理STL的时间复杂度。

本文仅整理有用（竞赛）的stl及其用法，并且不阐述过于基础的内容。

---

vector

头文件#include

vector开在局部或者全局都是开的堆空间，不会爆栈。
也就是说你能把vector开到1e18的长度都没事。

函数

1.vec.front();	//返回第一个元素,时间复杂度O(1)

2.vec.back();	//返回最后一个元素,时间复杂度O(1)

3.vec.pop_back();	//删除最后一个元素，O(1)

4.vec.push_back(x);	//在尾部加入一个元素x，O(1)

5.vec.size();	//返回vec的长度,O(1)

6.vec.begin();	//返回vec的起始位置

7.vec.end();	//返回vec的结束位置加一个位置

8.vec.empty();	//返回vec是否为空

9.vec.clear();	//清空vec，**O(N)**
如果要清空二维vec，就需要循环行数进行clear

10.vec.inesrt(pos,x);	//在下标pos出插入x元素，**O(N)**
其中pos必须以这样的格式：vec.begin() + n，即插入到n位值（下标从0开始）

11.vec.erase(start,end);	//删除[first,end)范围内的元素，**O(N)**

创建一维vector

1.普通的创建
vector<数据类型> vec;

2.指定长度和初始值的创建
vector<数据类型> vec(长度)	//长度被指定，默认值为0
vector<数据类型> vec(长度，默认值);		//长度与默认值被指定

3.创建默认有多个元素的vector
vector<数据类型> vec{值1，值2，值3};	//创建了长度为3，并填充了三个指定值的vector

4.复制创建
(1).
vector<int> a;
vector<int> b(a);	//创建出和a有相同数据类型，相同长度，相同初始值的vector，不实用
(2).
vector<数据类型> b = a;	//相当于把a数组赋给了b，数据类型要保证相同

创建二维vector

1.指定行数的二维vector
vector<数据类型> vec[N];		//行数不可扩展只能为N，列数可扩展，vec[1]就相当于一个普通一维vector

2.行列均可变化的二维vector
vector<vector<数据类型>>vec;	//行和列均可扩展，但是必须push_back进去一个完整的数组

3.指定行列和默认值
vector<vector<数据类型>> vec(行，vector<数据类型>(列，0));

---

stack（不如数组模拟）

头文件#include

创建

stack<数据类型>s;

函数

1.s.push(x);	//将x压入栈中，O(1)

2.s.pop();		//弹出栈顶,O(1)

3.s.top();		//返回栈顶元素,O(1)

4.s.empty();	//返回栈是否为空,O(1)

5.s.size();		//返回栈元素个数,O(1)

无法直接遍历栈，必须一个个弹出来遍历，当然不如直接用数组模拟能够直接遍历。

---

queue

头文件#include

创建

queue<数据类型>q

函数

均为O(1)时间复杂度

1.q.front();	//返回队首元素

2.q.back();

3.q.push(x);

4.q.pop();

5.q.size();

6.q.empty();

---

deque

头文件#include

创建

deque<数据类型>q;

函数

1.q.push_back(x)/q.push_front(x)	//压入首/尾，O(1)

2.q.back()/q.front()	//返回首/尾元素,O(1)

3.q.pop_back()/q.pop_front()	//O(1)

4.q.erase(pos)/q.erase(st,ed)		//删除pos处元素或删除[st,ed)的元素，**O(N)**

5.q.empty()	//O(1)

6.q.size()	//O(1)

7.q.clear()	//**O(N)**

8.q.insert(pos,x)	//**O(N)**

---

priority_queue

头文件#include

创建

priority_queue<int>heap 或 priority_queue< int,vector<int>,less<int> >heap;		//大根堆，top是最大
priority_queue< int,vector<int>,greater<int> >heap;								//小根堆，top是最小

创建对结构体的优先队列时，需要在结构体内定义好排序规则（重载运算符）

struct Node{
	int a,b;
	bool friend operator <const	(Node &A,Node &B){
		return A.a < B.a;
	}
};

函数

牢牢记住优先队列的两个logN，血的教训

1.q.top()		//返回堆顶元素,O(1)

2.q.push(x)		//压入x元素,**O(logN)**

3.q.pop()		//弹出x元素，**O(logN)**

4.q,size()		//返回堆中元素数量,O(1)

5.q.empty()		//O(1)

---

map/unordered_map

头文件#include及#include
map基于红黑树，unordered_map基于哈希表
map按照值排序，unordered_map不排序
map的指引可以分成两种，第一种是迭代器，就是下标，第二种是键。
基础用法不赘述

创建

map<数据类型（键），数据类型（值）>map

函数

1.m.find(x)	//返回值为key的键，如果没有就返回最后一个下标的下一个值,**O(logN)**

2.m.erase(pos)	//删除pos位置的键及其值，O(1)

3.m.erase(key)	//删除key键及其值

4.m.size()		//返回已经存入了多少个键或值，O(1)

5.m.clear()		//清空，O(N)

6.m.insert({key,value})	//插入元素

7.m.rbegin()	//返回最后一个元素的迭代器

8.m.begin()		//返回第一个元素的迭代器

9.m.count(key)	//查询是否存在键key

10.m.lower_bound(x)	//返回键大于等于x的第一个键的迭代器,O(logN)

11.m.upper_bound(x)	//返回键大于x的第一个键的迭代器,O(logN)

对于map，修改和查询都相当于对红黑树进行修改，即时间复杂度都为O(logN)，而unordered_map的修改查询操作都接近O(1)

---

multimap

头文件#include
与map不同的地方在于multimap可以存储多个相同的键及其对应的值

创建

multimap<数据类型(key)，数据类型(值)>m

函数

1.m.count(key)	//返回键为key的键值对的个数

2.m.emplace()	//指定位置构建键值对，比insert效率高

大多数函数与map相同，值得注意的是，multimap不能通过直接给出键来查询值。

---

set/unordered_set

头文件#include以及#include
并且也有multiset

创建

set<数据类型>s

函数

1.s.begin()		//返回第一个元素的迭代器,O(1)

2.s.rbegin()	//返回最后一个元素迭代器,O(1)

3.s.clear()		//清空,O(N)

4.s.empty()		//O(1)

5.s.insert()	//O(logN)

6.s.size()		//O(1)

7.erase(key)	//删除键为key的值,O(logN)

8.s.find(x)		//查找x，并返回迭代器,O(logN)

9.s.count(x)	//查询x是否出现过,O(logN)

10.s.lower_bound(x)		//返回大于等于x的第一个元素的迭代器,O(logN)

11.s.upper_bound(x)		//返回大于x的第一个元素的迭代器,O(logN)

set可以改变排序方式

sets	//从小到大

set>s	//从大到小

---

string

头文件#include

特性

支持比较运算符，即可直接按照字典序比较两个字符串，并且更长的更大。

两个字符串可以直接用加法运算法加起来

读入

cin >> str遇到空格就停止
getline(cin,s)遇到换行符停止

函数

1.s.size()/s.length()	//返回长度

2.s.insert(pos,x)	//在pos位置插入字符串x

3.s.push_back(x)	//在结尾插入字符x，效率较高

4.s.erase(pos)		//删除pos处的字符

5.s.erase(st,ed)	//删除[st,ed)中的字符

6.s.clear()			//清空

7.s.replace(pos,len,str)	//从pos开始的长度为len替换为字符串str

8.s.replace(pos,len,cnt,c)	//从pos开始的长度为len替换为cnt个字符c

9.s.replace(it1,it2,str)	//把从[it1,it2)替换为str

10.tolower(s[i])		//字符s[i]变为小写

11.toupper(s[i])		//字符s[i]变为大写

12.s.substr(pos,len)	//截取从pos开始，长度为len的字符串

13.s.find(str,pos)		//从pos开始查找字符串str或字符

14.s.rfind(str,pos)		//从pos倒着找字符串str或字符

---

bitset

头文件#include
只能存0和1

创建

1.bitset<n>a	//创建n位，每一位都是0

2.bitset<n>a(s)	//用string类型创造bitset

特性

可以像二进制数一样进行位运算

函数

1.b.any()		//返回b中是否有1的数位

2.b.none()		//返回b中是否没有1的数位

3.b.count()		//返回b中1的个数

4.b.size()		//返回二进制位有多少

5.b[pos]		//直接查询pos数位是什么数

6.b.set()		//把b所有数位设为1

7.b.set(pos)	//把pos数位设为1

8.b.reset()		//b所有数位设为0

9.b.reset(pos)	//bpos数位设为0

10.b.flip()		//b的所有二进制数位取反

11.b.flip(pos)

12.b.to_ulong()	//用b返回一个unsigned long值

---

array

头文件#include
大小固定，更像普通数组，比vector快

创建

1.array<数据类型，len>a;	//开一个len长度的，但是默认值不确定

2.array<数据类型，len>a{};	//开一个len长度的，默认值为0

函数

1.a.begin()		//返回第一个元素的迭代器

2.a.end()		//返回最后一个元素后一个位置的迭代器

3.a.rbegin()	//返回最后一个元素的迭代器

4.a.size()		//返回a的长度

5.a.at(n)		//返回a[n]

6.a.front()		//返回第一个元素

7.a.back()		//返回最后一个元素

8.a.data()		//返回一个指向a的第一个元素的指针

9.a.fill(x)		//用x给a初始化

10.a1.swap(a2)	//交换相同长度的a1和a2的所有元素

11.fill(st,ed,x)//初始化[st,ed)为x

12.get<n>(a)	//相当于a[1]，并且n只能为具体数字

---

STL函数

这里有众多神器啊

__builtin_ffs(x)

返回x的二进制数位中从后往前找的第一个1所在的位置。

__builtin_popcount(x)

返回x的二进制形式中1的个数

__builtin_ctz

返回x的二进制形式中末尾0的个数（从后往前第一个1之后的）

以上函数都可以在结尾出加上ll来转化为对long long的函数

accumulate(a + st,a + ed,original) O(N)

对取件[st,ed]以original为初始值来求和
并且可以定义函数来定义对结构体的求和方式

atoi(char*) / stoi(string)

把字符串转化为int

fill(a + st,a + ed,value) O(N)

对数组把[st,ed]范围内转化为value值

is_sorted(a + st,a + ed) O(N)

判断数组在[st,ed]范围内是否排序好了

lower_bound(a+st,a+ed,target) / upper_bound(a+st,a+ed,target) O(logN)

在范围内lower_bound查找第一个大于等于target的值，upper_bound查找第一个大于target的值

max_element(a+st,a+ed) / min_element(a+st,a+ed)O(N)

返回数组在范围内的最大值和最小值

nth_element(a+st,a+nth,a+ed)O(N)

返回数组在范围内第nth小的值

next_permutation(a + st,a + ed)O(N)

求下一个字典序大一的排列，并且有返回值，如果是最大的排列就返回false

```prev_permutation(a + st,a + ed)````O(N)

求下一个字典序小一的排列，并且有返回值，如果是最小的排列就返回false

stable_sort()O(NlogN)

与sort一样，只不过不会改变大小相同的元素的位置

to_string

将整数或小数转化为字符串

unique()O(N)

去重

__lg(x)O(1)

求 $lo{g}_{2}x$ 下取整