Click here to Skip to main content
13,737,943 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

7.7K views
50 downloads
8 bookmarked
Posted 27 Jan 2018
Licenced CPOL

Erase-remove Idiom Revisited

, 27 Jan 2018
Rate this:
Please Sign up or sign in to vote.
Always use Erase-remove Idiom to erase vector elements

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Shao Voon Wong
Software Developer (Senior)
Singapore Singapore
Right now, I am picking up DevOps skills at Pluralsight and pursuing CCNA certification. Stay tuned for my CCNA related article!

Coding Tidbit Blog

Latest blogpost: C++ – The Forgotten Trojan Horse by Eric Johnson

IT Certifications

  • IT Infrastructure Library Foundational (ITIL v3)
  • Scrum Alliance Certified Scrum Master (CSM)
  • Certified Secure Software Lifecycle Professional (CSSLP)

View my certificates here.

You may also be interested in...

Comments and Discussions

 
Suggestionlooks like we're missing a function erase_if() Pin
Stefan_Lang31-Jan-18 21:02
memberStefan_Lang31-Jan-18 21:02 
GeneralRe: looks like we're missing a function erase_if() Pin
Shao Voon Wong6-Feb-18 2:37
professionalShao Voon Wong6-Feb-18 2:37 
QuestionMessage Closed Pin
28-Jan-18 22:36
member28-Jan-18 22:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web04-2016 | 2.8.180920.1 | Last Updated 28 Jan 2018
Article Copyright 2018 by Shao Voon Wong
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid