I've heard more about how vector<bool>
is slow, and we need to dodge him or use vector<char>
.
But today I ran some tests in "Codeforces custom test" with GNU G++.
First simple erato sieve
//N = 3e7
for(int i=2;i<N;++i) if(!u[i]) for(int j=i*2;j<N;j+=i) u[j] = 1;
int cnt = 0;
for(int i=0;i<N;++i) if(u[i]) ++cnt;
cout<<cnt<<endl;
Depends on u
:
bool u[N] : 420 ms, 31204 KB
vector<bool> u(N): 218 ms, 5484 KB
vector<char> u(N): 451 ms, 31164 KB
You can say like "memory constant speed up this code"
Second.
//N = 1e4
double total = 0;
for(int it=0;it<N;++it){
for(int i=0;i<N;++i){
int x = rand()%N;
u[x] = 1;
}
for(int i=0;i<N;++i){
int x = rand()%N;
u[x] = 0;
}
for(int i=0;i<N;++i){
total+=u[i];
u[i] = 0;
}
}
cout<<total/N<<endl;
bool u[N] : 2683 ms, 1860 KB
vector<bool> u(N): 2667 ms, 1832 KB
vector<char> u(N): 2620 ms, 1868 KB
We see its equal!
So maybe its not so bad? Or you have examples where vector<bool>
is really slower than alternatives?