[ericr2427]

I created a program and was using vector<int> but I was running into problems using values > 100,000,000 because of memory limitations, so I created a similar program that used vector<bool>. However, on a run that takes 23 seconds, the program using bool runs about 6 seconds slower than the one using int.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main (int argc, char *argv[]) {
  int size, i, j;
  size = 100000000;
  vector<bool> primes(size, 1);
  for (i = 2; i <= sqrt(size); i++) {
	if (primes[i]) {
	  for (j = 2; j*i <= size; j++) {
		primes[i*j] = 0; // This line causes the time difference
	  }
	}
  }
}

I'm wondering if anyone has any ideas for making that line run faster. Alternatively, I saw an article warning against the use of vector<bool> and instead using dynamic_bitset or something similar, but I couldn't find any good tutorials on that. Suggestions for using either method more efficiently would be appreciated.

[perfectly.insane]

vector<bool> may be a specialized template instantiation. A bool on my compiler consumes 1 byte, so if you want to use a vector, then maybe a vector<char> would work better.

There is also std::bitset, in which each bit really consumes only 1 bit, but again, it will be slower (perhaps vector<bool> in your library is similar to std::bitset?).