std::bad_alloc crash

Hello,

I'm not sure whether this is a Qt issue or something deeper, which is why I am posting it here. Please move this topic if it is better placed elsewhere.

Just for fun and learning, I decided to look into prime number sieves. Knowing nothing about them, I settled on what is generally regarded as the simplest to implement. Here is my complete, naive code:

Code:

---

#include <QCoreApplication>
#include <QDebug>
#include <QtMath>
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    /**
      * Seive of Eratosthenes
      * see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
      */
 
    // initialize
    const int n = INT16_MAX;
    QList<bool> sieve;
    for (int i = 0; i <= n; ++i)
        sieve.append(true);
 
    // compute
    for (int i = 2; i <= qFloor(qSqrt(n)); ++i) {
        if (sieve.at(i) == true) {
            for (int j = i*i; j <= n; j += i)
                sieve.replace(j, false);
        }
    }
 
    // print!
    QList<QString> primes;
    for (int i = 2; i < sieve.count(); ++i)
        if (sieve.at(i) == true)
            primes.append(QString::number(i));
    qDebug() << primes.join(", ");
 
    return a.exec();
}

---

It works correctly. However, if I change the value of n to INT32_MAX, the program crashes with the following error:

Code:

---

libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc

---

The problem appears to be in the initialization loop. For example, if I comment out the call to append and just let the loop run without a body, the program hangs. If I then change <=n to <n, it goes to completion. If I then uncomment the call to append, it crashes as before. Can anyone explain why this is?

Thank you!

Haha, I stopped and actually thought about just how big INT32_MAX is, and it's something like 4 billion. I guess I'm just filling up my computer's memory. Nothing to see here! ;)

In any case QList is not the best container to use for the sieve.
Since you already know the number of entries beforehand, you could simply use a vector, e.g. QVector.

Code:

---

QVector<bool> sieve(n, true);

---

In this very specific case, with the value type being a simple bool, you could even use QBitArray

Code:

---

QBitArray sieve(, true);

---

which only needs one byte for 8 values.

Might even work with INT32_MAX then :)

Cheers,
_

Thanks very much for your observations. The new, vector-based code looks like this:

Code:

---

// initialize
const int n = INT16_MAX;
QVector<bool> sieve(n+1, true);

---

You'll notice the 'n+1'. When I simply used n, I got an index-out-of-range fatal error while computing the sieve. 'n' is actually not a great variable name because it typically connotes number of elements, whereas in this algorithm it is actually a max value, matched by its index.

Finally, using a QBitArray yielded the same bad_alloc crash with INT32_MAX, alas! But, it was a good suggestion. :)