How to efficiently remove elements from C++ associated containers

1. Introduction

The association container associates keys with values, including:

std::map, with unique keys;
std::multimap, there can be several identical keys;
std::unordered_map, hash map with unique keys;
std::unordered_multimap, there can be several hash maps of the same key.

The associated container also includes a collection (set）：

std::set, contains unique elements;
std::multiset, contains multiple equivalent elements;
std::unordered_set, hash set containing unique elements;
std::unordered_multiset, hash sets containing multiple hashings of the same elements.

Collections are contained in the association container because they can be considered as fusing keys and values into one element.

2. Remove elements from a given position

If you know the position of the associated container element through the iterator position, it is very easy to delete elements from the associated container. For example:

// Remove the entry from this location.(position);

// Remove all elements between the first (including) and the last (excluding).(first, last);

At this time, the iterator pointing to the deleted element fails, but all other iterators pointing to the container remain valid. This is the difference between the associated container.

3. Remove elements equivalent to specific key values

For the associated container, it is not talked about "equal to a specific key value", but "equal to a specific key value".

If you know the key value of the element you want to remove, the removal operation is very simple:

(myKey);

This will remove all key values frommyKeyEquivalent elements (formulticontainer).

Removes elements identified by values rather than key values: If you want to remove onemap(or itmultiOr hash the elements in the corresponding container) identified by the value rather than the key value, the operation is less intuitive.

All elements that meet certain conditions need to be removed, i.e. theirvalueEqual to a certain value.

4. Remove elements that meet specific conditions

4.1. Structural differences from sequence containers

To remove elements from a sequence container based on specific conditions, you can usestd::remove_if. But this cannot be done here.

In a sequence container, it is feasible to move the elements to be retained upwards, because their values are only arranged in order (this is the definition of the sequence container).

But associated containers have stronger constraints: they need to quickly find key values (for non-hash containers, time complexity is O(log(n)); for hash containers, time complexity is O(1)). To achieve this, they organize data in a more complex way, usually non-hash containers use trees, while hash containers use tables, where exact location is important.

Therefore, you cannot simply rearrange elements like std::remove_if, otherwise the internal structure will be damaged. So the interface must be followed. The interface provides the erase method seen above.

4.2. Follow the interface

The general idea of removing elements that meet certain conditions is to traverse the container, check the conditions for each element, and remove the returntrueelements. But the question is how to remove elements while traversing?

Consider a naive version of this traversal:

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

Note that this is a very rare case in which not much is known about iterators, only they are iterators. This is code that should never appear.

Take a look at this line of code in the example above:

(it);

This will makeitIneffective. Then watchforThe end position of the loop:

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

existitExecute immediately after failure++it. This results in undefined behavior.

4.3. Iterator operation

There is a need to find a way to increment the iterator before removing the element. For this, there are several options. In C++98, you can use the suffix increment operator, which will first increment the iterator and then pass a copy of the unincremented iterator toerase：

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

But the risk of operating iterators is also very high. In C++11, a less risky implementation is obtained becauseeraseReturns the iterator after the element is removed. You can rewrite the code in this way:

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

To ensure that this function is only used for associative containers, the C++ standard should have a related concept, but before that, various situations can be written 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 = (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);
}

5. Summary

Removes elements from a given position:useerase(position)orerase(first, last)Method, you can remove elements in a specified position or elements in a specified range.
Remove elements equivalent to a specific key value:useerase(myKey)Method, you can remove all key values andmyKeyEquivalent elements.
Remove elements that meet certain conditions:Due to the internal structure of the associated container, it cannot be used directly.std::remove_ifMethod removes elements that meet specific conditions. You need to use an iterator and manually traverse the container, check whether each element meets the conditions, and useeraseMethod removes elements that meet the conditions.

When removing elements, you need to pay attention to the issue of iterator failure and use the correct iterator operation to avoid undefined behavior.

This article also provideserase_ifImplementation of a function, which can be used to remove elements in an associated container that meet certain conditions. This function useseraseMethods and iterator operations are implemented and overloaded for different associated container types.

The above is the detailed content of how to efficiently remove elements in C++ associated containers. For more information on removing elements of C++ associated containers, please follow my other related articles!