常用 STL 整合

一、vector

vector 是 STL 提供的一种 内存连续，长度可变 的动态数组。

虽说动态数组，但 vector 的底层仍是定长数组。当数组大小不足时，vector 会倍增的申请、分配更多连续的空间。

定义

vector<int>h; 定义一个数据类型为 int 的 vector h。

需要头文件 #include<vector>。

函数

1. 元素访问

   • h.begin() 返回一个迭代器，指向 h 的第一个元素的位置。
   • h.end() 返回一个迭代器，指向 h 的最后一个元素的后一个位置。
   • h.front() 返回 h 中的第一个数。
   • h.back() 返回 h 中的最后一个数。
   • h[x] 返回 h 下标为 x 的元素。

2. 元素修改

   • h.clear() 清空 h。
   • h.push_back(int val) 在 h 的末尾加入元素 val，均摊时间复杂度 \(O(1)\)，最坏复杂度为 \(O(n)\)（倍增申请空间）。
   • h.pop_back() 删除 h 的最后一个元素，时间复杂度 \(O(1)\)。
   • h.insert(iterator poi,int val) 在 poi 位置之前插入一个元素 val，时间复杂度与插入位置到 h.end() 的距离有关。
   • h.erase(iterator poi) 删除 poi 位置的元素，并返回指向下一个迭代器，时间复杂度同 insert 操作。
   • h.erase(iterator sta，iterator end) 删除位于 [sta,end) 之间的元素，并返回指向下一个迭代器，时间复杂度同 insert 操作。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

应用

• 邻接表存图

1. 定义

struct edge{
	int to,val;
};
vector<edge>e[inf];

2. 存图（有向图）

for(int i=1;i<=m;i++)
{
	int u=re(),v=re(),w=re();
	e[u].push_back((edge){v,w});
}

3. 对边进行排序

for(int i=1;i<=n;i++)
	sort(h[i].begin(),h[i].end(),cmp);

4. 遍历

void dfs(int now)
{
	for(int i=0;i<(h[now].size());i++)
	{
		...
		dfs(h[now][i]);
		...
	}
}

• 桶优化 dijkstra

有兴趣者可以看 这个，此处不再赘述。

memset(dis,127,sizeof(dis));
int now=s;dis[now]=0;
while(1)
{
	vis[now]=1;
	for(int i=fir[now];i;i=nex[i])
	{
		int p=poi[i];
		if(dis[p]>dis[now]+val[i])
		{
			dis[p]=dis[now]+val[i];
			T[dis[p]].push_back(p);
			maxn=max(maxn,dis[p]);
		}
	}
	last=now;
	for(int i=1;i<=maxn;i++)
	{
		if(T[i].size())
		{
			if(vis[T[i][0]]==0)now=T[i][0];
			last=i;T[i].erase(T[i].begin());
			break;
		}
	}
	if(last==now)break;
}

• 模拟平衡树

cin>>op>>k;
if(op==4)cout<<h[k-1]<<endl;
if(op==2)h.erase(lower_bound(h.begin(),h.end(),k));
if(op==1)h.insert(upper_bound(h.begin(),h.end(),k),k);
if(op==6)cout(*upper_bound(h.begin(),h.end(),k))<<endl;
if(op==3)wr(lower_bound(h.begin(),h.end(),k)-h.begin()+1);
if(op==5)cout<<(*--lower_bound(h.begin(),h.end(),k))<<endl;

不要在意 1,2,3,4 的顺序，个人感觉这样逐行递增比较好看

二、stack

stack 是 STL 提供的一种栈。

定义

stack<int>h; 定义一个数据类型为 int 的 stack h。

需要头文件 #include<stack>。

函数

1. 元素访问

   • h.top() 返回 h 的栈顶元素。

2. 元素修改

   • h.push(int val) 在 h 的栈顶加入元素 val。
   • h.pop() 弹出 h 的栈顶元素。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

和 vector 基本一致，只是少了很多。

应用

• 后缀表达式

#include<bits/stdc++.h>
int sum[57],top,ans;
char s[57];
int main()
{
	std::cin>>s;
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		if(s[i]=='.')continue;
		if(s[i]>'9'||s[i]<'0')
		{
			if(s[i]=='+')ans=sum[top-1]+sum[top];
			if(s[i]=='-')ans=sum[top-1]-sum[top];
			if(s[i]=='*')ans=sum[top-1]*sum[top];
			if(s[i]=='/')ans=sum[top-1]/sum[top];
			sum[--top]=ans;
		}
		else
		{
			sum[++top]=0;
			while(s[i]!='.')
				sum[top]=sum[top]*10+s[i]-48,i++;
		}
	}
	std::cout<<ans;
	return 0;
}

三、queue

queue 是 STL 提供的一种队列。

定义

queue<int>h; 定义一个数据类型为 int 的 queue h。

需要头文件 #include<queue>。

函数

1. 元素访问

   • h.front() 返回 h 的队首元素。
   • h.back() 返回 h 的队尾元素。

2. 元素修改

   • h.push(int val) 在 h 的队尾加入元素 val。
   • h.pop() 弹出 h 的队首元素。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

和 stack 基本一致，只是多了一些。

特殊队列：双端队列 deque

deque<int>h; 定义一个数据类型为 int 的 deque h。

需要头文件 #include<deque>。

1. 元素访问

   • h.front() 返回 h 的队首元素。
   • h.back() 返回 h 的队尾元素。
   • h[x] 返回 h 下标为 x 的元素。

2. 元素修改

   • h.push_front(int val) 在 h 的队尾加入元素 val。
   • h.push_back(int val) 在 h 的队首加入元素 val。
   • h.pop_front() 弹出 h 的队首元素。
   • h.pop_back() 弹出 h 的队尾元素。
   • h.insert(iterator poi,int val) 在 poi 位置之前插入一个元素 val。
   • h.erase(iterator poi) 删除 poi 位置的元素，并返回指向下一个迭代器。
   • h.erase(iterator sta，iterator end) 删除位于 [sta,end) 之间的元素，并返回指向下一个迭代器。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

好像和 vector 差不多，而且好像比 vector 更高级。

但不用一次你绝对不知道 deque 的空间复杂度多大（血的教训）

特殊队列：优先队列 priority_queue

priority_queue 是 STL 提供的一种二叉堆，默认大根堆。

priority_queue<int>h; 定义一个数据类型为 int 的 priority_queue h。

需要头文件 #include<queue>。

1. 元素访问

   • h.top() 返回 h 中的最大值。

2. 元素修改

   • h.push(int val) 在 h 中的加入元素 val，时间复杂度 \(O(\log n)\)。
   • h.pop() 弹出 h 中的最大值，时间复杂度 \(O(\log n)\)。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

应用

• BFS/SPFA

BFS

h.push((node){x,y});
vis[x][y]=1;
while(h.size())
{
	node now=h.front();h.pop();
	for(int i=0;i<8;i++)
	{
		int xx=now.x+dx[i],yy=now.y+dy[i];
		if(xx>0&&yy>0&&xx<=n&&yy<=m&&vis[xx][yy]==0)
		{
			h.push((node){xx,yy});
			ans[xx][yy]=ans[now.x][now.y]+1;
			vis[xx][yy]=1;
		}
	}
}

SPFA

memset(dis,127,sizeof(dis));
dis[s]=0;vis[s]=1;
h.push(s);
while(h.size())
{
	int now=h.front();h.pop();
	vis[now]=0;
	for(int i=fir[now];i;i=nex[i])
	{
		int p=poi[i];
		if(dis[p]>dis[now]+val[i])
		{
			dis[p]=dis[now]+val[i];
			if(vis[p])continue;
			vis[p]=1;h.push(p);
		}
	}
}

• 堆优 dijkstra

模板

memset(dis,127,sizeof(dis));
h.push(node(s,0));
dis[s]=0;
while(h.size())
{
	int now=h.top().to;h.pop();
	if(vis[now])continue;
	vis[now]=1;
	int len=e[now].size();
	for(int i=0;i<len;i++)
	{
		int p=e[now][i].to;
		if(dis[p]>dis[now]+e[now][i].val)
		{
			dis[p]=dis[now]+e[now][i].val;
			h.push(node(p,dis[p]));
		}
	}
}

不会 SPFA 和堆优 dij 的可以查看 此博客。

四、set

set 是 STL 提供的集合，能实现平衡树的部分操作，其内部是一颗红黑树（一种很高效的平衡树）。

set 不支持重复元素，若需要用到多个相同元素，可使用 multiset。

定义

set<int>T; 定义一个数据类型为 int 的 set T。

需要头文件 `#include。

函数

1. 元素访问

   • h.begin() 返回一个迭代器，指向 h 的第一个元素的位置。
   • h.end() 返回一个迭代器，指向 h 的最后一个元素的后一个位置。
   • h.front() 返回 h 中的第一个数。
   • h.back() 返回 h 中的最后一个数。
   • h[x] 返回 h 下标为 x 的元素。

2. 元素修改

   • h.clear() 清空 h。
   • h.push_back(int val) 在 h 的末尾加入元素 val，均摊时间复杂度 \(O(1)\)，最坏复杂度为 \(O(n)\)（倍增申请空间）。
   • h.pop_back() 删除 h 的最后一个元素，时间复杂度 \(O(1)\)。
   • h.insert(iterator poi,int val) 在 poi 位置之前插入一个元素 val，时间复杂度与插入位置到 h.end() 的距离有关。
   • h.erase(iterator poi) 删除 poi 位置的元素，并返回指向下一个迭代器，时间复杂度同 insert 操作。
   • h.erase(iterator sta，iterator end) 删除位于 [sta,end) 之间的元素，并返回指向下一个迭代器，时间复杂度同 insert 操作。

3. 元素个数

   • h.size() 返回 h 中的元素个数。
   • h.empty() 检查 h 是否为空，为空返回 1，非空返回 0。

应用

五、map