从std::map中删除前N个条目？

Question

尝试编写一个方法，从std::map中删除前N个（键最小的）项。尝试了以下代码：

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()));
}

当元素数量大于要删除的数量时，它可以正常工作。所以如果我有5个元素，并要求删除2个，则最后3个元素将保留。但是，如果我只有一个元素并请求删除2个，则仍然会保留一个元素。

有没有一种简洁的方法来解决这个问题？我可以在周围添加一个IF语句，检查numElementsToRemove是否大于map.size()，但肯定有更好的解决方案吧？

- user997112

---

为什么会有比最直接的解决方案更好的解决方案？ - Benjamin Lindley

Answer 1

std::advance(i, n) 有一个前提条件，即 i 至少可以被递增 n 次。在你的代码中，你没有检查这个前提条件，因此如果你用 numElementsToRemove > originalSize 调用它，你会违反这个前提条件，从而经历“未定义行为”。为了修复这个问题，在调用 std::advance 之前，您必须进行检查，可能使用 std::min：

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

- Angew is no longer proud of SO

Answer 2

一个if语句提供了一个简单易读的解决方案：

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

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

- Paul Evans

Answer 3

还有一个尚未提及但值得注意的事情是，自从C++11以来，std::map::erase(const_iterator)实际上会返回指向下一个元素的迭代器。因此，代码也可以编写为：

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

这将遍历元素一次，而不是两次来擦除。

- thep

---

同时，多元素的“erase”操作很可能被优化，以大幅减少所需的平衡操作数量，与逐个删除相比。一如既往：在考虑性能时，请进行测量。 - Angew is no longer proud of SO

Answer 4

我认为最简单的方法是使用 std::next 和一个 if 语句来实现。

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

请注意，_map.size() < numElementsToRemove 存在符号/无符号不匹配的问题。最好将 numElementsToRemove 定义为 std::size_t 或者 decltype(_map)::size_type。

- NathanOliver