Какова временная сложность операции удаления элемента в контейнере vector?

В контейнере std::vector операция удаления элемента (например, с помощью erase) имеет временную сложность O(n) в худшем случае, где n — количество элементов в векторе.

Причина в том, что после удаления элемента все последующие элементы сдвигаются влево, чтобы заполнить освободившееся место. Этот сдвиг требует копирования или перемещения элементов.

Пример:

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // Удаляет элемент '3'
// Элементы '4' и '5' сдвигаются на одну позицию влево

Таким образом, удаление элемента в середине или начале вектора — операция линейной сложности.