Erase-remove Idiom Revisited

• Download source code - 3.7 KB

Recently, I reread Erase-remove Idiom on classic Effective STL by Scott Meyers, which is dated by now, so I also consulted the same topic on another STL book published in 2017. How to remove elements from container is a common C++ interview question, so you may want to sit up and pay attention here.

std::vector contains an erase function to remove elements. The problem is once erase is called, all iterators are invalidated. That means if std::vector contains more than 1 element which satisfy the criteria to be removed, developer has to restart iterating by getting a new iterator from vector::begin(). A much better way is to use erase-remove Idiom. First, we use the STL remove/remove_if to move the removed elements to back of the vector container. STL remove/remove_if, despite their name, cannot remove anything from the std::vector because they operate on iterators and are not aware of the underlying container object. So after calling remove/remove_if, we have to call container's erase to actually erase the elements.

remove takes in value to be removed as the last argument: Any element matching the same value is 'removed'. Whereas remove_if takes in functor or lambda as predicate in the last argument: Any element which satisfies predicate is 'removed'.

// initializes a vector that holds the numbers from 0-9.
std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
print(v);

// removes all elements with the value 5
v.erase( std::remove( v.begin(), v.end(), 5 ), v.end() );
print(v);

// removes all odd numbers
v.erase( std::remove_if(v.begin(), v.end(), is_odd), v.end() );
print(v);

std::remove/std::remove_if Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 6 7 8 9
0 2 4 6 8

From Wikipedia Erase–remove idiom

STL remove/remove_if returns Past-the-end iterator for the new range of values (if this is not end, then it points to an unspecified value, and so do iterators to any values between this iterator and end).

If no element is 'removed', remove/remove_if returns v.end(), so the erase call actually does nothing and no element is erased.

v.erase( v.end(), v.end() );

STL remove/remove_if shifts the rest of the elements to fill the gap left by removed element. The performance could be improved if maintaining relative order between the elements is not a requirement. Mentioned in Mastering the C++17 STL by Arthur O'Dwyer', unstable_remove has been proposed for future standardization but has not yet adopted into the STL. unstable_remove does not shift the remaining element to fill the 'hole', instead it moves the last element to fill the 'hole'.

namespace my 
{
    template<class BidirIt, class T>
    BidirIt unstable_remove(BidirIt first, BidirIt last, const T& value)
    {
        while (true) 
        {
            // Find the first instance of "value"...
            first = std::find(first, last, value);
            // ...and the last instance of "not value"...
            do 
            {
                if (first == last) 
                    return last;
                --last;
            } 
            while (*last == value);
            // ...and move the latter over top of the former.
            *first = std::move(*last);
            // Rinse and repeat.
            ++first;
        }
    }
    template<class BidirIt, class Pred>
    BidirIt unstable_remove_if(BidirIt first, BidirIt last, Pred predicate)
    {
        while (true) 
        {
            // Find the first instance of "value"...
            first = std::find_if(first, last, predicate);
            // ...and the last instance of "not value"...
            do 
            {
                if (first == last) 
                    return last;
                --last;
            } 
            while (predicate(*last));
            // ...and move the latter over top of the former.
            *first = std::move(*last);
            // Rinse and repeat.
            ++first;
        }
    }
} // namespace my

unstable_remove usage is the same as std::remove but their output is different.

// initializes a vector that holds the numbers from 0-9.
std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
print(v);

// removes all elements with the value 5
v.erase( my::unstable_remove( v.begin(), v.end(), 5 ), v.end() );
print(v);

// removes all odd numbers
v.erase( my::unstable_remove_if(v.begin(), v.end(), is_odd), v.end() );
print(v);

my::unstable_remove/my::unstable_remove_if Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 9 6 7 8
0 8 2 6 4

In his book, Arthur also noted:

For std::list container, std::list::erase can be much faster than the Erase-remove idiom on a std::list.

Special points of interest: This idiom can be used with std::unique where consecutive same values are moved to the back of the container. The erase–remove idiom cannot be used for containers that return const_iterator (for example, set). Another important note is erase–remove idiom can only be used with containers holding elements with full value semantics without incurring resource leaks, meaning raw pointer pointing to allocated memory should not be stored in the container, smart pointer is fine.

Reference

• Wikipedia Erase–remove idiom
• Effective STL by Scott Meyers
• Mastering the C++17 STL by Arthur O'Dwyer : unstable_remove featured here is from his book