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