Как стереть и удалить указатели на объекты, хранящиеся в векторе?

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

    vector<Entity*> Entities;
    /* Fill vector here */
    vector<Entity*>::iterator it;
    for(it=Entities.begin(); it!=Entities.end(); it++)
        if((*it)->getXPos() > 1.5f)
            Entities.erase(it);

Когда какой-либо из объектов Entity достигает xPos>1.5, программа вылетает с ошибкой утверждения... Кто-нибудь знает, что я делаю неправильно?

Я использую VC++ 2008.

Источник

5 ответов

Решение

Вы должны быть осторожны, потому что erase() сделает недействительными существующие итераторы. Однако ir возвращает новый действительный итератор, который вы можете использовать:

for ( it = Entities.begin(); it != Entities.end(); )
   if( (*it)->getXPos() > 1.5f )
      delete * it;  
      it = Entities.erase(it);
   }
   else {
      ++it;
   }
}
Источник

"Правильный" способ сделать это - использовать алгоритм:

#include <algorithm>
#include <functional>

// this is a function object to delete a pointer matching our criteria.
struct entity_deleter
{
    void operator()(Entity*& e) // important to take pointer by reference!
    { 
        if (e->GetXPos() > 1.5f)
        {
            delete e;
            e = NULL;
        }
}

// now, apply entity_deleter to each element, remove the elements that were deleted,
// and erase them from the vector
for_each(Entities.begin(), Entities.end(), entity_deleter());
vector<Entity*>::iterator new_end = remove(Entities.begin(), Entities.end(), static_cast<Entity*>(NULL));
Entities.erase(new_end, Entities.end());

Теперь я знаю, о чем ты думаешь. Вы думаете, что некоторые другие ответы короче. Но, (1) этот метод обычно компилируется в более быстрый код - попробуйте сравнить его, (2) это "правильный" способ STL, (3) меньше шансов для глупых ошибок, и (4) легче читать После того, как вы можете прочитать код STL. Стоит изучать программирование на STL, и я предлагаю вам ознакомиться с замечательной книгой Скотта Майера "Эффективный STL", в которой есть множество советов по STL по этому виду вещей.

Другим важным моментом является то, что, не стирая элементы до конца операции, элементы не нужно перетасовывать. GMan предлагал использовать список, чтобы избежать этого, но при использовании этого метода вся операция - O(n). Код Нила, приведенный выше, напротив, O(n^2), поскольку поиск O (n), а удаление O(n).

Источник 
if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}
Источник

Основная проблема заключается в том, что большинство итераторов контейнера stl не поддерживают добавление или удаление элементов в контейнере. Некоторые сделают недействительными все итераторы, некоторые сделают недействительными только те итераторы, которые указывают на удаляемый элемент. Пока вы не почувствуете, как работает каждый из контейнеров, вам нужно будет внимательно прочитать документацию о том, что вы можете и что не можете делать с контейнером.

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

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

vector<Entity*> Entities;
/* Fill vector here */
vector<Entity*>::iterator it;
for(it=Entities.end(); it!=Entities.begin(); ){
  --it;
  if(*(*it) > 1.5f){
   delete *it;
   it=Entities.erase(it);
  }
}
Источник

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

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

Источник
Другие вопросы по тегам