Erasing using iterator from 'find' or 'remove'

Question

I would like to know what's the best practice to remove an element from a vector in C++.

I have seen many times people using std::remove to find and delete the element, and then using erase to remove the element from the vector.

But why is it better than using find to get the iterator of the element you want to remove and then using the erase with that iterator?

Thanks

Klausenburg

Answer 1

std::find followed by vector::erase will erase the first occurrence of an object with the given value from the vector.

std::vector<int> vec{1,3,3,8,3,5};
vec.erase(std::find(vec.begin(), vec.end(), 3));
//vec == {1,3,8,3,5}

std::remove followed by vector::erase will remove every occurrence of an object with the given value from the vector.

std::vector<int> vec{1,3,3,8,3,5};
vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
//vec == {1,8,5}

Neither is better, they just do different things.

std::remove is more generally useful, and that is why it is more often seen; in particular, std::remove followed by vector::erase does nothing when the element is not present in the vector, while std::find followed by vector::erase has undefined behavior.

Note that both "find-erase", "remove-erase" maintain the relative order of the elements. If you want to remove an element from the vector but do not care about the resulting order of the elements, you can use "find-move-pop_back" or "partition-erase":

//find-move-pop_back
std::vector<int> vec{1,3,3,8,3,5};
*std::find(vec.begin(), vec.end(), 3) = std::move(vec.back());
vec.pop_back();

//partition-erase
std::vector<int> vec{1,3,3,8,3,5};
vec.erase(
    std::partition(vec.begin(), vec.end(), [](int v){return v != 3;}),
    vec.end());

Sherfield

Note that partition-erase will remove elements for which predicate returns false, and remove-erase will remove elements for which predicate returns true. – Communion

Shouldn't std::remove have better efficiency for std::vector, since it moves the elements to the end of the vector first (avoid realloc)? – Restrict

Answer 2

You're right that std::erase and std::remove simply return an iterator. But std::remove does one thing differently: it moves the elements to be removed to the end of the vector first. Then your meant to call std::erase from the element std::remove returns, to the end of the vector.

You can use that property to find out how many elements were removed from the std::vector:

void print( vector<string> &v ) {
  for( auto&& s : v ) {
    printf( "  - %s\n", s.c_str() );
  }
  puts("");
}

int main() {
  
  vector<string> s = { "Strings", "a", "in", "a", "a", "a", "test", "test", "a", "a", "vector" } ;
  puts( "Original" );
  print( s );

  auto it = std::remove( s.begin(), s.end(), "a" );
  printf( "Deleting %d elts\n", s.end() - it );
  s.erase( it, s.end() );

  puts( "After" );
  print( s );

}

Restrict