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

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

Ответы

Ответ 1

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

std::vector

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

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

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

...

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

С++ 14 черновик N4140 [vector.modifiers] читает:

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

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

станд:: Deque

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

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

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

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

С++ 14 черновик N4140 [deque.modifiers]/5:

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

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

с помощью этого способа сложность времени = длина диапазона + длина сдвига (n - конец диапазона)

    vector<int> it = (vector<int>::iterator) &vec[pos];
    vec.erase(it, it+length);