1

I'm working through Bjarne Stroustrup's Programming: Principles and Practice Using C++ (2nd ed.) book and ran into a problem using his custom header file, std_lib_facilities.h when I try to use a vector<bool>.

I'm working on exercise 13 on p. 130, which is to allow the user to specify an upper bound, n, and then to find all of the primes between [2..n] using the Sieve of Eratosthenes. I figured I'd use a vector<bool> to store the marks on the numbers (whether or not they are composite). However, that is not working. Here is my code:

// exercise 13 on p. 130
// using Sieve of Eratosthenes to find prime numbers from 2..max

#include "../include/std_lib_facilities.h"

vector<int> sieve_of_Eratosthenes(int max)
{
        // initialize all values from 0..n to false
        vector<bool> is_composite; 
        for (int i = 0; i < max + 1; ++i)
                is_composite[i] = false;

        vector<int> primes;
        int sqrt_max = sqrt(max);

        for (int m = 2; m <= sqrt_max; ++m) {
                if (!is_composite[m]) {
                        primes.push_back(m);
                        for (int k = m * m; k <= max; k += m)
                                is_composite[k] = true;
                }
        }

        for (int m = sqrt_max; m <= max; ++m)
                if (!is_composite[m])
                        primes.push_back(m);

        return primes;
}

int main()
{
        int max = 100;

        cout << "Enter maximum value for Prime Finder: ";
        cin >> max;

        vector<int> primes = sieve_of_Eratosthenes(max);
        for (int p : primes)
                cout << p << '\n';
}

However, when I try to compile using g++ (g++ (SUSE Linux) 7.3.1 20180323 [gcc-7-branch revision 258812]), I get the following error(s):

> g++ exercise13.cpp -o bin/exercise13

In file included from exercise13.cpp:4:0:
../include/std_lib_facilities.h: In instantiation of ‘T& Vector<T>::operator[](unsigned int) [with T = bool]’:
exercise13.cpp:11:17:   required from here
../include/std_lib_facilities.h:88:36: error: cannot bind non-const lvalue reference of type ‘bool&’ to an rvalue of type ‘bool’
   return std::vector<T>::operator[](i);
          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/7/vector:65:0,
                 from ../include/std_lib_facilities.h:37,
                 from exercise13.cpp:4:
/usr/include/c++/7/bits/stl_bvector.h:80:5: note:   after user-defined conversion: std::_Bit_reference::operator bool() const
     operator bool() const _GLIBCXX_NOEXCEPT
     ^~~~~~~~

I'm not sure if the sieve is correct or not as I have not been able to compile it to test, but mainly I'm trying to just get past this error. Is there an alternate way I should be solving this because vector<bool> is not allowed, is this an issue with the header file, or did I do something else wrong?

Dan
  • 4,488
  • 5
  • 48
  • 75
  • 5
    std::vector is a rather odd duck. So odd that it [gets its own documentation page](https://en.cppreference.com/w/cpp/container/vector_bool). In my opinion you don't deserve downvotes for this. I'm going to see if I can come up with a decent formal answer for this. – user4581301 Jul 12 '18 at 02:31
  • Try `std::deque`. Also, an unadulterated `std::vector` would work fine, it is that the header munges everything up -- read the comment: `// disgusting macro hack to get a range checked vector: #define vector Vector`. This is another case where you should use `std::` in your own code. – PaulMcKenzie Jul 12 '18 at 02:31
  • @PaulMcKenzie thank you, will do. The book has only introduced vector so far and the only header I import is the custom one for the book so a lot is abstracted. Not sure how to implement this algorithm without using so much as an array (also not taught in the book yet - I have a C background so I can go this route but am trying to restrict myself to the limitations the author imposes for learning benefit). – Dan Jul 12 '18 at 02:33
  • `std::vector is_composite;` -- This will use the "real" `std::vector` class instead of using the range-checked vector from the header. – PaulMcKenzie Jul 12 '18 at 02:40
  • I knew someone already had to have a good explanation here: [Why vector::reference doesn't return reference to bool?](https://stackoverflow.com/questions/8399417/why-vectorboolreference-doesnt-return-reference-to-bool) Definitely read the link at the top of the first answer. If this answer your question, I'll close as a duplicate. If not I'll see if I can write this up faster than someone else. – user4581301 Jul 12 '18 at 02:41
  • @user4581301 that makes sense. Go ahead and close. – Dan Jul 12 '18 at 02:43
  • @PaulMcKenzie the header somehow still gets in the way if I use the std namespace. I'll just avoid his header altogether for this one. – Dan Jul 12 '18 at 02:44
  • @Dan It shouldn't get in the way if you leave everything as-is and just say `std::vector is_composite;`. – PaulMcKenzie Jul 12 '18 at 02:45
  • @PaulMcKenzie no it won't compile. Somehow that header still interferes because he redefines vector in the standard namespace as Vector. Then lots of `__copysign` errors. I just included headers manually, which let it compile but I got a segfault during runtime. – Dan Jul 12 '18 at 02:49
  • @PaulMcKenzie would love to discuss further [in chat](https://chat.stackoverflow.com/rooms/116940/c-questions-and-answers) – Dan Jul 12 '18 at 02:49
  • Probably the best solution for you here, assuming you want to go on using `vector`, is to replace `#include "../include/std_lib_facilities.h"` with `#include #include #include using namespace std;` Some linefeeds are required in there. Comments suck at linefeeds. – user4581301 Jul 12 '18 at 02:53
  • @user4581301 I tried that. It compiles but I get a segmentation fault after entering the upper bound and don't know why. Maybe an issue with my loops (new issue). – Dan Jul 12 '18 at 02:55
  • Tactical note: even one call to `sqrt` can be quite expensive. It can also be imprecise, and may lead to losing a value due to an unfortunate truncation when converted to integer. You may get better performance from `for (int m = 2; m * m <= max; ++m)` – user4581301 Jul 12 '18 at 02:57
  • 2
    Your segfault is probably `std::vector is_composite;` allocates no storage to the `vector`. No storage means `is_composite[i] = false;` is writing into the unknown. `std::vector is_composite(max+1, false);` should fix that AND eliminate the need for the loop. The `vector` is sized appropriately and all of the values in it will be `false`. [See constructor (2) here for details.](https://en.cppreference.com/w/cpp/container/vector/vector) – user4581301 Jul 12 '18 at 03:05
  • @user4581301 that worked like a charm! Thank you! – Dan Jul 12 '18 at 03:09

0 Answers0