Временная сложность std :: vector :: erase на начальном элементе вектора

Question

Посмотрев на то, как работает vector.erase, я не уверен, что сложность времени выполнения std :: vector :: erase для первого элемента вектора.Будет ли это постоянное время?

Answer 1

С [vector.modifiers] (выделено):

стирание итератора (позиция const_iterator);
стирание итератора (сначала const_iterator, последний const_iterator);

[...]

Сложность: деструктор T называется числом раз, равным количеству стертых элементов, но оператор присваивания T называется числомраз равное количеству элементов в векторе после стертых элементов .

Следовательно, когда вы стираете первый элемент, вы получаете один вызов деструктора и присваивания size() - 1, чтолинейная сложность по времени.