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

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

    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, программа вылетает с ошибкой утверждения... Кто-нибудь знает, что я делаю неправильно?

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

Ответ 1

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

for ( it = Entities.begin(); it != Entities.end(); )
   if( (*it)->getXPos() > 1.5f )
      delete * it;  
      it = Entities.erase(it);
   }
   else {
      ++it;
   }
}

Ответ 2

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

#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). Напротив, код Neil - это O (n ^ 2), так как поиск O (n) и удаление O (n).

Ответ 3

if((*it)->getXPos() > 1.5f)
{
   delete *it;
   it = Entities.erase(it);
}

Ответ 4

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

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

Ответ 5

Основная проблема заключается в том, что большинство итераторов контейнеров 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);
  }
}