向量中擦除<n复杂度的元素

Question

我需要擦除排序向量中的元素，同时抑制等于或大于n的复杂度。我知道vector . erase方法会消除它，但它的复杂性是n。我可以用最后一个元素重写那个结构元素，然后使用回弹删除最后一个应该是常量的方法，但问题是它不会保持排序，所以我不得不重新排序。它甚至有可能解决这个问题并保持低于n的复杂度？

Answer 1

既然你需要它排序，std::vector（据我所知）没有解决方案。但是，std::vector似乎并不适合您的情况。 std::list是你的一个选择（可能会更好）。

从该参考文献：http://www.cplusplus.com/reference/list/list/erase/

复杂

线性在擦除元素的数量（破坏）。

这意味着它将调用析构函数N次，其中N是要删除的项目数。所以，它是删除项目的数量（不是std::list项目数量）线性关系

Answer 2

如果您必须保持您的数据结构排序，并能够从中间擦除元素（s）具有高性能，更好地用另一个容器替换vector（例如set，multiset）？