Сохранение действительного вектора :: iterator после erase ()

Question

РЕДАКТИРОВАТЬ: у меня было много ответов, говорящих мне, что я должен разделить удаление в другой цикл.Возможно, я не дал достаточно ясного объяснения, но в своем последнем абзаце я заявил, что хотел бы найти решение ДРУГОЕ, чем это.то есть, сохраняя текущую структуру кода, но используя какой-то малоизвестный фрейм C ++, чтобы он работал.

Хорошо, я знаю, что вызов erase() для вектора делает недействительными итераторы для элемента и всех тех, кто после негои что erase() возвращает итератор следующему действительному итератору, но что, если стирание произойдет в другом месте?

У меня следующая ситуация (упрощенно):

ПРЕДУПРЕЖДЕНИЕ: НЕ предполагайте, чтоэто весь кодТо, что показано ниже, ЧРЕЗВЫЧАЙНО упрощено, чтобы проиллюстрировать мою проблему.Все классы и методы, показанные ниже, на самом деле намного сложнее.

class Child {
   Parent *parent;
}

class Parent {
   vector<Child*> child;
}

void Parent::erase(Child* a) {
   // find an iterator, it, that points to Child* a
   child.erase(it);
}

int Child::update() {
   if(x()) parent.erase(*this) // Sometimes it will; sometimes (most) it won't
   return y;
}

void Parent::update() {
   int i = 0;
   for(vector<A>::iterator it = child.begin(); it != child.end(); it++)
      i += (*it)->update();
}

Таким образом, очевидно, что он потерпит крах после выполнения (*it)->update(), если x() вернет true, потому что когда это произойдет, Child будетпопросите Родителя удалить его из вектора, сделав недействительным итератор.

Есть ли способ исправить это, кроме как заставить Parent::erase() передать итератор полностью до Parent::update()?Это было бы проблематично, так как не вызывается для каждого вызова Child::update(), и, таким образом, этой функции потребуется способ возвращать итератор самому себе каждый раз, и она также в настоящее время возвращает другое значение.Я также предпочел бы избежать какого-либо другого аналогичного способа отделения процесса от цикла обновления.

Answer 1

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

Вы можете сделать это, изменив возвращаемое значение Child::update на что-то вроде std::pair<int, bool>, где int - это значение, а bool указывает, следует ли удалять этот элемент.

Если вы можете сделать Child::update метод const (то есть он не изменяет объект и вызывает только другие методы const), вы можете написать простой функтор, который вы можете использовать с std::remove_if. Примерно так:

class update_delete {
public:
    update_delete() : sum(0) {}
    bool operator()(const Child & child) {
        std::pair<int, bool> result = child.update();
        sum += result.first;
        return result.second;
    }
private:
    int sum;
}

Если вы не можете сделать update it const, просто поменяйте местами элемент с каким-то элементом со спины (вам нужно будет сохранить итератор, который всегда указывает на последний элемент, доступный для замены). Когда вы закончите агрегирование, просто отбросьте конец вектора (который теперь содержит все элементы, которые должны быть удалены), используя vector::resize. Это аналогично использованию std::remove_if, но я не уверен, возможно ли / допустимо ли использовать его с предикатом, который изменяет объекты в последовательности.

Answer 2

Вы не можете по-настоящему перебирать и мутировать одновременно std :: vector, если между итерацией нет какой-либо связи с мутацией.

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

Answer 3

Если вы можете передать как функцию стирания, так и идентификатор из функции обновления, то вы можете сделать это следующим образом:

int Child::update(bool& erase) {
   erase = x();
   return y;
}

void Parent::update() {
   int i = 0;

   for(vector<A>::iterator it = child.begin(); it != child.end();) {
      bool erase = false;
      i += (*it)->update(erase);

      if (erase) {
         it = child.erase(it); // erase returns next iterator
      } else {
         ++it;
      }
   }
}

Answer 4

Как насчет добавления дочерних элементов для удаления в список и удаления их после обновления каждого дочернего элемента.

По сути, вы будете откладывать удаление до окончания первого цикла.

Answer 5

Одной из основ решения (как уже говорили другие) является переключение с std :: vector на std :: list, поскольку вы можете затем удалить узлы из списка, не делая недействительными ссылки на другие узлы.

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

Что я сделал, то с некоторыми схожими требованиями, придерживался вектора, но разрешил дыры или «мертвые записи» в вашемвектор при удалении элементов.

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

Я опишу эту настройку более подробно в следующем сообщении в блоге: * http://upcoder.com/12/vector-hosted-lists/

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

Answer 6

Я не уверен во всех ваших ограничениях / целях проектирования, но вы можете указать на необходимость удаления дочернего элемента через его общедоступный API и просто заставить Parent::update условно выполнить удаление.

void Parent::update()
{
    int i = 0;
    for( vector<A>::iterator it = child.begin();
         it != child.end(); /* ++it done conditionally below */ )
    {
        i += (*it)->update();
        if( (*it)->should_erase() )
        {
            it = child.erase( it );
        }
        else
        {
            ++it;
        }
    }
}

bool Child::should_erase() const
{
    return x();
}

int Child::update()
{
    // Possibly do other work here.
    return y;
}

Тогда, возможно, вы можете удалить Parent::erase.

Answer 7

Мне кажется, проблема в том, что ваш метод "update" также делает недействительными итераторы точно так же, как это делает std :: vector :: erase. Поэтому я рекомендую вам сделать то же самое: вернуть новый действительный итератор и соответственно откорректировать вызывающий цикл.

Answer 8

попробуйте модифицированную версию ниже:

   for(vector<A>::iterator it = child.begin(); it != child.end();)
      i += (*it++)->update();

РЕДАКТИРОВАТЬ: Это, конечно, ужасно сломано, однако будет работать , если вы можете изменить контейнер на std::list. Без этого изменения вы можете попробовать обратный итератор (если порядок не имеет значения), т.е.

   for(vector<A>::reverse_iterator it = child.rbegin(); it != child.rend();)
      i += (*it++)->update();