Erase first N items from a std::map?

Question

Trying to write a method which deletes the first (lowest-keyed) N items from an std::map. Tried this:

void EraseNMapElements(const int numElementsToRemove){

    const int originalSize = _map.size();     
    auto eraseIter = _map.begin();
    std::advance(eraseIter, numElementsToRemove);

    _map.erase(_map.begin(), eraseIter);

    assert(_map.size() == (originalSize - numElementsToRemove)) || (0 == originalSize) || (0 == _map.size()));
}

It works when the number of elements is more than the number requested to be removed. So if I had five elements, request to delete 2, the last 3 element remain. However, if I have one element and request to erase 2, I still have one element remaining.

Is there a neat way to cover this? I could shove an IF statement around checking for numElementsToRemove greater than map.size() but there must be a better solution?

Answer 1

std::advance(i, n) has a precondition that i can be incremented at least n times. In your code, you're not checking that precondition, so if you call it with numElementsToRemove > originalSize, you're violating that precondition and thus experiencing Undefined Behaviour. To fix that, you must do the check before calling std::advance, perhaps using std::min:

auto realNumToRemove = std::min(numElementsToRemove, originalSize);
std::advance(eraseIter, realNumToRemove);

Answer 2

An if statement provides a simple, readable solution:

if (originalSize <= numElementsToRemove) {
    auto eraseIter = _map.begin();
    std::advance(eraseIter, numElementsToRemove);

    _map.erase(_map.begin(), eraseIter);
} else {
    _map.clear(); // or whatever's appropriate
}

Answer 3

The simplest way I can see to do this would be to use std::next and a if statement.

void EraseNMapElements(const int numElementsToRemove)
{
    if (_map.size() < numElementsToRemove)
        _map.erase(_map.begin(), std::next(_map.begin(), numElementsToRemove));
    else
        _map.clear();
}

Do note though that _map.size() < numElementsToRemove has a sign/unsigned mismatch. Preferably numElementsToRemove should be a std::size_t or decltype(_map)::size_type.

Answer 4

One thing that has not been mentioned yet and that is good to know is that since C++11 std::map::erase(const_iterator) actually returns an iterator to the following element. So the code could also be written as:

auto i = _map.begin();
while (i != _map.end() && numElementsToRemove > 0)
{
     i = _map.erase(i);
     --numElementsToRemove;
}

This will traverse the elements to erase once instead of twice.