Удалить последние n элементов вектора <int>в O (1) сложности с ++?

Question

Я хочу удалить последние n элементов вектора целых чисел с постоянной временной сложностью O (1). Я думаю, это должно быть выполнимо, потому что для конечного указателя требуется только некоторая арифметика c. Тем не менее, стирание, изменение размера и удаление имеют сложность O (n). Какую функцию использовать?

Answer 1

Стандарт C ++ (я полагаю) говорит, что стоимость удаления k элементов из конца std::vector должна иметь временную сложность O (k), но это верхняя граница на сумму работа выполнена, а не нижняя граница.

Компилятор C ++ при генерации кода для std::vector<int>::erase может проверять типы и понимать, что при удалении int s нет необходимости выполнять какую-либо работу с отдельными элементами; он может просто отрегулировать логический размер std::vector и прекратить работу. Фактически, похоже, что g ++ с включенной оптимизацией делает именно это . Сгенерированная сборка здесь не включает никаких циклов и просто изменяет размер std::vector.

. Если вы не хотите полагаться на компилятор для этого, другим вариантом будет сохранение вашего собственного разделите переменную размера, а затем просто «сделайте вид», что вы удалили элементы из std::vector, никогда не используя их снова. На это нужно время O (1).

Надеюсь, это поможет!