Удаление элементов из конца вектора в C ++ с помощью итератора

Question

Удаление элементов из конца вектора в C ++ с помощью итератора

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

std::vector<int> data = ...
std::vector<int>::iterator iter;
for(iter = data.end() - 1; iter != data.begin() - 1; iter--) {
data.erase(iter);
}

Мой вопрос заключается в том, будет ли каждый из этих вызовов erase () быть O (1), так как мы удаляем в конце, даже если общая сложность удаления — O (n)? Кроме того, является ли этот код «безопасным», предполагая, что вектор имеет хотя бы 1 элемент?

3

c++invalidate iterator time-complexity vector

Решение

Другие решения

Если вы действительно необходимость чтобы удалить их в обратном порядке, вам лучше просто позвонить data.clear(),

В противном случае нет, это не «безопасно»: формирование data.begin() - 1 не определено, и уменьшается iter после того как ты позвонил .erase на это тоже не определено. Deduplicator опубликовал хорошее исправление для этого.

3

Своего рода. Сложность std :: vector erase () равна

Линейный по количеству стертых элементов (разрушений) плюс количество элементов после последнего удаленного элемента (перемещение).

На основании этого источника: http://www.cplusplus.com/reference/vector/vector/erase/

Поскольку вы удаляете только один элемент и его последний элемент, он является линейным с N = 1, что можно интерпретировать как O (1) константу.

0

Источник

Accepted Answer

Нет, ваш алгоритм имеет UB.
Если бы не было, у него было бы O (n).
Изменение тела на это приведет к удалению UB: iter = data.erase(iter);
Зачем? Так как vector.erase() ведет себя так:

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

Если переписать цикл следующим образом, он будет работать даже для пустого контейнера:

for(auto it = data.end(); it!=data.begin(); it = data.erase(it-1)) /**/;

Это равно:

std::remove_if(data.rbegin(), data.rend(), [](data::reference x){return true;});

Во всяком случае, используя data.clear(), data.resize(0) или обмен с временным пустым вектором, скорее всего, будет быстрее.

4