我想以恒定时间复杂度 O(1) 删除整数 vector 的最后 n 个元素。我认为这应该是可行的，因为只需要对结束指针进行一些算术运算。但是，删除、调整大小和删除都具有 O(n) 复杂度。有什么功能可以使用？
最佳答案
C++ 标准(我相信)说从 std::vector 末尾删除 k 项的成本必须有时间复杂度 O(k)，但这是完成工作量的上限，而不是下限。
C++ 编译器，在为 std::vector<int>::erase 生成代码时，可以检查类型并意识到在删除 int 时不需要对每个元素进行任何操作小号；它可以调整std::vector的逻辑大小并收工。事实上，it looks like g++, with optimization turned on, does just that .这里生成的程序集不涉及任何循环，只是改变了std::vector的大小。 .
如果您不想依赖编译器来执行此操作，另一种选择是存储您自己的单独大小变量，然后只是“假装”您已从 std::vector 中删除项目。不再使用它们。这需要时间 O(1)。
希望这会有所帮助!
关于c++ - 在 O(1) 复杂度 C++ 中删除 vector<int> 的最后 n 个元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61623284/