How to Remove Elements from an Associative Container in C++

Published September 21, 2018 - 11 Comments

Welcome back for our second part in our series on removing elements from C++ containers!

How to Remove Elements from a Sequence Container (vector, string, deque, list)
How to Remove Pointers from a Vector in C++ (co-written with Gaurav Sehgal)
How to Remove Elements from an Associative Container (maps and sets)
How to Remove Duplicates from an Associative Container

Associative containers associate keys to values, and they include:

std::map, that has unique keys,
std::multimap, that can have several equivalent keys,
std::unordered_map, the hash map with unique keys,
std::unordered_multimap, the hash map that can have several equivalent keys.

By extension, the associative containers also include sets:

std::set, that has unique elements,
std::multiset that can have several equivalent elements,
std::unordered_set, the hash set with unique elements,
std::unordered_multiset, the hash set that can have several equivalent elements.

Sets are included in associative containers because they can be seen as melting keys and values into one element.

We will answer the same 4 questions as in part one on sequence containers:

How to remove the elements at a given position (or between two given positions),
How to remove the elements equivalent to a certain value,
How to remove the elements satisfying a certain predicate,
How to remove the duplicates (this one is hairy enough to deserve its own article).

remove mltimap map set multiset

Removing the elements at a given position

As for sequence containers, removing elements from an associative container is a walk in the park if you know its position with an iterator position. If a is of any of the 8 associative containers:

a.erase(position);

removes the entry at that position.

And:

a.erase(first, last);

removes all the entries between first (included) and last (not included).

Of course, the iterators pointing to the removed elements gets invalidated, but all other iterators to the container remain valid. This is a difference with sequence containers.

Removing the elements equivalent to a certain key

Note that for associative containers we don’t talk about “equal to a certain key” but rather “equivalent to a certain key”. If you’re not familiar with it, this subtle difference is explained in details in Custom comparison, equality and equivalence with the STL.

If you have the key of the entry you want to remove from an associative container, it’s easy as pie:

a.erase(myKey);

Note that this removes all the entries whose key is equivalent to myKey (for the multi containers).

However, if you want to remove the elements of a map (or of its multi- of hash- counterparts) identified by their value and not their key, it’s not as straightforward.

For this you need to remove the elements satisfying the predicate of having their value equal to something. Which leads us to the next section:

Removing the elements that satisfy a predicate

A structural difference with sequence containers

To remove elements from an sequence container according to a predicate, we used std::remove_if. We can’t do the same thing here.

Indeed, pulling up the elements to be kept was OK in a sequence container, where the values are simply lined up one after the other (by definition of a sequence container).

But associative container have stronger constraints: they have to find keys pretty fast (in O(log(n)) for non-hash and O(1) for hash). And to achieve this, they structure the data in more complex ways, typically in a tree for non-hash containers, and in a table where exact positions matter, for hash containers.

So we can’t just shuffle the elements like std::remove_if does, otherwise we would break the internal structure. So we have to play along with the interface. And what we get in the interface is the erase method that we’ve seen above.

Playing along with the interface

The general idea to remove elements according to a predicate is to iterate over the container, check the predicate on each element and remove those that return true. But the problem is, how to iterate and remove elements at the same time?

Indeed, consider the naive version of such an iteration:

template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
    for (auto it = begin(container); it != end(container); ++it)
    {
        if (shouldRemove(*it))
        {
            container.erase(it);
        }
    }
}

Note that this is one of the very rare cases where we don’t know more about the iterators than that they are iterators. In other cases, I consider it to be one of the 7 names we should never see in code.

Anyway, consider line 8:

container.erase(it);

This has the effect of invalidating it. Then look at the end of line 4:

for (auto it = begin(container); it != end(container); ++it)

We do ++it right after it has been invalidated. This causes undefined behaviour.

Juggling with iterators

We need to find a way to increment the iterator before erasing it. For this we have several options. In C++98 we can use the post-fix increment operator that will first increment the iterator and then pass a copy of the non-incremented iterator to erase:

template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
    for (auto it = begin(container); it != end(container); /* nothing here, the increment in dealt with inside the loop */ )
    {
        if (shouldRemove(*it))
        {
            container.erase(it++);
        }
        else
        {
            ++it;
        }
    }
}

But juggling with iterators is not much less dangerous than juggling with knives. Or with torches. In C++11 we get a less risky implementation because erase returns the iterator following the removed elements. We can then rewrite the code this way:

template<typename AssociativeContainer, typename Predicate>
void erase_if(AssociativeContainer& container, Predicate shouldRemove)
{
    for (auto it = begin(container); it != end(container); /* nothing here, the increment in dealt with inside the loop */ )
    {
        if (shouldRemove(*it))
        {
            it = container.erase(it);
        }
        else
        {
            ++it;
        }
    }
}

To make sure that this function is only used with associative containers, I suppose we will be able to use a concept when they’re out (in C++20, as it seems) but in the meantime we can just write the various cases explicitly:

namespace details
{
    template<typename AssociativeContainer, typename Predicate>
    void erase_if_impl(AssociativeContainer& container, Predicate shouldRemove)
    {
        for (auto it = begin(container); it != end(container); /* nothing here, the increment in dealt with inside the loop */ )
        {
            if (shouldRemove(*it))
            {
                it = container.erase(it);
            }
            else
            {
                ++it;
            }
        }
    }
}

template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::map<Key, Value, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::multimap<Key, Value, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::unordered_map<Key, Value, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Value, typename Comparator, typename Predicate>
void erase_if(std::unordered_multimap<Key, Value, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::set<Key, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::multiset<Key, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::unordered_set<Key, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

template<typename Key, typename Comparator, typename Predicate>
void erase_if(std::unordered_multiset<Key, Comparator>& container, Predicate shouldRemove)
{
    return details::erase_if_impl(container, shouldRemove);
}

This type of generic function has been proposed by Stephan T. Lavavej for the C++ standard. The proposal hasn’t made it in C++17 though. Perhaps it will be accepted along with the Ranges proposal.

Removing duplicates from an associative container

Next up in our series about removing stuff from containers in C++ we’ll see how to remove duplicates from associative containers. It’s a hairy topic, but one that gives a chance to get a more in-depth understanding of STL containers.

Stay tuned, and see you there!