Possible memory issue using an unordered_map with a vector as the object

Question

I'm writing a program that determines the prime factors of every number up to 120000. I'm trying to learn how to use unordered_map's, so that I have a map with an int as the key mapping to a vector of its prime factors.

The algorithm I've come up with involves listing all of the prime numbers below 120000, then recursively working through the products of 2 primes (2x3=6, 3x19=57 etc), then the products of 3 primes (2x2x5=20, 3x5x7=105 etc) and so on until I have a complete list.

I wrote the program to take in any maximum (not just 120000), and it works perfectly with values up to MAX_C=45000, however when I try it with MAX_C>50000, it breaks (and quite often crashes my computer.

I tried rewriting the program to avoid using unordered_maps, using a vector of my factorsAndTotal struct, but I had similar problems. I tried allocating arbitrarily large amounts of memory to the map, but to no avail.

I'm guessing this is a memory issue, but I'm not really sure, so I can't really post code fragments, sorry!

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

//structs
struct factorsAndTotal
{
    vector<int> factors;
    int total;
};

//prototypes
vector<int> allPrimesLessThan(int);
void buildPrimeFactorsMap();
vector<factorsAndTotal> siftNextSet(vector<factorsAndTotal>);

//globals
int MAX_C = 45000;
vector<int> primes;
unordered_map <int, vector<int> > mapPrimeFactors;

//main
int main() 
{   
    primes = allPrimesLessThan(MAX_C);
    mapPrimeFactors.reserve(MAX_C);

    buildPrimeFactorsMap();

    cout<<mapPrimeFactors.size()<<endl;

    return 0;

}

void buildPrimeFactorsMap()
{
    vector<int> chainOfFactors;
    vector<factorsAndTotal> sifting;

    factorsAndTotal temp;

    //add primes themselves to the map
    int size = primes.size();
    for (int i=0; i<size; i++)
    {
        //put them in map itself and get struct ready for recursion later
        chainOfFactors.push_back(primes[i]);

        mapPrimeFactors[primes[i]] = chainOfFactors;
        temp.factors = chainOfFactors;
        temp.total = primes[i];

        sifting.push_back(temp);

        chainOfFactors.clear();
    }
    //recursion
    while (!sifting.empty())
    {
        sifting = siftNextSet(sifting);
    }

    cout<<"factors found"<<endl;
}

vector<factorsAndTotal> siftNextSet(vector<factorsAndTotal> input)
{
    int total = 0;
    int i = 0, j = 0;
    int size = input.size(); 
    bool finished = false;
    vector<int> chainOfFactors;
    vector<factorsAndTotal> output;
    factorsAndTotal temp;

    for (i=0; i<size; i++)
    {
        //find last factor
        while (primes[j] < input[i].factors.back()) j++;

        while (!finished)
        {
            total = input[i].total*primes[j];

            if (total > MAX_C)
            {
                finished = true;
            }
            else
            {
                chainOfFactors = input[i].factors;
                chainOfFactors.push_back(primes[j]);

                mapPrimeFactors[total] = chainOfFactors;

                temp.total = total;
                temp.factors = chainOfFactors;
                output.push_back(temp);

                chainOfFactors.clear();

                j++;
            }
        }
        finished = false;
        j=0;
    }

    return output;
}

//returns primes less than a given number
vector<int> allPrimesLessThan(int x)
{
    vector<int> findingPrimes;

    int i = 0, j = 0;

    bool isPrime;

    for (i=2; i<=x; i++)
    {
        isPrime = true;

        for (j=0; j<findingPrimes.size(); j++)
        {
            if (i%findingPrimes[j] == 0) isPrime = false;
        }

        if (isPrime) findingPrimes.push_back(i); 
    }

    cout<<"primes found"<<endl;

    return findingPrimes;
}

Answer 1

The issue has little to do with the value of MAX_C you chose. Look at this loop, along with the usage of the variable j:

while (primes[j] < input[i].factors.back()) 
    j++;

while (!finished)  
{
    total = input[i].total*primes[j];  

When I run your code, j goes beyond the limit of the primes vector, since you're incrementing j in the while(!finished) loop.

The while(!finished) loop doesn't throttle how high j will go, so you need to make sure your loop either terminates or does something other than access the primes vector with an out-of-bounds value for j.

One way to ensure you don't go out of bounds:

while (!finished && j < primes.size() )  
{
    total = input[i].total*primes[j];