Working of Erase Remove Idiom
This is a two-step technique that involves using both std::remove and std::erase functions one after another. The following are the steps:
- STEP 1: The std::remove function moves all elements to be removed at the end of the container. It returns the new logical end of the range.
- STEP 2: The std::erase function is then used to erase all the elements after the new logical end at once.
Erase-Remove Idiom in C++
Erase-Remove-Idiom is a C++ STL (Standard Template Library) technique to remove elements from a container. It is used to remove all the elements satisfying certain conditions from the container.
The erase-remove idiom is especially useful in array-based containers like vectors, where each elimination requires all the remaining elements to adjust. In the worst case, this may lead to O ( n2 ) time complexity. This technique avoids this by providing the elimination of the elements in a single parse. That is why, the erase-remove idiom provides O( n ) time complexity.
In this technique, we use the combination of two member functions of the container to remove the elements efficiently.
- std::erase
- std::remove or std::remove_if
It is due to the use of this function that this technique is called the erase-remove idiom.