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?