How to Erase Elements from Stl Containers

How do I erase elements from STL containers?

Unfortunately, there isn't a single uniform interface or pattern for erasing elements from STL containers.
But three behaviors emerge:

std::vector Pattern

To erase elements that fulfill a certain condition from a std::vector, a common technique is the so called erase-remove idiom.

If v is an instance of std::vector, and we want to erase elements with value x from the vector, code like this can be used:

// Erase elements having value "x" from vector "v"
v.erase( std::remove(v.begin(), v.end(), x), v.end() );

If the criterion to be fulfilled for erasing elements is more complex than the simple "element to be erased == x", the std::remove_if() algorithm can be used instead of std::remove():

// Erase elements matching "erasing_condition" from vector "v"
v.erase( std::remove_if(v.begin(), v.end(), erasing_condition), v.end() );

where erasing_condition is a unary predicate, that can be expressed in several forms: e.g. it can be a bool-returning function taking vector element type as input (so if the returned value is true, the element will be erased from the vector; if it's false, it won't); or it can be expressed in-line as a lambda; it can be a functor; etc.

(Both std::remove() and std::remove_if() are generic algorithms from <algorithm> header.)

Here is a clear explanation from Wikipedia:

The algorithm library provides the remove and remove_if
algorithms for this. Because these algorithms operate on a range of
elements denoted by two forward iterators, they have no knowledge of
the underlying container or collection. Thus, no elements are actually
removed from the container. Rather, all elements which don't fit the
remove criteria are brought together to the front of the range, in the
same relative order. The remaining elements are left in a valid, but
unspecified state. When this is done, remove returns an iterator
pointing one past the last unremoved element.

To actually eliminate elements from the container, remove is combined
with the container's erase member function, hence the name
"erase-remove idiom".

Basically, std::remove() and std::remove_if() compact the elements that do not satisfy the erasing criteria to the front of the range (i.e. to the beginning of the vector), and then erase() actually eliminates the remaining elements from the container.

This pattern applies also to other containers like std::deque.

std::list Pattern

To erase elements from a std::list, simple remove() and remove_if() methods are available:

// Erase elements having value "x" from list "l"
l.remove( x )

// Erase elements satisfying "erasing_condition" from list "l"
l.remove_if( erasing_condition );

(Where erasing_condition is a unary predicate, with the same characteristics discussed for std::remove_if() in the above section.)

The same pattern can be applied to similar containers, like std::forward_list.

Associative Containers (e.g. std::map, std::set, ...) Pattern

Associative containers like std::map, std::set, std::unordered_map, etc. follow the common pattern described here:

If the erasing condition is a simple key-matching (i.e. "erase the element
having key x"), then a simple erase() method can be called:
```
// Erase element having key "k" from map "m":
m.erase( k );
```

If the erasing condition is more complex, and is expressed by some custom
unary predicate (e.g. "erase all odd elements"), then a for loop can be used
(with an explicit erasing condition checking in loop body, and call to erase(iterator) method):

//
// Erase all elements from associative container "c", satisfying "erasing_condition":
//
for (auto it = c.begin(); it != c.end(); /* "it" updated inside loop body */ )
{
    if ( erasing_condition(*it) )
    {   
        // Erase the element matching the specified condition 
        // from the associative container.
        it = c.erase(it);

        // Note:
        // erase() returns an iterator to the element 
        // that follows the last element removed, 
        // so we can continue the "for" loop iteration from that position.
    }
    else
    {
        // Current element does _not_ satisfy erasing condition,
        // so we can just move on to the next element.
        ++it;
    }       
}

The Need for a Unified Approach

As it can be noted from the above analysis, unfortunately there isn't a uniform common approach for erasing elements from STL containers.

The following table summarizes the aforementioned patterns:

----------------+------------------------------------------             
   Container    |            Erasing Pattern
----------------+------------------------------------------                
                |
 vector         |    Use erase-remove idiom.
 deque          |
                |
----------------+------------------------------------------               
                |
 list           |    Call remove()/remove_if() methods.
 forward_list   |
                |
----------------+------------------------------------------  
                |
 map            |    Simple erase(key) method call, 
 set            |    or 
 unordered_map  |    loop through the container,
 multimap       |    and call erase(iterator) on matching
                |    condition.
 ...            |
                |
----------------+------------------------------------------

Writing different specific code based on the particular container is error-prone, hard to maintain, hard to read, etc.

However, it's possible to write function templates with common names (e.g. erase() and erase_if()) overloaded for different container types, and embed the aforementioned pattern implementations in those functions.

So, the client can simply call those erase() and erase_if() generic functions, and the compiler will dispatch the call to proper implementation (at compile time), based on container type.

A more elegant approach, using a template meta-programming technique, is presented by Stephan T. Lavavej here.

Find and erase element from STL container while iterating

From cppreference on unordered_multimap::erase:

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

So I think that if you get an iterator to secondPair and secondPairIt != it then you can safely erase secondPairIt. You should also check that you are not invalidating the end of the range.

for (auto it = range.first; it != range.second;)
{
    if (condition)
    {
        auto secondPairIt = getSecondPairIt(it, myMultiMap); // Assume this is not end
        if (secondPairIt != it)
        {      
           if (secondPairIt == range.second)
               range.second = myMultiMap.erase(secondPairIt);
           else
               myMultiMap.erase(secondPairIt);
        }
        it = myMultiMap.erase(it);
    }
    else
    {
        ++it;
    }
}

How to remove from any container?

_Edit:

As noted by @pasbi, it seems that we already have std::experimental::erase_if, which does exactly that! It will be merged into std:: in C++20.

If you want a custom implementation, read ahead.

You don't have to specialize for specific containers. Instead, you can use type traits and SFINAE to determine container 'category'.

Is there a (commonly used) container which does not fit in either category?

I'd say yes. There are std::list and std::forward_list which have .remove_if() member function, which should be faster than erase-remove.

Thus, we have three possible implementations:

We use .remove_if() if it's available (as determined by std::experimental::is_detected).

This way we handle std::list and std::forward_list.

Otherwise, we use erase-remove if possible. (Which is possible if container elements are move-assignable, which can be tested with std::is_move_assignable.)

This way we handle all remaining standard containers except for std::[unordered_]map and std::[unordered_]set. (This is what you call vector-like containers.)

Otherwise we resort to a simple erasing loop over the elements.

This way we handle std::[unordered_]map and std::[unordered_]set.

Example implementation:

#include <algorithm>
#include <iterator>
#include <experimental/type_traits>
#include <utility>

inline auto dummy_predicate = [](auto &&){return false;};

template <typename T> using detect_member_remove_if =
    decltype(std::declval<T&>().remove_if(dummy_predicate));

template <typename T, typename F> void remove_if(T &container, F &&func)
{
    using element_t = std::remove_reference_t<decltype(*std::begin(container))>;

    if constexpr (std::experimental::is_detected_v<detect_member_remove_if, T>)
    {
        container.remove_if(std::forward<F>(func));
    }
    else if constexpr (std::is_move_assignable_v<element_t>)
    {
        auto new_end = std::remove_if(std::begin(container), std::end(container),
                                      std::forward<F>(func));
        container.erase(new_end, std::end(container));
    }
    else
    {
        auto it = std::begin(container);
        while (it != std::end(container))
        {
            if (func(*it))
                it = container.erase(it);
            else
                it++;
        }
    }
}

I'd prefer something without experimental

Here's a custom replacement for std::experimental::is_detected_v:

namespace impl
{
    template <typename ...P> struct void_impl {using type = void;};
    template <typename ...P> using void_t = typename void_impl<P...>::type;

    template <typename Dummy, template <typename...> typename A, typename ...B>
    struct is_detected : std::false_type {};

    template <template <typename...> typename A, typename ...B>
    struct is_detected<void_t<A<B...>>, A, B...> : std::true_type {};
}

template <template <typename...> typename A, typename ...B>
inline constexpr bool is_detected_v = impl::is_detected<void, A, B...>::value;

Note that we don't use C++17 std::void_t because, as far as I know, it still doesn't SFINAE correctly in Clang.

Iterating through STL containers and removing/adding multiple items

Use std::remove_if with a predicate that decide if a button needs to be removed:

bool needsRemoved(const Button& button);

vec.erase(std::remove_if(vec.begin(), vec.end(), &needsRemoved), vec.end());

EDIT: For your last example, the quadratic (i.e. bad for performance) algorithm is:

std::vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
auto end = vec.end();
for (auto it = vec.begin(); it < end; ++it)
{
    std::set<int> bad = {1, 4, 9};
    end = std::remove_if
        (vec.begin(), end,
         [bad](int x) { return (bad.find(x) != bad.end()); });
}
vec.erase(end, vec.end());

You will probably be better off using a container with fast lookup though (like a set, or a map).

How to remove elements by substrings from a STL container

What you need to do is first, iterate through the list and split up all the multi-word values into single words. If you're allowing Unicode, this means you will need something akin to ICU's BreakIterators, else you can go with a simple punctuation/whitespace split. When each string is split into it's constituent words, then use a hash map to keep a list of all the current words. When you reach a multi-word value, then you can check if it's words have already been found. This should be the simplest way to identify duplicates.

Removing something from a STL container without deconstructing it

If you have a container of pointers (which it sounds like you do since you are assigning NULL to "erased" elements), then erasing an element from the container does not delete the pointed-to object. You are responsible for doing that yourself.

If you have a container of objects (well, non-pointer objects), then you need to copy the element out of the container before you erase it.

Constant time removing element in an stl container

std::list has erase with complexity:

Complexity

1) Constant.

2) Linear in the distance between first and last.

where for case 2 you use erase for a range of elements.

from the docs, std::list<T>::erase looks like this:

//(1)
iterator erase( iterator pos );
iterator erase( const_iterator pos );
//(2)   
iterator erase( iterator first, iterator last );
iterator erase( const_iterator first, const_iterator last );

another one is std::forward_list (not exactly the same because it only has erase_after)

c++: Remove element from container and get it back

There is no built-in method to do this, you can however store the element by accessing it and then erase it.
Erasing requires you to specify key.If it's a multi-map you should erase with position.

What STL container to perform removal of elements in between?

I don't entirely follow your algorithm, but std::vector is required to provide amortized constant time push_back. It may also have better locality of reference when iterating.

If order doesn't matter, removal of any item is also a constant time operation:

template <typename T>
void remove(std::vector<T> &v, size_t i)
{
    std::swap(v[i], v.back());
    v.pop_back();
}