此文章比较了一些常用数据结构和算法的C++实现和Rust实现的速度。
此处的C++，指g++ 10.0.1和clang++ 10.0.0；Rust指rustc 1.43.0。C++的编译参数是-Ofast -march=native -std=c++20；Rust的编译参数是-C opt-level=3 -C target-cpu=native。速度，指user time。
为了排除读入速度的差异，使用了相同的快读实现（在Rust中我实在是找不到一种原生的快读方法，只好extern "C"了）。C++使用printf输出，Rust使用std::io::BufWriter输出；两者的速度经我测试没有肉眼可见的差别。
int read(){
int r=0,c;
do c=getchar();while(!isdigit(c));
do r=r*10+c-48,c=getchar();while(isdigit(c));
return r;
}
extern "C"{fn getchar()->i32;}
fn read()->i32{
let mut r=0;let mut c;
loop{
unsafe{c=getchar();}
if c>=48 && c<48+10{break;}
}
loop{
r=r*10+c-48;unsafe{c=getchar();}
if c<48 || c>=48+10{break;}
}
r
}
let out=&mut BufWriter::new(stdout());
std::sort VS Vec::<T>::sort_unstable
对于长度为$2^{24}$的随机数列进行排序，然后输出。数列中元素范围是$[1,10^9]$。两个排序均为不稳定的，底层实现均为快速排序的某个变种。
const int N=1<<24;
vector<int> a(N);
ranges::generate(a,read);
ranges::sort(a);
for(int i:a)printf("%d\n",i);
const N:usize=1<<24;
let mut v=vec![];
v.resize_with(N,read);
v.sort_unstable();
for i in v{writeln!(out,"{}",i).ok();}
g++运行时间：2.432s；clang++运行时间：2.399s；rust运行时间：1.676s。每个语言都有0.725s时间花在输出上，0.286s时间花在读入上，可见Rust的sort效率是C++的2倍以上。由于测输入输出时间太烦了，以后的输入和输出的时间我都认为与输入/输出的数个数成正比，不再继续测量了。
std::vector VS Vec
输入一个$2^{24}$个点的随机树，输出邻接表。
const int N=1<<24;
vector<vector<int>> v(N);
for(int _=1;_<N;_++){
int x=read(),y=read();
v[x].push_back(y);v[y].push_back(x);
}
for(int i=0;i<N;i++){
for(int j:v[i])printf("%d ",j);
puts("");
}
const N:usize=1<<24;
let mut v=vec![vec![];N];
for _ in 1..N{
let (x,y)=(read()as usize,read()as usize);
v[x].push(y);v[y].push(x);
}
for i in 0..N{
for &j in &v[i]{write!(out,"{} ",j).ok();}
writeln!(out,"").ok();
}
C++实现为啥不用std::array或者原生数组？因为栈里开不下。为什么不用static？因为开static vector<int> v[N];的一瞬间，我电脑死机了。Rust实现不用原生数组也是一样的道理。
g++用时10.601s；clang++用时10.372s；rust用时10.508s。可见在这方面还是半斤八两的；无论什么语言都别想开超过一百万个vector，否则神仙也难救。
std::unordered_map VS std::collections::HashMap
进行$2^{24}$次操作，每次操作有$\dfrac{1}{2}$的概率插入（随机的）键值对，如果键已存在就更新值；另外$\dfrac{1}{2}$的概率询问一个键对应的值（键有$\dfrac{1}{3}$左右的概率不存在）。键和值的范围均是$[1,10^9]$。底层实现均为哈希表，并且Rust的实现不可能被卡（哈希函数是随机选择的）。
const int N=1<<24,QRY=2;
unordered_map<int,int> mp(N);
for(int _=N;_--;){
int op=read(),key=read();
if(op==QRY)
printf("%d\n",mp.contains(key)?mp[key]:-1);
else mp[key]=read();
}
const N:usize=1<<24;
const QRY:i32=2;
let mut mp=HashMap::<i32,i32>::with_capacity(N);
for _ in 0..N{
let (op,key)=(read(),read());
if op==QRY{
writeln!(out,"{}",if mp.contains_key(&key){mp[&key]}else{-1}).ok();
}else{mp.insert(key,read());}
}
值得一提的是怎么gen数据，即怎么从一个很大的集合中随机选出一个元素。我使用了pbds，*t.find_by_order(rand()%t.size())。不知道有没有什么更简单的方法。
g++用时3.932s；clang++用时3.766s；rust用时3.181s。可见Rust的哈希表效率是C++的1.3倍左右。
std::set VS std::collections::BTreeSet
进行$2^{24}$次操作，每次操作有$\dfrac{1}{2}$的概率插入一个（随机的）元素（可能已经存在）；另外$\dfrac{1}{2}$的概率询问集合中$\ge x$的最小值（即lower_bound），可能不存在。元素范围是$[1,10^9]$。底层实现是不同的，C++实现是红黑树，Rust实现是B Tree。
const int N=1<<24,QRY=2;
set<int> st;
for(int _=N;_--;){
int op=read(),key=read();
if(op==QRY){
auto it=st.lower_bound(key);
printf("%d\n",it==st.end()?-1:*it);
}else st.insert(key);
}
const N:usize=1<<24;
const QRY:i32=2;
let mut st=BTreeSet::<i32>::new();
for _ in 0..N{
let (op,key)=(read(),read());
if op==QRY{
let mut r=st.range((Included(key),Unbounded));
writeln!(out,"{}",r.next().unwrap_or(&-1)).ok();
}else{st.insert(key);}
}
可怕！g++用时14.850s，clang++用时15.131s，rust用时5.622s。红黑树被打爆了。Rust的set效率是C++的set的三倍以上。
std::priority_queue VS std::collections::BinaryHeap
进行$2^{24}$次操作，$\dfrac{2}{3}$概率插入一个随机数，$\dfrac{1}{3}$概率弹出堆顶并输出弹出的元素（保证堆非空）。元素范围是$[1,10^9]$。底层实现均为二叉堆，并且Rust的堆是可以遍历的。
const int N=1<<24,QRY=2;
priority_queue<int> pq;
for(int _=N;_--;){
int op=read();
if(op==QRY){
int x=pq.top();pq.pop();
printf("%d\n",x);
}else pq.push(read());
}
const N:usize=1<<24;
const QRY:i32=2;
let mut pq=BinaryHeap::<i32>::with_capacity(N);
for _ in 0..N{
let op=read();
if op==QRY{
writeln!(out,"{}",pq.pop().unwrap()).ok();
}else{pq.push(read());}
}
这里C++的代码没有先reserve，因为priority_queue的reserve比较麻烦（因为c是保护成员变量，要先继承），并且没有变快。
g++用时1.170s，clang++用时1.132s，rust用时0.979s。虽然表面上差距不大，不要忘了IO所用时间是很多的。减去IO时间可以估算出Rust的堆效率是C++的1.6倍左右。
std::deque VS std::collections::VecDeque
进行$2^{24}$次操作，每次操作可能是：在头部或尾部插入随机数，各有$\dfrac{1}{5}$概率；弹出头部或尾部元素（保证非空），各有$\dfrac{1}{5}$概率；输出某一特定下标上的元素（保证非空），也有$\dfrac{1}{5}$的概率。元素范围是$[1,10^9]$。我太菜了，不清楚底层实现。
const int N=1<<24;
deque<int> v;
for(int _=N;_--;){
int op=read();
switch(op){
case 0:{v.push_front(read());break;}
case 1:{v.push_back(read());break;}
case 2:{printf("%d\n",v.front());v.pop_front();break;}
case 3:{printf("%d\n",v.back());v.pop_back();break;}
case 4:printf("%d\n",v[read()]);
}
}
const N:usize=1<<24;
let mut v=VecDeque::<i32>::with_capacity(N);
for _ in 0..N{
let op=read();
match op{
0=>v.push_front(read()),
1=>v.push_back(read()),
2=>{writeln!(out,"{}",v.pop_front().unwrap()).ok();},
3=>{writeln!(out,"{}",v.pop_back().unwrap()).ok();},
4=>{writeln!(out,"{}",v[read()as usize]).ok();},
_=>()
}
}
C++的deque貌似是没有reserve这种功能的。但是就算公平竞争，把Rust的with_capacity(N)改成new()，rust也只需0.804s。
g++用时0.936s，clang++用时0.939s，rust用时0.798s。减去IO时间，Rust的deque效率是C++的1.8倍到两倍左右。
