如何擦除C++映射中的最后n个元素？

Question

是否有一个很好的和简单的方式找到nth element的C++ std::map？特别是我正在寻找一种算法来擦除最后的k元素map.检索nth element和调用迭代器是有意义的std::map::erase.要求是复杂性不会受到影响 - 应该可以擦除元素范围O(N).

不应仅仅为了擦除元素而复制数据.例如,一个解决方案是将数据复制到std::vector,然后做std::nth_element的std::vector,然后std::map::find找迭代器,以找出从抹去.

其他解决方案之一是迭代std::map维护要移除的元素数量的计数器变量.这会给O(n).是否可以for用STL algorithm？替换循环？

Answer 1

地图不能通过索引提供比元素更好的线性访问,例如vector或deque.您可以使用std::advance,但需要时间与之成比例k.如果k很小,它通常会足够快 - 它基本上包括跟随k指针.这是一个例子:

template<typename Map>
void erase_last_elements(Map & map, ptrdiff_t k)
{
    assert(k >= 0);
    assert(map.size() >= (size_t)k);
    typename Map::iterator i = map.end();
    std::advance(i, -k);
    map.erase(i, map.end());
}

或者,如果您使用的是Boost,则可以使用boost::prior:

template<typename Map>
void erase_last_elements(Map & map, ptrdiff_t k)
{
    assert(k >= 0);
    assert(map.size() >= (size_t)k);
    typename Map::iterator i = boost::prior(map.end(), k);
    map.erase(i, map.end());
}

否则,您必须维护单独的索引,或使用其他容器.vector如果您不插入和删除元素太多,那么类似于排序可能是合适的.