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

有没有一个很好的和简单的方法来找到nth element在C++std::map？特别是我正在寻找一种算法来清除map中的最后一个k元素。这将是有意义的检索迭代器到nth element和呼叫std::map::erase。要求是复杂度不会受到影响 - 应该可以擦除O(N)中的元素范围。如何擦除C++映射中的最后n个元素？

不应仅仅为了擦除元素而复制数据。例如，一种解决方案是将数据复制到std::vector中，然后在std::vector上执行std::nth_element，然后在std::map::find上查找迭代器以便找出从哪里擦除。

其他解决方案之一是迭代std::map维护一个计数器变量的要删除的元素数量。那会给O(n)。有可能用STL algorithm替换for循环吗？

来源

2010-09-20 Leonid

地图不提供按索引优于线性访问元素，如vector或deque。您可以使用std::advance来做到这一点，但需要的时间与k成正比。如果k很小，它通常会足够快 - 它基本上涉及以下k指针。这里有一个例子：

或者，如果你使用升压，您可以使用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可能是合适的。

来源

2010-09-20 11:05:43 Doug

为什么'std :: map'没有提供一个'O（log（n））'解决方案来访问第n个元素？ – Leonid 2010-09-20 11:08:58

删除“end（） - 1”应该更有效。 – 2010-09-20 11:11:07

这听起来像是一个合理的解决方案斯蒂芬。 – Leonid 2010-09-20 11:11:49

编辑：回复原始帖子编辑后不适用。

来源

2010-09-20 11:02:32

这正是我不想做的事情。 – Leonid 2010-09-20 11:09:16

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

回答

相关问题