2

Подскажите, как корректно пройтись по вектору и удалить некоторые его элементы.
Т.е., корректно ли выполнять такие действия?

for (auto it = arr.begin(); it != arr.end(); it++)
{
    if (check(*it) == false)
        arr.erase(it);
}

Или возникнут проблемы с итератором после удаления первого элемента?


Прочитал комментарии, всем спасибо за помощь

Пересмотрел код и понял, что не совсем полно поставил задачу:

for (auto it = arr.begin(); it != arr.end(); it++)
{
    if (check(*it) == false)
    {
        // сделать-что-то полезное с данными, которые потом будут удалены

        arr.erase(it);
    }
}

Если воспользоваться советом @Harry, то тогда код можно же преобразовать к такому:

arr.erase(remove_if(arr.begin(), arr.end(), [](auto x) {
    if (check(x))
    {
        // сделать что-то полезное с данными из x

        return true;
    }

    return false; 
}), arr.end());

?

4 ответа 4

3

А почему не так:

arr.erase(remove_if(arr.begin(),arr.end(),
                    [](auto x){ return !check(x); }),
          arr.end());

? Как по мне - понятнее и никаких проблем с итераторами... Вероятно, еще и быстрее, чем убирать по одному элементу...

Если перепишете check так, чтоб работал наоборот - то и лямбда-выражение (или bind) не потребуется.

Если уж позарез нужен цикл - то воспользуйтесь тем, что erase возвращает итератор на элемент, следующий за удаленным:

for(auto i = arr.begin(); i != arr.end();
    i = (check(*i) == false) ? arr.erase(i) : i+1);

Но учтите, что тут сложность - квадратичная, в отличие от remove_if (спасибо @pavel).

7
  • способы действительно хорошие, просто тогда мне придется сделать двойной проход по массиву, сначала для удаления неугодных элементов, а потом для работы с угодными элементами (у меня в реализации), но это совершенно несмертельно, так что наверное так и реализую, как ты советуешь
    – Zhihar
    18 фев 2019 в 11:21
  • "Если перепишете check так, чтоб работал наоборот - то и лямбда-выражение (или bind) не потребуется." - вот это не очень понял, что имеется в виду?
    – Zhihar
    18 фев 2019 в 11:21
  • Вы проверяете и удаляете при check(*it) == false. Если будете удалять при newcheck(*it) == true, то лямбда-0выражение не потребуется, просто передадите третьим параметром newcheck.
    – Harry
    18 фев 2019 в 12:10
  • вот цикл как раз в таком виде я бы писать не советовал. Квадратичная сложность на ровном месте.
    – pavel
    18 фев 2019 в 13:48
  • @pavel А он для вектора в любом виде при удалении по одному элементу будет квадратичный :) Впрочем, remove_if - тоже, из-за перемещения неудаленных.
    – Harry
    18 фев 2019 в 14:27
2

erase вернёт следующий итератор, элемент будет удалён, но будет проблема с инкрементом, так что нужно добавить вспомогательный код.

for (auto it = arr.begin(); it != arr.end(); it++)
{
    if (check(*it) == false){
       it = arr.erase(it);
       --it;
    }
}
1

Итератор после удаления станет не валидным и it++ сделать будет нельзя. К тому же, на каждую итерацию будет перестроение вектора, что в общем случаем считается тяжелой операцией. Можно перенести все правильные значения в новый вектор:

decltype(arr) new_vector;
new_vector.reserve(arr.size());
for (auto i = 0; i < arr.size(); ++i)
{
    new_vector.emplace_back(std::move(arrr[i]));
}
arr.swap(new_vector)
1

Альтернатива ответу @Komodosh.

Чтобы не декрементировать итератор лишний раз, можно сделать так:

auto it = arr.begin();
while (it != arr.end())
{
    if (check(*it) == false)
        it = arr.erase(it);
    else
        it++;
}

Но лучше послушать Harry и взять erase-remove idiom.

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.