Why vector<bool> so slow? Isn't it optimized?

• Following is one 12ms answer @aileenbai, original post: 12ms-c-solution

``````class Solution {
public:
int countPrimes(int n) {
if(--n < 2) return 0;
int m = (n + 1)/2, count = m, k, u = (sqrt(n) - 1)/2;
bool notPrime[m] = {0};   // <---------   this line

for(int i = 1; i <= u;i++) {
if(!notPrime[i]) {
for(k = (i+ 1)*2*i; k < m;k += i*2 + 1)
if (!notPrime[k]) {
notPrime[k] = true;
count--;
}
}
}
return count;
}
};
``````

If you change "this line" from `bool notPrime[m] = {0}` to `vector<bool> notPrime(m, 0)`, running time increases from 12ms to 100+ms.....

• Read this, `vector<bool>` is a specialized version of vector, which is used for elements of type bool and optimizes for space. In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types. You should use `vector<char> notPrime(m, 0);`, instead of `vector<bool> notPrime(m, 0);` to fix the performance issue.

• Thanks for the link. I think the essence of the problem is that `vector<bool>` "favors memory optimization over processing".

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.