1

I've just started learning C++ using Programming: Principles and Practice using C++. That book tells me to use a header file which sets things up for me. The header file in question is available at http://www.stroustrup.com/Programming/std_lib_facilities.h

I'm attempting an exercise which asks me to write a prime sieve. I have the following program:

#include "std_lib_facilities.h"

void sieve_erat(int end) {
  vector<bool> primes (end, true);
  int final_element = sqrt(end) + 1;
  for (int i=2; i<final_element; ++i)
    if (primes[i])
      for (int j=i*i; j<end; j += i)
    primes[j] = false;

  for (int p=2; p<end; ++p)
    if (primes[p])
      cout << p << " ";
  cout << '\n';
}

int main() {
  cout << "Enter the number to which I should find the primes: ";
  cin >> max;
  sieve_erat(max);
  return 0;
}

But when I compile on my computer with g++ primes.cpp I get the following output:

~/src/c++ $ g++ primes.cpp 
In file included from /usr/include/c++/4.8.1/ext/hash_map:60:0,
                 from std_lib_facilities.h:34,
                 from primes.cpp:4:
/usr/include/c++/4.8.1/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
 #warning \
  ^
In file included from primes.cpp:4:0:
std_lib_facilities.h: In instantiation of ‘T& Vector<T>::operator[](unsigned int) [with T = bool]’:
primes.cpp:36:17:   required from here
std_lib_facilities.h:88:38: error: invalid initialization of non-const reference of type ‘bool&’ from an rvalue of type ‘std::vector<bool, std::allocator<bool> >::reference {aka std::_Bit_reference}’
   return std::vector<T>::operator[](i);
                                  ^

I've tried my best to find the answer to this question on the web, but I just can't understand what the message is telling me I've done wrong! Please may somebody be kind enough to point me in the right direction?

Thank you.

Charles
  • 953
  • 1
  • 8
  • 19
  • 2
    try replacing the bool vector with an int vector? – tohava Jul 29 '13 at 17:35
  • Thanks for the comment. That does work, but I find the code less readable. Is there a fundamental reason why I shouldn't use the bool type here? – Charles Jul 29 '13 at 17:37
  • Somebody tell mr. Stroustrup that his header sucks. :) – jrok Jul 29 '13 at 17:40
  • @jrok, it serves a very specific purpose of teaching C++ to programming novices, so they don't need to know about namespaces or how Microsoft define `min` and `max` as macros or other cruft that gets in the way for beginners. – Jonathan Wakely Jul 29 '13 at 17:50
  • see this related question: http://stackoverflow.com/questions/670308/alternative-to-vectorbool – yasouser Jul 29 '13 at 17:51
  • @JamesWakely I read this book, too. The header is still a bit meh. Note how OP is saying `cin >> max;` without declaring `max` anywhere. They'll gonna get a weird error about `std::max` along with 100 possible candidates for `operator>>`. I understand the need for such header but `using namespace std;` is as bad here as anywhere else, IMO. – jrok Jul 29 '13 at 17:55
  • @jrok, I noted the `max` issue in my answer - don't blame Stroustrup for that, that won't compile with or without Stroustrup's header so I suspect the OP didn't post the right code to produce the error shown. – Jonathan Wakely Jul 29 '13 at 17:57
  • @JonathanWakely Yeah, well, don't get me wrong, I think it's a great book. I'd just aproach this header differently :) – jrok Jul 29 '13 at 18:01

2 Answers2

3

(Are you sure that's the code you're compiling? where is max declared?)

std::vector<bool> is a very strange beast which doesn't behave like std::vector<T> for any other T.

Unfortunately even though std::vector<bool> seems like the obvious choice in your case, it forces you to deal with the oddness of std::vector<bool> and it doesn't work with Stroustrup's Vector class template.

The detailed explanation of the error is that Stroustrup's header re-defines vector to refer to his Vector template, which adds some range-checking to the element access operator (i.e. operator[], which is the one used when you say primes[i]). The redefined vector cannot be instantiated with bool because std::vector<bool>::operator[] does not return a normal reference, and the redefined vector expects it to do so.

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
  • Thank you for expanding on my question Jonathan. I copied the code I pasted right out of my editor, so I assume the answer to your question is yes, that is the code I'm compiling -- not sure if I've misunderstood something. I'll chalk this one up for further study once I learn more C++ as I still don't fully understand what has happened. I'm content to consider vector to be something I should avoid for now :-) Thanks again. – Charles Jul 29 '13 at 18:33
  • (sorry, I just realised what you were referring to, I mispasted my code, forgot the `int max;` line. Arrggh) – Charles Jul 29 '13 at 18:39
2

From a first look, the vector of bool seems to be the problem. Unfortunately, vectors and bool values do not go well together, as iterators are unable to return a bool& reference. See this question for a fairly detailed explanation.

Community
  • 1
  • 1
DUman
  • 2,560
  • 13
  • 16