Временная сложность удаления элементов в векторах и Деке

Я читал, что временная сложность добавления элементов в конец std::vector является амортизируемой константой, а вставка элементов в верхней и нижней части std::deque является постоянной.Поскольку оба эти контейнера имеют итератор произвольного доступа, то доступ к элементам в любом индексе является постоянным. Пожалуйста, дайте мне знать, если у меня есть какие-либо из этих фактов wrong.My вопрос в том, если доступ к элементу в std::vector или std::deque постоянен, то почему временная сложность удаления элемента через erase O(n). Один из ответов здесь здесь говорится, что удаление элементов через erase-Это O(n). Я знаю, что erase удаляет элементы между начальными итераторами и конечным, поэтому ответ в основном означает, что его O(n) зависит от количества элементов между двумя итераторами и что удаление одного элемента из вектора / deque в любом индексе будет равно нулю?

3 11
c++ vector deque

3 ответа:

Вещи немного отличаются для std::vector и std::deque, а также они отличаются для C++98 и C++11.

Std:: vector

Сложность

Линейна как по длине стираемого диапазона, так и по количеству элементов между концом диапазона и концом контейнера (поэтому стирание элемента из конца занимает постоянное время).

C++2003 [lib.vector.modifiers] читает: 

iterator erase(iterator position);
iterator erase(iterator first, iterator last);`

...

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

C++14 проект N4140 [vector.modifiers] гласит:

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

Таким образом, вы видите, что реализация C++11/14 в целом более эффективна, поскольку она выполняет назначение перемещения вместо назначения копирования, но сложность остается прежней.

Std:: deque

Сложность std::deque::erase() линейна как к длине стираемого диапазона, так и к минимуму из двух чисел: количество оставшихся элементов до начала диапазона, и количество оставшихся элементов после окончания диапазона. Таким образом, стирание элемента либо с начала, либо с конца занимает постоянное время.

C++2003 [lib.deque.modifiers]:

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

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

C++14 проект N4140 [deque.modifiers]/5:

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

Таким образом, это то же самое в C++98 и C++11/14, опять же, за исключением того, что C++11 может выбирать между назначением перемещения и назначением копирования (здесь я вижу некоторое несоответствие в стандарте, потому что формулировка не упоминает назначение перемещения, как для std::vector - может быть причиной для другого вопроса).

Обратите также внимание на "самое большее "и" не более " в формулировках. Это позволяет реализациям быть более эффективными, чем линейные, хотя на практике они линейны (DEMO ).
7

Стирание элемента в векторе равно O (n), так как после удаления элемента вам все равно нужно переместить все последующие элементы, чтобы заполнить образовавшийся пробел. Если вектор имеет n элементов, то в худшем случае вам нужно будет сдвинуть n-1 элемент, следовательно, сложность равна O(n).

4

Удаление элементов действительно O(n) не из-за того, что вы должны сделать, чтобы найти элемент для удаления, а из-за того, что вы должны сделать со всеми из нихпосле . Эти элементы должны быть сдвинуты вниз, чтобы заполнить пустое место.

Таким образом, в среднем стирание займет элемент примерно на полпути через вектор, так что вам придется сдвинуть примерно половину элементов. Отсюда O(n). В лучшем случае, вы стираете последний элемент-никакого скольжения не требуется. В худшем случае вы сотрете первый элемент-придется чтобы затем переместить каждый другой элемент.

3