关于map与unordered_map的clear时间复杂度
  • 板块学术版
  • 楼主jiangwenyi2076
  • 当前回复34
  • 已保存回复37
  • 发布时间2023/10/26 15:57
  • 上次更新2023/11/2 11:20:59
查看原帖
关于map与unordered_map的clear时间复杂度
1105946
jiangwenyi2076楼主2023/10/26 15:57

rt 今天我在写一道题时,把unordered_map改成map就过了。发现似乎是clear的问题,然后本机用这段代码测试他们的效率:

#include <bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
int main()
{
	double s=clock();
	for(int i=1;i<=2e5;++i)
	{
		mp[i]=i;
	}
	for(int i=1;i<=2e5;++i)
	{
	    mp.clear();
	}
	double t=clock();
	printf("%.8lf",(t-s)/CLOCKS_PER_SEC);
	return 0;
}

这段代码在NOI LINUX下用时18.23115900秒

把unordered_map改成map只需要0.28151300秒

所以unordered_map clear的复杂度是O(size)吗?如果是,效率为什么会差那么多。如果不是,那么它的效率是多少?

2023/10/26 15:57
加载中...