How to erase or change element while iterating over vector in C++?

Question

I was in the middle of creating a simple sieve of Erathostenes function when I stumbled upon one obstacle. In to order to accomplish the highest efficiency in this task I wanted to use only a vector. Here is the current code:

vector<int> sieveOfErathostenes(int N) {

        vector <int> result(N, 1);

        for(int i = 2; i < sqrt(N); i++)

                if(result[i] == 1)

                        for(int j = 2*i; j < N; j += i)

                                result.at(j) = 0;
        //  :c
        return result;
}

This vector returns 1 and 0 in the proper position but I can't figure out how to implement both erasing or changing an element's value in a single loop. When I use an iterator to erase an element as in erase set element while iterating/// I can't access the vector to change its value, and when I use a standard for loop to access the element I can't remove it. I have tried going from the end of the vector and counting non zero elements and giving some offset when erasing but no success. TL DR: What I can't figure out is:

for(int i = 0; i < N; i++)
{
        if(result[i] == 0) {
                //remove at position i
        } else {
                result.at(i) = i;
        }
}

Thank you in advance for your time :)

[Erasing elements in vector](https://en.cppreference.com/w/cpp/container/vector/erase) takes O(n) time and is not effective. — MikeCAT, Jan 12 '21 at 17:52
Also using `at()` may be ineffective because they do range checking. — MikeCAT, Jan 12 '21 at 17:56

score 1 · Accepted Answer · answered Jan 12 '21 at 17:58

1

Instead of erasing elements in the middle of the vector, you should write the results from the beginning of the vector and eliminate the unused elements in the end of vector.

int finalSize = 0;
for(int i = 0; i < N; i++)
{
        if(result[i] != 0) {
                result[finalSize++] = i;
        }
}
result.resize(finalSize);

answered Jan 12 '21 at 17:58

MikeCAT

73,922
11
45
70

And in case someone lands here, this is exactly what [std:remove_if](https://en.cppreference.com/w/cpp/algorithm/remove) does. So unless you are forbidden from using std algorithms for some reason, use that instead. – spectras Jan 12 '21 at 18:13
So simple, yet so powerful. Failure of my imagination saddens me deeply. Thank you kind sir :D – Jan 12 '21 at 18:17

alex_noname · Answer 2 · 2021-01-12T18:05:02.887

0

If you still need to remove an element from a std::vector during traversal, keep in mind that erase returns an iterator following the last removed element:

  std::vector<int> result = {1,1,1,0,1,1,1};
  for(auto it = result.begin(); it != result.end(); )
  {
    if(*it==0)
      it = result.erase(it);
    else
      it++;
  }

edited Jan 12 '21 at 18:05

answered Jan 12 '21 at 17:59

alex_noname

26,459
5
69
86

Thank you very much :D – Jan 12 '21 at 18:17

How to erase or change element while iterating over vector in C++?

2 Answers2