C++ vector erase function not working properly

Question

I want to erase all elements with value greater 2 and less 5 here is the code :

 vector<int> myvector{3, 3, 3, 3, 3, 3, 3, 1, 2, 3, 4, 5 , 2, 3, 4, 9};
 vector<int>::iterator it;

 it = myvector.begin();
 for(int i = 0; i < myvector.size(); i++)
 {
   if(myvector[i] > 2 && myvector[i] < 5)
   {
     myvector.erase(it+i);
   }
     
 }
 for(int i = 0; i < myvector.size(); i++)
 {
   cout << ' ' << myvector[i];
     
 }

output: 3 3 3 1 2 4 5 2 4 9

Where is the problem.

You cannot rely on the value of `it` after calling `erase`. This operation "invalidates iterators at or after the point of erase", which could mean the stored `myvector.begin()` value. In your case, there's no reason why you shouldn't just use `myvector.begin()` always. However, there's another problem. Consider what happens when item 0 and item 1 in the vector are both to be erased. You start with `i==0` and erase that. Now the second item is at position 0, but the loop will advance `i` to 1, skipping over it. — paddy, Dec 08 '20 at 09:02
See [std::erase_if](https://en.cppreference.com/w/cpp/container/vector/erase2) — paddy, Dec 08 '20 at 09:05
Besides the correctness issue, calling `erase` iteratively is not efficient, O(n^2) in the worst case. A better solution is to use a simple for loop with two indices, one for read and one for write.Or use `std::erase_if` as mentioned above. — Damien, Dec 08 '20 at 09:05
*Where is the problem* -- The problem is not using the proper algorithm functions to do this work, such as [std::remove_if](https://en.cppreference.com/w/cpp/algorithm/remove). If you find yourself writing raw loops to do something that seems that it has been done before, there is usually an algorithm function that does the work. — PaulMcKenzie, Dec 08 '20 at 09:09
The issue was in index if any element erased index values are changed — Villance, Dec 08 '20 at 10:43

Vlad from Moscow · Answer 1 · 2020-12-08T09:21:27.600

3

Use the approach with applying the standard algorithm std::remove_if. For example

#include <vector>
#include <iterator>
#include <algorithm>

//...

    std::vector<int> myvector{ 3, 3, 3, 3, 3, 3, 3, 1, 2, 3, 4, 5 , 2, 3, 4, 9 };

    myvector.erase( std::remove_if( std::begin( myvector ), std::end( myvector ),
        []( const auto &item )
        {
            return 2 < item && item < 5;
        } ), std::end( myvector ) );

    for (const auto &item : myvector) std::cout << item << ' ';
    std::cout << '\n';

The output of this code snippet is

1 2 5 2 9

Using this for loop

for(int i = 0; i < myvector.size(); i++)

is incorrect. For example if you have a vector with 2 elements and in the first iteration the element with the index 0 was deleted when i will be incremented and equal to 1. So as now i equal to 1 is not less then the value returned by size() then the second element will not be deleted.

Apart from this such an approach with sequential erasing elements in a vector also is inefficient.

edited Dec 08 '20 at 09:21

answered Dec 08 '20 at 09:10

Vlad from Moscow

301,070
26
186
335

1

For a homework exercise, I would advise a named function over an unnamed lambda. It makes the separation of responsibilities clearer. – MSalters Dec 08 '20 at 12:11
Yes exactly the issue was in for loop not in erase function. After index shifts but loop control remained same. In your example, if using `std::remove_if` then why `erase`? – Villance Dec 09 '20 at 11:13
1

@Villance After erasing an element the used iterator can be invalid. – Vlad from Moscow Dec 09 '20 at 11:18

score 1 · Answer 2 · edited Dec 08 '20 at 09:11

1

The problem is with using the erase function in a loop with iterators of that modified vector. From the cppreference page for the erase function (bolding mine):

Erases the specified elements from the container.

Removes the element at pos.

Removes the elements in the range [first, last).

Invalidates iterators and references at or after the point of the erase, including the end() iterator.

Correctly erasing elements inside a loop can be done, but it is a little tricky. The easier way is to apply the erase-remove-idiom. Or if you can use C++20, have a look at std::erase_if.

edited Dec 08 '20 at 09:11

463035818_is_not_an_ai

109,796
11
89
185

answered Dec 08 '20 at 09:02

Adrian Mole

49,934
160
51
83

Yes C++20 `std::erase_if` is good, Here i put just an example but i required it for deleting index in randomly distributed points on x-y plane. – Villance Dec 09 '20 at 11:18

C++ vector erase function not working properly

2 Answers2