title: Performance gap between vector<bool> and array
body: <p>I was trying to solve <a href="https://leetcode.com/problems/count-primes/" rel="noreferrer">a coding problem in C++</a> which counts the number of prime numbers less than a non-negative number <code>n</code>.</p>
  
  <p>So I first came up with some code:</p>
  
  <pre><code>int countPrimes(int n) {
      vector&lt;bool&gt; flag(n+1,1);
      for(int i =2;i&lt;n;i++)
      {
          if(flag[i]==1)
              for(long j=i;i*j&lt;n;j++)
                  flag[i*j]=0;
      }
      int result=0;
      for(int i =2;i&lt;n;i++)
          result+=flag[i];
      return result;
  }
  </code></pre>
  
  <p>which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:</p>
  
  <pre><code>int countPrimes(int n) {
      // vector&lt;bool&gt; flag(n+1,1);
      bool flag[n+1] ;
      fill(flag,flag+n+1,true);
      for(int i =2;i&lt;n;i++)
      {
          if(flag[i]==1)
              for(long j=i;i*j&lt;n;j++)
                  flag[i*j]=0;
      }
      int result=0;
      for(int i =2;i&lt;n;i++)
          result+=flag[i];
      return result;
  }
  </code></pre>
  
  <p>which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like <a href="https://stackoverflow.com/questions/381621/using-arrays-or-stdvectors-in-c-whats-the-performance-gap">this one</a> and <a href="https://stackoverflow.com/questions/3664272/is-stdvector-so-much-slower-than-plain-arrays">that one</a> but I am still confused.</p>
  
  <p>EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing <code>vector&lt;bool&gt;</code> with <code>vector&lt;char&gt;</code>.</p>