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

Question

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

    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.

Answer 1

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

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

Answer 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). Код Нейла, приведенный выше, напротив, O (n ^ 2), поскольку поиск O (n), а удаление O (n).

Answer 3

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

Answer 4

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

Answer 5

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

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