I want to remove the last n elements of a vector of integers in constant time complexity O(1). This should be doable I think because only some arithmetic for the end pointer is needed. However, erase, resize, and remove all have O(n) complexity. What function is there to use?
1 Answers
The C++ standard (I believe) says that the cost of removing k items from the end of a std::vector must have time complexity O(k), but that's an upper bound on the amount of work done, not a lower bound.
The C++ compiler, when generating code for std::vector<int>::erase, can inspect the types and realize that there's no need to do any per-element work when removing ints; it can just adjust the logical size of the std::vector and call it a day. In fact, it looks like g++, with optimization turned on, does just that. The generated assembly here doesn't involve any loops and simply changes the size of the std::vector.
If you don't want to rely on the compiler to do this, another option would be to store your own separate size variable and then just "pretend" that you've removed items from the std::vector by never using them again. That takes time O(1).
Hope this helps!
Related