在 O(1) 复杂度 C++ 中删除 vector<int> 的最后 n 个元素？
Remove last n elements of vector<int> in O(1) complexity C++?
我想以常数时间复杂度 O(1) 删除整数向量的最后 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.
的大小
如果您不想依赖编译器来执行此操作，另一种选择是存储您自己的单独大小变量，然后 "pretend" 您已从 std::vector 不再使用它们。这需要时间 O(1).
希望对您有所帮助！
我想以常数时间复杂度 O(1) 删除整数向量的最后 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.
如果您不想依赖编译器来执行此操作，另一种选择是存储您自己的单独大小变量，然后 "pretend" 您已从 std::vector 不再使用它们。这需要时间 O(1).
希望对您有所帮助！