【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; }

• « 上一篇：NodeJS编程实现：打开有密码的ZIP文件
• » 下一篇：嵌入式系统概述