在 O(1) 复杂度 C++ 中删除 vector<int> 的最后 n 个元素？

Question

我想以常数时间复杂度 O(1) 删除整数向量的最后 n 个元素。我认为这应该是可行的，因为只需要对结束指针进行一些算术运算。然而，擦除、调整大小和删除都具有 O(n) 复杂度。有什么功能可以使用？

Answer 1

C++ 标准（我相信）说从 a 的末尾删除 k 项的成本std::vector必须具有时间复杂度 O(k)，但这是完成工作量的上限，而不是下限。

C++ 编译器在为 生成代码时std::vector<int>::erase，可以检查类型并意识到删除ints时无需对每个元素进行任何工作；它可以只调整逻辑大小std::vector并收工。事实上，在启用优化的情况下，看起来 g++ 就是这样做的。这里生成的程序集不涉及任何循环，只是更改std::vector.

如果您不想依赖编译器来执行此操作，另一种选择是存储您自己的单独大小变量，然后只是“假装”您已从std::vector不再使用它们的情况下删除项目。这需要时间 O(1)。

希望这可以帮助！