Java教程

常用 STL 整合

本文主要是介绍常用 STL 整合,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

常用 STL 整合

一、vector

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

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

定义

vector<int>h; 定义一个数据类型为 intvector 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];
  1. 存图(有向图)
for(int i=1;i<=m;i++)
{
	int u=re(),v=re(),w=re();
	e[u].push_back((edge){v,w});
}
  1. 对边进行排序
for(int i=1;i<=n;i++)
	sort(h[i].begin(),h[i].end(),cmp);
  1. 遍历
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; 定义一个数据类型为 intstack 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; 定义一个数据类型为 intqueue 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; 定义一个数据类型为 intdeque 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; 定义一个数据类型为 intpriority_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; 定义一个数据类型为 intset 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

这篇关于常用 STL 整合的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!