Prime factorization of number error

Question

I made a function that returns a vector with all the prime factors of an integer, and I am trying to make another function that creates a map from that vector.

However, I am getting some typicall illegal memory access error and I cannot find what it is. I think it happens inside the for loop of the map<int, int> factorizacion(vector<int>) function.

I hope I could get some help here.

I could post the whole program but I'll just stick to the function that's causing the issue. Just ask for the rest of the code in case you need to give it a look.

map<int, int> factorizacion(vector<int> v) {
    map<int, int> m;

    while (!v.empty()) {
        int elto = v.front();
        int ctd = 0;

        for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
            if (*it == elto) {
                ++ctd;
                v.erase(it);
            }
        }
        m[elto] = ctd;
    }

    return m;
}

Erasing from the vector makes your iterators invalid and leads to undefined behaviour — Niklas B., Feb 26 '14 at 14:48
http://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating — chris, Feb 26 '14 at 14:48
The same thing can be achieved using `multiset(v.begin(),v.end())`, by the way, or by a simple `for (int x: v) m[x]++;` — Niklas B., Feb 26 '14 at 14:49
@NiklasB. Worth mentioning that the enhanced for works only in C++11 — Boris Strandjev, Feb 26 '14 at 14:59
@Boris: OP seems to know how to iterate over a vector even without range-based for loops, so he should be able to adapt it in case he decides to use an outdated compiler :) — Niklas B., Feb 26 '14 at 15:29
actually I am kind of struggling with iteration now. is there any way to get the previous/next iterator of an iterator with C++98? — dabadaba, Feb 26 '14 at 15:30
@dabadaba: For RandomIterator, you can use `+1` and `-1`, but I don't need that very often. Why do you think you need it? And more importantly, why do you use C++98? I mean, at least C++03 should be supported by every compiler by now — Niklas B., Feb 26 '14 at 15:31
I get a compilation error when I try `m.end()-1`. I just want to stop the printing loop before the last element so I don't get an extra plus sign. Yeah, it's C++03. — dabadaba, Feb 26 '14 at 15:36
@dabadaba: Yeah, map iterators don't support random access obviously. You can just use the [example implementation from cppreference](http://en.cppreference.com/w/cpp/iterator/prev) if you really want to. But I would rather do something like `bool first = 1; for (map::iterator it = m.begin(); it != m.end(); ++it) { if (!first) cout << " + "; first = 0; cout << it->fst << "^" << it->snd; }` otherwise you need to duplicate the loop body. You should also consider using C++11 if you have the choice. — Niklas B., Feb 26 '14 at 15:44
Or just `for (map::iterator it = m.begin(); it != m.end(); ++it) { if (it != m.begin()) cout << " + "; cout << it->fst << "^" << it->snd; }` — Niklas B., Feb 26 '14 at 16:00

Boris Strandjev · Accepted Answer · 2014-02-26T14:56:37.987

You modify a collection you iterate upon:

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    if (*it == elto) {
        ++ctd;
        v.erase(it);
    }
}

If you erase the item pointed by the iterator you can not just continue using the same iterator.

Btw you can make use of the fact that map will automatically initialize to 0 a value for key that does not exist.

This code will do what you want:

map<int, int> m;
for (int i = 0; i < v.size(); i++) {
  m[v[i]]++;
}

The only thing is that performance-wise my solution is a bit slower - it executes more queries than the optimal solution. However, the solution I propose is better that yours (when it gets fixed, because):

Erasing in a vector is costly operation and takes linear time, a lot worse performance wise than my map tweak
I do not alter the parameter of the method. I know it is not passed in by reference but it is always a good idea not to affect parameters when this is possible.

Steve Jessop · Answer 2 · 2014-02-26T14:55:08.237

1

v.erase(it) makes it invalid. You need to change your loop:

for (vector<int>::iterator it = v.begin(); it != v.end();) {
    if (*it == elto) {
        ++ctd;
        it = v.erase(it);
    } else {
       ++it;
    }
}

Or better, use std::remove and .erase similarly to the "erase-remove" idiom. Which I won't repeat here because you can look it up. You can compute the count as the difference between two iterators.

Or even better, count the factors without erasing them at all, as in Niklas's comment.

edited Feb 26 '14 at 14:55

answered Feb 26 '14 at 14:49

Steve Jessop

273,490
39
460
699

Thanks, now it works. But can you explain why my program gave an error and why those changes need to be done? – dabadaba Feb 26 '14 at 15:37
@dabadaba: "`v.erase(it)` makes `it` invalid" is the explanation why your program is undefined and the proposed code sample in this answer contains the changes that need to be done. – Niklas B. Feb 26 '14 at 15:48
oooh so `it` is somewhat flagged? – dabadaba Feb 26 '14 at 15:53
@dabadaba: [`vector::erase` "Invalidates iterators and references at or after the point of the erase, including the `end()` iterator."](http://en.cppreference.com/w/cpp/container/vector/erase) – Niklas B. Feb 26 '14 at 15:55

Prime factorization of number error

2 Answers2