CODEWITHSUNDEEP
c++stl
oggmonster
oggmonster

Reputation: 4872

What is the difference between remove-erase and find-erase

Suppose you want to remove a single element from a vector by value. What is the difference between remove-erase:

vector<int> v;
// add some values
vector<int>::iterator it = remove(v.begin(), v.end(), 5);
v.erase(it);

And find-erase

vector<int> v;
// add some values
vector<int>::iterator it = find(v.begin(), v.end(), 5);
if(it != v.end())
{
  v.erase(it);
}

Upvotes: 8

Views: 944

Answers (3)

codeling
codeling

Reputation: 11379

The difference would be that if there is more than one value matching the given one, the remove solution will move all of the non-matching items to the start (thanks to Steve Jessop for pointing it out in the comments). Only erase will then remove the first occurence of these; and you end up with a re-sorted vector, containing one less of the given value.

The find- solution would only remove the first occurence, and not change the order of the vector.

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279255

Your remove-erase code is not correct. The remove-erase idiom looks like this:

vector<int>::iterator it = remove(v.begin(), v.end(), 5);
v.erase(it, v.end());

In that case, it has the effect of erasing all values equal to 5 but it minimises the amount of copying required to achieve that.

Your find-erase code removes only the first value equal to 5, so it does what you want.

Your remove-erase code moves all the values not equal to 5 to the front of the vector (that's what std::remove does), erases one of the remaining elements of the vector, and leaves any remaining elements after that with unspecified values (which is also what remove does). It has undefined behavior if the vector doesn't contain a 5 to begin with, because remove would return v.end() in that case.

So, if you only want to erase a single element of several equal to 5 then std::remove is no use to you because it doesn't preserve the (other) 5s. If you want to move the non-5 values to the start and the 5 values to the end, before removing the first of the 5s, then you could in fact do that with std::partition just not with std::remove:

auto it = partition(v.begin(), v.end(), [](int i) { return i != 5; });
if (it != v.end()) v.erase(it);

Although, since one 5 is as good as another you get the same result by erasing the last of the 5s rather than the first, and it's more efficient when there's more than one of them:

auto it = partition(v.begin(), v.end(), [](int i) { return i != 5; });
if (it != v.end()) v.pop_back();

If you can somehow be sure that the vector initially contains exactly one element equal to 5 (no more or less), then your two bits of code do the same thing. And in that case you wouldn't need the test for it != v.end() in the find-erase code, you would know it isn't equal. You could just do v.erase(find(v.begin(), v.end(), 5)).

Upvotes: 15

Marius Bancila
Marius Bancila

Reputation: 16328

Did you actually try to see the difference?

In the first piece of code, std::remove transforms the vector by placing all the elements that are equal to 5 to the end of the vector and returns the iterator to the new end. When you call erase then you remove the first element after the new end. You probably want to do:

vector<int>::iterator it = remove(v.begin(), v.end(), 5);
v.erase(it, v.end());

That would remove all the elements with value 5.

In the second example, std::find finds the first element of the vector that is equal to 5 and returns an iterator to it. Calling erase will only remove that element.

That is the difference.

Upvotes: -1

Related Questions