Erase-Remove Idiom

The technique of efficiently deleting elements that provide certain criteria from containers in C++ is called “Erase-remove idiom”.

The erase-remove idiom is a common technique used in C++ to remove elements from a container, such as a vector, based on a certain value or condition. It involves using the std::remove algorithm in combination with the erase member function to achieve the removal.

As you know, to delete an element from a container, it is necessary to call the container’s member function.

As seen above we deleted the first element by calling the container’s own erase function and it decreased to size. So this worked as expected.

std::remove (Remove value from range)

Transforms the range [first,last) into a range with all the elements that compare equal to val removed, and returns an iterator to the new end of that range.

The std::remove function shifts elements containing a given value towards the end of the vector and returns the next position of the new last element. Therefore, the std::remove function only moves values ​​and does not actually perform the delete.

That is, it never deletes, it just shifts the desired values ​​to the end.

for example, delete the value 5 from a vector containing 1,2,3,4,5,6,7,8,9,10,11,12,13,14

as you can see size has not decreased but the value 5 has been deleted.

So how does std::remove work?

Algorithms cannot directly delete the value from the vector. They move the value to be deleted to the end and change the end value of the iterator, thus making it appear as if the element to be deleted from the vector has been deleted.

As seen above, it didn’t actually delete the value 5, moved it to the end of the vector, and changed the iterator end address!

Size value has not changed.

std::vector<int> vec = {1,5,2,3,5,4,5,6,7,8,9,10, 5,11,12,13,14};

Let’s update our vector values ​​as above and want it to delete the 5 values.

We can print the undeleted items, the number of deleted and undeleted items to the screen as follows.

So what should we do if we want the size value to decrease when we delete it?

This is where the erase-remove idiom comes into play;

As seen above vector size changed. A deletion has actually been made.

Here, the erase-remove idiom is applied. The std::remove algorithm is used to shift all occurrences of valueToRemove towards the end of the vector. The remove algorithm returns an iterator pointing to the new logical end of the sequence. This iterator is then passed to the erase member function of the vector to physically remove the undesired elements.