【swap】对象是STL容器时的时间复杂度


今天看启发式合并的时候发现一个题解里面直接对 set 进行 swap，就好奇其时间复杂度。测了一下，容器的 swap 应该是 O(1) 左右的。

vector 的 swap 时间近似 O(1)
set, map 的 swap 时间常数稍大，是 vector 的 2 倍左右
string 比 vector 要快得多
priority_queue 也可以 swap

set 的测试代码：
#include<bits/stdc++.h> using namespace std; #define rep(i, l, r) for(int i =
l; i <= (r); ++ i) const int N = 1e5 + 10, M = 1e7 + 10; inline bool check(int x
){ return __lg(x) % 3; } int is[M]; set<int> v1, v2, v3; void init() // 预处理随机数据
{ clock_t startTime,endTime; startTime = clock();//计时开始 srand(time(0)); rep(i, 1
, N) v1.insert(rand()); rep(i, 1, N) v2.insert(rand()); rep(i, 1, N) v3.insert(
rand()); rep(i, 1, M - 1) is[i] = check(rand()); // 这样是让数据更随机，防止编译器优化掉 endTime =
clock();//计时结束 cout << "The run time is: " <<(double)(endTime - startTime) /
CLOCKS_PER_SEC<< "s" << endl; } void swap_test() { clock_t startTime,endTime;
startTime= clock();//计时开始 int t; rep(i, 1, M - 1) // 对长度为 10^5 的容器随机交换 10^7 次 {
t= is[i]; if(t == 0) swap(v1, v2); if(t == 1) swap(v1, v3); if(t == 2) swap(v3,
v2); } endTime = clock();//计时结束 cout << "The run time is: " <<(double)(endTime -
startTime) / CLOCKS_PER_SEC << "s" << endl; } int main() { init(); swap_test();
return 0; }

技术
下载桌面版
GitHub
Microsoft Store
SourceForge
Gitee
百度网盘（提取码：draw）
云服务器优惠
华为云优惠券
京东云优惠券
腾讯云优惠券
阿里云优惠券
Vultr优惠券
站点信息
问题反馈
邮箱：[email protected]
吐槽一下
QQ群：766591547
关注微信
©2020-2025 ioDraw All rights reserved, Privacy Policy