如何删除 C++ 中的最后 n 个元素地图？

Question

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

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

其他解决方案之一是仅迭代 std::map 维护要删除的元素数量的计数器变量。这将给出O(n)。是否可以用STL算法替换for循环？

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

否则，您将必须维护单独的索引，或使用不同的容器。如果您不插入和删除太多元素，则类似排序向量之类的东西可能是合适的。

Answer 2

编辑：编辑原始帖子后答案不适用。