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

Question

在 C++ std::map 中，是否有一种很好且简单的方法来查找 第 n 个元素？特别是我正在寻找一种算法来从 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

map 不提供比索引更好的线性访问元素，如 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 的东西可能是合适的。