c++stdvectorerase

c++ while loop equivalent of for loop list traversal + erasure not working

Consider the following function

void removeOdd(vector<int>& v)
{
  for(vector<int>::iterator it=v.begin(); it!=v.end(); )
  {
      if((*it)%2) it = v.erase(it);
      else it++;
  }
}

which, when linked into the following test script

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

void test()
{
    int a[9] = { 5, 2, 8, 9, 6, 7, 3, 4, 1 };
    vector<int> x(a, a+9);  // construct x from the array
    assert(x.size() == 9 && x.front() == 5 && x.back() == 1);
    removeOdd(x);
    assert(x.size() == 4);
    sort(x.begin(), x.end());
    int expect[4] = { 2, 4, 6, 8 };
    for (int k = 0; k < 4; k++)
        assert(x[k] == expect[k]);
}

int main()
{
    test();
    cout << "Passed" << endl;
}

and compiled with WSL g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 with the -fsanitize=address flag, works just fine.

Compilation command: g++ -fsanitize=address test.cpp -o test

Output of test: Passed

However, the following while loop analogue of removeOdd,

void removeOdd_new(vector<int>& v)
{
  for(vector<int>::iterator it=v.begin(); it!=v.end(); it++)
  {
      while ((*it)%2)
        it = v.erase(it);
  }
}

when compiled with the same compiler under the same options i.e. g++ -fsanitize=address test_new.cpp -o test_new, throw the following error when run

==207338==ERROR: AddressSanitizer: negative-size-param: (size=-4)
    #0 0x7f26ba2d5f97 in __interceptor_memmove ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:810
    #1 0x5577715186c7 in int* std::__copy_move<true, true, std::random_access_iterator_tag>::__copy_m<int>(int const*, int const*, int*) (/mnt/c/Users/somebody/Downloads/test_new+0x86c7)
    #2 0x557771517a2b in int* std::__copy_move_a2<true, int*, int*>(int*, int*, int*) (/mnt/c/Users/somebody/Downloads/test_new+0x7a2b)
    #3 0x5577715166e0 in int* std::__copy_move_a1<true, int*, int*>(int*, int*, int*) (/mnt/c/Users/somebody/Downloads/test_new+0x66e0)
    #4 0x5577715157fb in __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > std::__copy_move_a<true, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >) (/mnt/c/Users/somebody/Downloads/test_new+0x57fb)
    #5 0x557771514e37 in __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > std::move<__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > >(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >) (/mnt/c/Users/somebody/Downloads/test_new+0x4e37)
    #6 0x5577715144bd in std::vector<int, std::allocator<int> >::_M_erase(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >) (/mnt/c/Users/somebody/Downloads/test_new+0x44bd)
    #7 0x557771513792 in std::vector<int, std::allocator<int> >::erase(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >) (/mnt/c/Users/somebody/Downloads/test_new+0x3792)
    #8 0x5577715125ec in removeOdd_new(std::vector<int, std::allocator<int> >&) (/mnt/c/Users/somebody/Downloads/test_new+0x25ec)
    #9 0x557771512b91 in test() (/mnt/c/Users/somebody/Downloads/test_new+0x2b91)
    #10 0x557771512f44 in main (/mnt/c/Users/somebody/Downloads/test_new+0x2f44)
    #11 0x7f26b9d69d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #12 0x7f26b9d69e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #13 0x5577715123c4 in _start (/mnt/c/Users/somebody/Downloads/test_new+0x23c4)

0x604000000024 is located 20 bytes inside of 36-byte region [0x604000000010,0x604000000034)
allocated by thread T0 here:
    #0 0x7f26ba3521e7 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:99
    #1 0x5577715168f7 in __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (/mnt/c/Users/somebody/Downloads/test_new+0x68f7)
    #2 0x557771515b79 in std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (/mnt/c/Users/somebody/Downloads/test_new+0x5b79)
    #3 0x5577715150fb in std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (/mnt/c/Users/somebody/Downloads/test_new+0x50fb)
    #4 0x557771514824 in void std::vector<int, std::allocator<int> >::_M_range_initialize<int*>(int*, int*, std::forward_iterator_tag) (/mnt/c/Users/somebody/Downloads/test_new+0x4824)
    #5 0x557771513950 in std::vector<int, std::allocator<int> >::vector<int*, void>(int*, int*, std::allocator<int> const&) (/mnt/c/Users/somebody/Downloads/test_new+0x3950)
    #6 0x557771512a79 in test() (/mnt/c/Users/somebody/Downloads/test_new+0x2a79)
    #7 0x557771512f44 in main (/mnt/c/Users/somebody/Downloads/test_new+0x2f44)
    #8 0x7f26b9d69d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58

SUMMARY: AddressSanitizer: negative-size-param ../../../../src/libsanitizer/sanitizer_common/sanitizer_common_interceptors.inc:810 in __interceptor_memmove
==207338==ABORTING

I am unable to understand the reason why the while loop version is throwing an address error because the while loop is logically no different from the for loop.

I also understand that the return value of std::vector.erase() is "(a)n iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence." This documentation is taken from https://cplusplus.com/reference/vector/vector/erase/.

Thus, the variable it in while loop should be updated accordingly (yet an error is thrown). I would also appreciate it if someone with a good understanding of cpp internals could help with interpreting the compiler error messages. Thank you!

Link to test.cpp and test_new.cpp: https://hackmd.io/54Mm2B1pStSPTWOkXJ4QtQ

Solution

  • The two are not equivalent.

    This:

    void removeOdd(vector<int>& v)
{
  for(vector<int>::iterator it=v.begin(); it!=v.end(); )
  {
      if((*it)%2) it = v.erase(it);
      else it++;
  }
}

    Will iterate all elements in the vector. It increments it until it==v.end() then the function returns.

    On the other hand, here

    void removeOdd_new(vector<int>& v)
{
  for(vector<int>::iterator it=v.begin(); it!=v.end(); it++)
  {
      while ((*it)%2)
        it = v.erase(it);
  }
}

    Once it reaches the last element, if that element is odd it will be erased, it becomes v.end() and *it dereferences the end iterator which is undefined.