如何在C++ map中删除最后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循环？

- Leonid

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可能是适当的选择。

- Doug

---

为什么std::map没有提供一个O(log(n))的解决方案来访问第n个元素？ - undefined

在 k 次的情况下，移除 "end() - 1" 的做法将会更加高效。 - undefined

这听起来像是一个合理的解决方案，Stefan。 - undefined

@Leonid - 他们无法快速访问第N个元素，因为他们需要维护一个单独的索引，这将需要更多的内存，或者降低插入和删除的速度。 - undefined

@Stefan - 你为什么认为这样做会更快？从渐近意义上说，复杂度是相同的，如果你在一次擦除调用中将它们全部移除，可能需要更少的树重新平衡。 - undefined

@Doug - 对的，那很有道理。在树中，每个节点可以使用4个字节，但大多数情况下这是多余的，特别是当元素的大小与地图中的整数相似时。 - undefined

Answer 2

编辑：在原帖编辑后，答案不适用。

- Shamim Hafiz - MSFT

---

这正是我不想做的事情。 - undefined