Откуда происходит увеличение производительности идиомы удаления-удаления?

Question

Мне нужно стереть все элементы из вектора, которые соответствуют определенным критериям.

Моим первым подходом было бы перебрать вектор и вызвать vector::erase для всех элементов, которые соответствуют критериям.

Насколько я понимаю, vector::erase имеет плохую производительность для этого варианта использования, потому что он удаляет элемент из базового массива и перемещает оставшуюся часть вектора вперед на один элемент (или больше, если вы удалите диапазон элементов). При удалении нескольких элементов задние элементы будут смещаться при каждом удалении.

remove Алгоритм берет все элементы, которые нужно удалить, и перемещает их в конец вектора, так что вам нужно только удалить ту заднюю часть вектора, которая не требует смещения.

Но почему это быстрее, чем стирать? (это еще быстрее?)

Не перемещает элемент до конца, подразумевает перемещение всех следующих элементов вперед, как в vector::erase?

Как получается, что удаление только имеет сложность O(n)?

Answer 1

Здесь проблема производительности заключается не в удалении элементов, которые должны быть удалены, или в перемещении их до конца (чего на самом деле не происходит), а в перемещении элементов, которые должны быть сохранены.

Если вы используете erase для каждого элемента, который вы хотите удалить, вам нужно переместить все элементы после них... для каждого вызова erase, Как правило, если вы хотите удалить k элементы, вы будете перемещать элементы после последнего (в векторе) k раз вместо одного.

Но если вы позвоните remove, вы будете перемещать их только один раз (см. пример ниже).

Небольшой пример, чтобы лучше понять, как работают эти два метода:

Допустим, у вас есть вектор размером 1000 и элементы, которые вы хотите удалить, находятся в позициях 17 и 37.

С erase действуя на два элемента, которые будут удалены:

• когда ты звонишь erase() для 17-го элемента вам нужно переместить элементы с 18 на 999, 982 элемента.
• когда ты звонишь erase() для 36-го элемента (сейчас это 36-й!) вам нужно переместить элементы с 37 на 998, 962 элемента.

В общей сложности вы переместили 962 + 982 = 1944 элементов, 962 из них были перемещены дважды за бесценок.

С removeпроисходит следующее:

element 0 does not change;
element 1 does not change;
...
element 17 is "discarded";
element 18 is moved at position 17;
element 19 is moved at position 18;
...
element 36 is moved at position 35;
element 37 is "discarded";
element 38 is moved at position 36;
...
element 999 is moved at position 997.

Всего вы переместили 998 элементов (1000 минус два удаленных элемента), что намного лучше, чем элементы 1943 года предыдущих методов. Это даже лучше, если вам нужно удалить более 2 элементов.

Вы можете взглянуть на возможную реализацию на en.cppreference.com, чтобы лучше понять, как std::remove работает.

Answer 2

Преимущество заключается в том, что std::remove не просто удаляет один элемент за раз. Например, если вызов std::remove в результате удаляются первые 10 элементов вашего вектора, он переместит 11-й элемент непосредственно в 1-ю позицию, 12-й элемент непосредственно во 2-ю позицию и т. д. Принимая во внимание, что если вы удалили первые 10 элементов по одному, это переместите каждый элемент после того, который вы удаляете обратно на 1. А затем вы удалите следующий элемент, каждый элемент должен быть перемещен снова. И это будет повторяться для каждого стертого элемента.

Кроме того, удаленные элементы не должны быть последовательными, чтобы это преимущество имело место. Например, если запрос на удаление приводит к удалению любого другого элемента, начиная с первого. Во-первых, 2-й элемент будет перемещен в 1-ю позицию, и это оставит зазор в два элемента до следующего сохраняемого элемента. Затем 4-й элемент будет перемещен непосредственно во 2-ю позицию, оставляя зазор в 3 элемента и так далее.

Также небольшая коррекция:

Алгоритм удаления берет все элементы, которые будут удалены, и перемещает их в конец вектора

Алгоритм удаления этого не делает. Неважно, что происходит с элементами, которые должны быть удалены. Они просто заменяются теми элементами, которые должны остаться. Значение элементов в конце после вызова remove не указано. Алгоритм, который вы описываете, является разделением (с обратной функцией сравнения).