История изменений

Сложность удаления значения из вектора по значению - O(N), не больше, потому что требований сохранения порядка элементов не прозвучало. А раз не прозвучало, значит я не должен сдвигать всё что стояло после удалённого и значит разрешается переместить на место удалённого кого-то другого.

Поэтому мы делаем так:

1. За O(N) ищем элемент, который следует удалить.
2. За O(1) меняем его местами с последним, а про последний тупо забываем (size -= 1)

Ежели задать вопрос «не отсортированы ли они часом» и получить на него «да», тогда O(N) в пункте 1 заменяется на O(log2(N)).

Сложность удаления значения из вектора по значению - O(N), не больше, потому что требований сохранения порядка элементов не прозвучало. А раз не прозвучало, значит я не должен сдвигать всё что стояло после удалённого и значит разрешается переместить на место удалённого кого-то другого.

Поэтому мы делаем так:

1. За O(N) ищем элемент, который следует удалить.
2. За O(1) меняем его местами с последним, а про последний тупо забываем (size -= 1)

Ежели задать вопрос «не отсортированы ли они часом» и получить на него «да», тогда O(N) в пункте 1 заменяется на log2(N).

Сложность удаления значения из вектора по значению - O(N), не больше, потому что требований сохранения порядка элементов не прозвучало. А раз не прозвучало, значит я не должен сдвигать всё что стояло после удалённого и значит разрешается переместить на место удалённого кого-то другого.

Поэтому мы делаем так:

1. За O(N) ищем элемент, который следует удалить.
2. За O(1) меняем его местами с последним, а про последний тупо забываем (size -= 1)