Удаление элемента из вектора, в то время как в C ++ 11 диапазон «для» цикла?

У меня есть вектор IInventory *, и я перебираю список, используя диапазон C ++ 11 для того, чтобы что-то делать с каждым.

После того, как вы поработаете с ним, я могу удалить его из списка и удалить объект. Я знаю, что могу позвонитьdelete на указатель в любое время, чтобы очистить его, но как правильно удалить его из вектора, находясь в диапазонеfor цикл? И если я удалю его из списка, мой цикл станет недействительным?

<code>std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

for (IInventory* index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
}
</code>
 Ben Voigt28 апр. 2012 г., 06:11
@ TomJ: Это все равно испортит итерацию.
 bobobobo30 апр. 2013 г., 17:53
@BenVoigt Я рекомендовал перейти наstd::list ниже
 Ivan28 апр. 2012 г., 09:28
@TomJ и это будет убийство производительности - при каждом стирании вы можете перемещать все элементы после стертого.
 TomJ28 апр. 2012 г., 06:06
Есть ли причина, по которой вы не можете просто добавить счетчик индекса, а затем использовать что-то вроде inv.erase (index)?
 Benjamin Lindley28 апр. 2012 г., 06:06
Если вы хотите стать модным, вы можете использоватьstd::remove_if с предикатом, который "делает вещи" и затем возвращает true, если вы хотите удалить элемент.

Ответы на вопрос(10)

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

Цикл for, основанный на диапазоне, является просто синтаксическим сахаром для слова "нормальный". цикл с использованием итераторов, поэтому вышеизложенное применимо.

При этом, вы можете просто:

inv.erase(
    std::remove_if(
        inv.begin(),
        inv.end(),
        [](IInventory* element) -> bool {
            // Do "some stuff", then return true if element should be removed.
            return true;
        }
    ),
    inv.end()
);
 04 мая 2013 г., 09:26
@bobobobo Если по «циклу на основе итераторов» quot; ты имеешь в видуSeth Carnegie's answer, то есть O (n ^ 2) в среднем.std::remove_if является O (n).
 04 мая 2013 г., 03:33
Это не выглядит проще, чем цикл на основе итератора, кроме того, вы должны помнить, чтобы окружатьremove_if с.eraseиначе ничего не происходит.
 28 апр. 2012 г., 06:40
& Quot;because there is a possibility that vector reallocated the block of memory in which it keeps its elements& Quot; Нетvector никогда не будет перераспределять из-за вызоваerase, Причина, по которой итераторы становятся недействительными, заключается в том, что каждый из элементов, следующих за удаляемым элементом, перемещается.
 28 апр. 2012 г., 07:00
@ildjarn Я исправлюсь, сэр!
 29 апр. 2012 г., 01:17
Захват по умолчанию[&] было бы целесообразно, чтобы он мог "делать некоторые вещи"; с локальными переменными.

Хорошо, я опоздал, но все равно: Извините, не правильно то, что я прочитал до сих пор - этоis возможно, вам просто нужно два итератора:

std::vector<IInventory*>::iterator current = inv.begin();
for (IInventory* index : inv)
{
    if(/* ... */)
    {
        delete index;
    }
    else
    {
        *current++ = index;
    }
}
inv.erase(current, inv.end());

Простое изменение значения, на которое указывает итератор, не лишает законной силы любой другой итератор, поэтому мы можем сделать это без беспокойства. На самом деле,std::remove_if (по крайней мере, реализация gcc) делает что-то очень похожее (используя классический цикл ...), просто ничего не удаляет и не стирает.

Имейте в виду, однако, что это не потокобезопасно (!) - однако, это относится и к некоторым другим решениям выше ...

 10 нояб. 2017 г., 16:50
Какого черта. Это перебор.
 13 нояб. 2017 г., 00:23
@ Кессе Правда? Это наиболее эффективный алгоритм, который вы можете использовать с векторами (не имеет значения, является ли цикл на основе диапазона или классический цикл итератора): таким образом, вы перемещаете каждый элемент в векторе не более одного раза и итерируете по всему вектору ровно один раз. Сколько раз вы будете перемещать последующие элементы и выполнять итерацию по вектору, если удаляете каждый соответствующий элемент с помощьюerase (конечно, если вы удалите более одного элемента)?

Гораздо более элегантным решением было бы перейти наstd::list (при условии, что вам не нужен быстрый произвольный доступ).

list<Widget*> widgets ; // create and use this..

Затем вы можете удалить с.remove_if и функтор C ++ в одну строку:

widgets.remove_if( []( Widget*w ){ return w->isExpired() ; } ) ;

Итак, я просто пишу функтор, который принимает один аргумент (Widget*). Возвращаемое значение является условием для удаленияWidget* из списка.

Я нахожу этот синтаксис приемлемым. Я не думаю, что когда-либо буду использоватьremove_if заСТД :: векторы - так многоinv.begin() а такжеinv.end() шум, который вам, вероятно, лучше использоватьудаление на основе целочисленного индекса или просто обычное обычное удаление на основе итераторов (как показано ниже). Но вы не должны быть удалены из серединыstd::vector все равно очень много, так что переход наlist для этого случая частого удаления середины списка рекомендуется.

Обратите внимание, однако я не получил возможность позвонитьdelete наWidget*которые были удалены. Для этого это будет выглядеть так:

widgets.remove_if( []( Widget*w ){
  bool exp = w->isExpired() ;
  if( exp )  delete w ;       // delete the widget if it was expired
  return exp ;                // remove from widgets list if it was expired
} ) ;

Вы также можете использовать обычный цикл на основе итераторов, например:

//                                                              NO INCREMENT v
for( list<Widget*>::iterator iter = widgets.begin() ; iter != widgets.end() ; )
{
  if( (*iter)->isExpired() )
  {
    delete( *iter ) ;
    iter = widgets.erase( iter ) ; // _advances_ iter, so this loop is not infinite
  }
  else
    ++iter ;
}

Если вам не нравится длинаfor( list<Widget*>::iterator iter = widgets.begin() ; ..., ты можешь использовать

for( auto iter = widgets.begin() ; ...
 30 апр. 2013 г., 21:57
Это не имеет значения. Удаление из серединыstd::vector всегда будет скользить каждый элемент после того, как вы удалили один, делаяstd::list гораздо лучший выбор.
 30 апр. 2013 г., 22:18
Тогда у вас есть отличный ответ в поисках вопроса.This question говорит об итерации списка, который является O (N) для обоих контейнеров. И удаление O (N) элементов, что также O (N) для обоих контейнеров.
 05 мая 2013 г., 02:10
Предварительная маркировка не требуется; вполне возможно сделать это за один проход. Вам просто нужно отслеживать & quot; следующий элемент для проверки & quot; и "следующий слот для заполнения". Думайте об этом как о создании копии списка, отфильтрованного по предикату. Если предикат возвращает true, пропустите элемент, в противном случае скопируйте его. Но копирование списка производится на месте, и вместо копирования используется замена / перемещение.
 30 апр. 2013 г., 22:00
Нет, он не будет "сдвигать каждый элемент вверх на один".remove_if будет скользить каждый элемент вверх на количество свободных мест. К тому времени, когда вы учитываете использование кэша,remove_if наstd::vector вероятно, превосходит удаление изstd::list, И консервыO(1) произвольный доступ
 30 апр. 2013 г., 21:16
Я не думаю, что вы понимаете, какremove_if наstd::vector на самом деле работает, и как это сохраняет сложность O (N).
Решение Вопроса

Нет, вы не можете & t. Диапазон на основеfor для того, когда вам нужно получить доступ к каждому элементу контейнера один раз.

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

Например:

auto i = std::begin(inv);

while (i != std::end(inv)) {
    // Do some stuff
    if (blah)
        i = inv.erase(i);
    else
        ++i;
}
 28 апр. 2012 г., 06:06
Не удастся ли здесь применить идиотизм к удалению?
 16 сент. 2014 г., 16:17
@Kolyunya Нет, это нормально, потому что он не хранит конечный итератор.
 30 апр. 2013 г., 21:18
Не нравится это решение, оно O (N ^ 2) для большинства контейнеров.remove_if лучше.
 29 апр. 2012 г., 01:13
@SethCarnegie Erase-remove с помощью лямбды для предиката элегантно позволяет это (так как это уже C ++ 11)
 28 апр. 2012 г., 06:07
@ Навин Я решил не пытаться сделать это, потому что, очевидно, ему нужно перебирать каждый элемент, делать с ним вычисления, а затемpossibly удалите это из контейнера. Erase-remove говорит о том, что вы просто стираете элементы, для которых возвращается предикатtrue, AFAIU, и, кажется, лучше не смешивать итерационную логику с предикатом.

извините за некропост, а также извините, если мой опыт с ++ помешает моему ответу, но если вы пытаетесь перебирать каждый элемент и вносить возможные изменения (например, стирание индекса), попробуйте использовать обратные слова для цикла.

for(int x=vector.getsize(); x>0; x--){

//do stuff
//erase index x

}

при удалении индекса x следующий цикл будет для элемента "перед" последняя итерация. я действительно надеюсь, что это помогло кому-то

 25 мая 2017 г., 22:27
просто не забывайте при использовании x для доступа к определенному индексу, сделайте x-1 lol

В идеале вы не должны изменять вектор, повторяя его. Используйте идиому удаления-удаления. Если вы это сделаете, вы, вероятно, столкнетесь с несколькими проблемами. Так как вvector erase делает недействительными все итераторы, начиная с элемента, удаляемого доend() вам нужно убедиться, что ваши итераторы остаются действительными, используя:

for (MyVector::iterator b = v.begin(); b != v.end();) { 
    if (foo) {
       b = v.erase( b ); // reseat iterator to a valid value post-erase
    else {
       ++b;
    }
}

Обратите внимание, что вам нужноb != v.end() проверить как есть. Если вы попытаетесь оптимизировать его следующим образом:

for (MyVector::iterator b = v.begin(), e = v.end(); b != e;)

вы столкнетесь с UB, так как вашe признан недействительным после первогоerase вызов.

 28 апр. 2012 г., 06:40
@ildjarn: Да, правда! Это была опечатка.
 29 апр. 2012 г., 05:34
@Potatoswatter: Конечно нет. Я пытался указать на проблемы с удалением во время итерации. Полагаю, моя формулировка не прошла проверку?
 29 апр. 2012 г., 01:15
Это не идиома удаления-удаления. Там нет вызоваstd::removeи это O (N ^ 2), а не O (N).

Я покажу на примере, приведенный ниже пример удаления нечетных элементов из вектора:

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};

    //method 1
    for(auto it = vecInt.begin();it != vecInt.end();){
        if(*it % 2){// remove all the odds
            it = vecInt.erase(it);
        } else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 2
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 2
    for(auto it=std::begin(vecInt);it!=std::end(vecInt);){
        if (*it % 2){
            it = vecInt.erase(it);
        }else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 3
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 3
    vecInt.erase(std::remove_if(vecInt.begin(), vecInt.end(),
                 [](const int a){return a % 2;}),
                 vecInt.end());

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

}

вывод aw ниже:

024
024
024

Имейте в виду, методerase вернет следующий итератор переданного итератора.

ОтВотмы можем использовать более генерируемый метод:

template<class Container, class F>
void erase_where(Container& c, F&& f)
{
    c.erase(std::remove_if(c.begin(), c.end(),std::forward<F>(f)),
            c.end());
}

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};
    //method 4
    auto is_odd = [](int x){return x % 2;};
    erase_where(vecInt, is_odd);

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;    
}

Смотрите здесь, чтобы увидеть, как использоватьstd::remove_if. https://en.cppreference.com/w/cpp/algorithm/remove

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

std::vector<IInventory*> inv;
inv.push_back( new Foo() );
inv.push_back( new Bar() );

for ( IInventory* &index : inv )
{
    // do some stuff
    // ok I decided I need to remove this object from inv...?
    if (do_delete_index)
    {
        delete index;
        index = NULL;
    }
}
std::remove(inv.begin(), inv.end(), NULL);

В отличие от этого заголовка темы, я бы использовал два прохода:

#include <algorithm>
#include <vector>

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

std::vector<IInventory*> toDelete;

for (IInventory* index : inv)
{
    // Do some stuff
    if (deleteConditionTrue)
    {
        toDelete.push_back(index);
    }
}

for (IInventory* index : toDelete)
{
    inv.erase(std::remove(inv.begin(), inv.end(), index), inv.end());
}

Я думаю, что сделал бы следующее ...

for (auto itr = inv.begin(); itr != inv.end();)
{
   // Do some stuff
   if (OK, I decided I need to remove this object from 'inv')
      itr = inv.erase(itr);
   else
      ++itr;
}

Ваш ответ на вопрос