c++ erase/remove 算法中的指针问题

Question

我一直在尝试创建一个 C++ 程序来查找某个整数 n 下的所有质数，使用 Sieve of Eratosthenes algorithm，如下所示：

创建一个整数向量，范围从 2 到 n。
从向量的最小元素 2 开始，将其添加到新的素数向量中，然后从整数向量中删除所有 2 的倍数。
使用整数向量的新最小元素（即 3）重复此过程，并重复直到整数向量为空。然后素数向量包含所有需要的素数。

现在，此代码有效：

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

void printVector(std::vector<int> v){
    for(int i: v)std:: cout << i << " ";
    std::cout << std::endl;
}

std::vector<int> primesBelow(int n){
    std::vector<int> primes {}, integers {};

    for(int i = 2; i <= n; i++) integers.push_back(i); //list elements 2 to n

    auto ptr = integers.begin(); //pointer to smallest element

    while(ptr != integers.end()){
        int p = *ptr;
        primes.push_back(p);
        integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){return x%p==0;}), integers.end());
    
        ptr = integers.begin();
    }
    return primes;
}

int main() {
    auto v = primesBelow(100);
    printVector(v);
    return 0;
}

但是，下面的代码不起作用（唯一的区别是在 while 循环中）：

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

void printVector(std::vector<int> v){
    for(int i: v)std:: cout << i << " ";
    std::cout << std::endl;
}

std::vector<int> primesBelow(int n){
    std::vector<int> primes {}, integers {};

    for(int i = 2; i <= n; i++) integers.push_back(i); //list elements 2 to n

    auto ptr = integers.begin(); //pointer to smallest element

    while(ptr != integers.end()){
     
        primes.push_back(*ptr);
        integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){return x%*ptr==0;}), integers.end());
    
        ptr = integers.begin();
    }
    return primes;
}

int main() {
    auto v = primesBelow(100);
    printVector(v);
    return 0;
}

值得注意的是，后一个程序 returns 所有素数都是正确的，但也是 4。我已经计算出后一个程序将 2 添加到素数列表中，然后添加 3 并删除的倍数3，然后加 4 并去掉 4 的倍数，等等。但重要的是 没有去掉 2 的倍数。

为什么后一个程序有这个错误，当我只是将 while 循环（等于 *ptr）中的 p 替换为 *ptr ？我原以为 ptr 和 *ptr 在 while 循环的每次迭代中都不会改变（当然，直到循环的最后一行），但显然它们会改变。

Answer 1

std::remove_if()（可能）重新排序向量的元素。因此，在进一步调用 std::remove_if() 谓词时，ptr 不再一定指向相同的值。相比之下，p的值不受std::remove_if()的影响。

您可以通过一些临时调试看到它们并不相同：

int p = *ptr;
primes.push_back(*ptr);
integers.erase(std::remove_if(integers.begin(), integers.end(), [=](int x){
    if (p != *ptr)
        std::cout << "Not the same\n"; // would not show if they had the same value
    return x%*ptr==0;
}), integers.end());

P.S。这对这个程序的结果并不重要，但 std::vector 的迭代器不一定是指针。

c++ erase/remove 算法中的指针问题

Issues with pointers in c++ erase/remove algorithm

c++

erase-remove-idiom