Deleting elements from a vector that meet a condition

Question

I am trying to program the Sieve of Eratosthenes, but I am not sure how to delete elements from the vector I made given a specific condition. Does anyone know how to achieve this? Here is my code:

#include <iostream>
#include <vector>

using namespace std;

int prime(int n);

int prime(int n)
{
    vector<int> primes;

    for(int i = 2; i <= n; i++)
    {
        primes.push_back(i);
        int t = i % (i + 1);

        if(t == 0)
        {
            delete t; // is there a way of deleting the elements from 
            // the   primes vector that follow this condition t?
        }

        cout << primes[i] << endl;
    }
}

int main()
{
    int n;
    cout << "Enter a maximum numbers of primes you wish to find: " << endl;
    cin >> n;
    prime(n);

    return 0;
}

Instead of "physically" removing elements, I'd recommend using an additional vector in which to store a `bool` flag that you set to `true` whenever the corresponding number in your initial vector is a multiple of a prime. Removing elements is "slow", as the vector has to shift elements around. In case you really want to remove elements, check the [Erase/Remove idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom). — vsoftco, Jun 17 '15 at 04:57

score 1 · Answer 1 · edited Jun 17 '15 at 05:25

1

You don't usually want to delete elements in the middle of a Sieve of Eratosthenes, but when you do want to, you usually want to use the remove/erase idiom:

x.erase(std::remove_if(x.begin(), x.end(), condition), x.end());

std::remove basically just partitions the collection into those that don't meet the specified condition, followed by objects that may have been used as the source of either a copy or a move, so you can't count on their value, but they are in some stable state so erasing them will work fine.

The condition can be either a function or a functor. It receives (a reference to a const) object that it examines and determines whether it lives or dies (so to speak).

edited Jun 17 '15 at 05:25

juanchopanza

223,364
34
402
480

answered Jun 17 '15 at 05:00

Jerry Coffin

476,176
80
629
1,111

Did you mean to use `std::remove_if`? – R Sahu Jun 17 '15 at 05:07
I see, so my method could be improved. Do you know how I would go about changing the implementation? – Jun 17 '15 at 05:35

score 1 · Accepted Answer · answered Jun 17 '15 at 05:42

1

Your algorithm is wrong:

t = i % (i + 1);

is

which is always != 0 because i is larger than 1. By the way if you absolutely want to remove the t-th element you have to be sure that the vector is not empty and then you do:

primes.erase(primes.begin()+t);

Even if you fix the algorithm your approach is inefficient: erasing an element in the middle of a vector means copying back of one position all the ones following the erased element.

answered Jun 17 '15 at 05:42

jimifiki

5,377
2
34
60

How would you suggest I implement the algorithm then? – Jun 17 '15 at 06:19
If you can read Python, find here an implementation you can use as inspiration: http://stackoverflow.com/questions/9043791/python-eratosthenes-sieve-algorithm-optimization/9043972#9043972 otherwise study thorough the pseudo code for the algorithm and implement it. – jimifiki Jun 27 '15 at 13:14

score 0 · Answer 3 · answered Jun 27 '15 at 13:30

Find here a c++ pseudocode for the sieve algorithm. Once you've understood the algorithm you can start working on this.

primes(vector& primes, size_t max){

  vector primesFlag(1,max);

    i=1
    while(i*i<max){

        ++i;
        for(j=i*i; j < max; j+= i){
            primesFlag[j] = 0;
        }
    }

    primes.clear()
    primes.reserve(...);
    for(j >= 2;
        if primesFlag[j] = 1 
            primes.push_back(j);
}

Deleting elements from a vector that meet a condition

3 Answers3