c++ - C++ 删除/删除算法中的指针问题

Question

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

1. 创建一个由 2 到 n 之间的整数组成的 vector 。

2. 从 vector 的最小元素 2 开始，将其添加到新的素数 vector 中，然后从整数 vector 中删除所有 2 的倍数。

3. 使用整数 vector 的新最小元素(即 3)重复此过程并重复直到整数 vector 为空。素数 vector 然后包含所有需要的素数。

现在，这段代码可以工作了:

#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;
}

值得注意的是，后一个程序正确返回所有素数，但也正确返回 4。我发现后一个程序将 2 添加到素数列表，然后添加 3 并删除 3 的倍数，然后添加 4 和删除 4 的倍数，等等。但重要的是没有删除 2 的倍数。

为什么后一个程序有这个错误，当我简单地替换了 while 循环中的 p (它等于 *ptr) 与 *ptr？我原以为 ptr 和 *ptr 在 while 循环的每次迭代中都不会改变(直到循环的最后一行，当然)，但显然他们这样做了。

Answer 1

std::remove_if()(可能)重新排序 vector 的元素。因此，ptr 不再必然指向 std::remove_if() 谓词的进一步调用中的相同值。相比之下，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());

附言它对该程序的结果并不重要，但 std::vector 的迭代器不一定是指针。