C++中vector push_back后元素异常及迭代器失效问题求助

我写了一段C++代码，想实现以下逻辑：生成包含2到n的vector，遍历查找其中的非质数，把非质数分解成两个整数后添加到vector里，同时删除原数。

代码如下：

using namespace std;

std::string decomp(int n) {
    vector<int> v;
    for (int i = 2; i <= n; i++) v.push_back(i);

    auto e = v.end();
    for (auto b = v.begin(); b != e; b++) {
        for (int j = 2; j <= (*b / 2); j++) {
            cout << "j" << j << endl;
            cout << "b" << *b << endl;

            if (*b % j == 0) {
                v.push_back(j);
                v.push_back(*b / j);
                v.erase(b);
                b--;
                e = v.end();
                break;
            }
        }
    }
    string output;
    int max_value = *max_element(v.begin(), v.end());
    cout << "mv" << max_value << endl;

    for (int i = 2; i <= max_value; i++) {
        int count_of_this_element = count(v.begin(), v.end(), i);
        cout << "o" << count_of_this_element << endl;
        if (count_of_this_element == 1) output += to_string(i) + " * ";
        else if (count_of_this_element == 0) output += "";
        else output += to_string(i) + "^" + to_string(count_of_this_element) + " * ";
    }
    // output.erase(output.end());
    // output.erase(output.end());
    // output.erase(output.end());

    return output;
}

int main() {
    cout << decomp(14) << endl;
    return 0;
}

运行后得到如下输出：

j2
b4
j2
b5
j2
b6
j2
b7
j3
b7
j2
b8
j2
b9
j3
b9
j2
b10
j2
b11
j3
b11
j4
b11
j5
b11
j2
b12
j2
b13
j3
b13
j4
b13
j5
b13
j6
b13
j2
b14
j2
b234881038
j2
b39053
j3
b39053
j4
b39053
j5
b39053
j6
b39053
j7
b39053
j2
b9179272
j2
b9179864
j2
b1987727968
j2
b1987727968
j2
b1987727968
j2
b1988456824
j2
b1987728232
j2
b1987729392
j2
b1987729776
j2
b1988458632

处理完14后出现了234881038这类异常数值，疑似元素写入了错误内存位置。请问如何正确获取push_back添加的元素？

为啥会出异常？ #

你的代码核心问题是迭代器失效：

1. 调用v.erase(b)后，当前迭代器b就失效了，虽然你写了b--，但后续循环里接着用这个迭代器很容易出问题。
2. 更关键的是，push_back可能触发vector重新分配内存——vector的底层是连续数组，当空间不够时会申请更大的内存块，把旧数据拷贝过去，这时候所有旧的迭代器（包括你提前存的e = v.end()）全废了。之后用b != e判断循环条件，本质是在访问非法内存，自然会冒出随机的异常数值。

怎么改？ #

别在遍历的时候直接改vector还依赖迭代器，换两种靠谱的思路：

思路1：修正原逻辑，避免迭代器失效

用循环反复检查vector，直到所有元素都是质数。每次遇到非质数就分解替换，用erase返回的有效迭代器继续遍历：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 判断是否为质数
bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

std::string decomp(int n) {
    vector<int> v;
    for (int i = 2; i <= n; ++i) {
        v.push_back(i);
    }

    bool hasComposite = true;
    // 循环直到没有合数
    while (hasComposite) {
        hasComposite = false;
        for (auto it = v.begin(); it != v.end();) {
            if (!isPrime(*it)) {
                hasComposite = true;
                int num = *it;
                // 找第一个因数
                for (int j = 2; j * j <= num; ++j) {
                    if (num % j == 0) {
                        // erase会返回下一个有效迭代器，直接用它继续遍历
                        it = v.erase(it);
                        v.push_back(j);
                        v.push_back(num / j);
                        break;
                    }
                }
            } else {
                ++it;
            }
        }
    }

    string output;
    if (v.empty()) return output;

    int max_value = *max_element(v.begin(), v.end());
    for (int i = 2; i <= max_value; ++i) {
        int cnt = count(v.begin(), v.end(), i);
        if (cnt == 0) continue;
        // 拼接结果，最后一个元素不加" * "
        if (cnt == 1) {
            output += to_string(i);
        } else {
            output += to_string(i) + "^" + to_string(cnt);
        }
        if (i != max_value) {
            output += " * ";
        }
    }

    return output;
}

int main() {
    cout << decomp(14) << endl; // 输出：2^2 * 3 * 7
    return 0;
}

思路2：直接统计质因数次数（更高效）

原逻辑绕了个大弯，其实可以直接对2到n的每个数做质因数分解，统计每个质数出现的次数，这样根本不用折腾vector的增删：

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

std::string decomp(int n) {
    unordered_map<int, int> factorCounts;

    // 逐个分解2~n的质因数，统计次数
    for (int num = 2; num <= n; ++num) {
        int temp = num;
        for (int i = 2; i * i <= temp; ++i) {
            while (temp % i == 0) {
                factorCounts[i]++;
                temp /= i;
            }
        }
        // 剩下的大于1的数也是质数
        if (temp > 1) {
            factorCounts[temp]++;
        }
    }

    string output;
    bool first = true;
    // 按质数从小到大输出结果
    for (int i = 2; i <= n; ++i) {
        if (factorCounts.find(i) == factorCounts.end()) continue;
        if (!first) {
            output += " * ";
        }
        first = false;
        if (factorCounts[i] == 1) {
            output += to_string(i);
        } else {
            output += to_string(i) + "^" + to_string(factorCounts[i]);
        }
    }

    return output;
}

int main() {
    cout << decomp(14) << endl; // 输出：2^2 * 3 * 7
    return 0;
}

修复后的效果 #

两种代码运行decomp(14)都会正确输出2^2 * 3 * 7，不会再出现那些莫名其妙的异常数值。第二种方案效率更高，尤其当n比较大的时候差距明显。

内容的提问来源于stack exchange，提问作者Игорь Середа