Итерация карты C ++ с удалением - PullRequest
13 голосов
/ 15 апреля 2011

Я не смог найти пример того, как это сделать, поэтому я надеялся, что кто-нибудь сможет мне помочь. У меня есть карта, определенная в классе следующим образом:

std::map<std::string, TranslationFinished> translationEvents;

TranslationFinished - это повышение :: функция. У меня есть метод как часть моего класса, который перебирает эту карту, вызывая каждую из функций следующим образом:

void BaseSprite::DispatchTranslationEvents()
{
    for(auto it = translationEvents.begin(); it != translationEvents.end(); ++it)
    {
        it->second(this);
    }
}

Однако для функции, вызываемой it->second(this);, возможно удалить элемент из карты translationEvents (обычно самой), используя следующую функцию:

bool BaseSprite::RemoveTranslationEvent(const std::string &index)
{
    bool removed = false;
    auto it = translationEvents.find(index);
    if (it != translationEvents.end())
    {
        translationEvents.erase(it);
        removed = true;
    }
    return removed;
}

выполнение этого вызывает ошибку отладочного утверждения, когда DispatchTranslationEvents() пытается увеличить итератор. Есть ли способ безопасно перебрать карту с возможностью того, что вызов функции во время итерации может удалить элемент с карты?

Заранее спасибо

РЕДАКТИРОВАТЬ: случайно C / Pd неправильный код удаления события. Исправлено сейчас.

Ответы [ 7 ]

7 голосов
/ 15 апреля 2011

map::erase делает недействительным удаленный итератор (очевидно), но не остальную часть карты.Это означает, что:

  • если вы удаляете какой-либо элемент , отличный от текущего , то вы в безопасности, и
  • , если вы удаляете текущий элемент, высначала нужно получить итератор next , чтобы вы могли продолжить итерацию с этого (поэтому функция erase для большинства контейнеров возвращает итератор next ).std::map нет, поэтому вы должны сделать это вручную)

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

for(auto it = translationEvents.begin(); it != translationEvents.end();)
{
    auto next = it;
    ++next; // get the next element
    it->second(this); // process (and maybe delete) the current element
    it = next; // skip to the next element
}

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

6 голосов
/ 15 апреля 2011

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

4 голосов
/ 15 апреля 2011

Прочитав все остальные ответы, я нахожусь в преимуществе здесь ... Но здесь это идет.

Однако это возможно для функции, вызываемой it-> second (this); удалить элемент из карты translationEvents (обычно сам)

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

Удаление текущего обратного вызова

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

// [1] Let the callback actually remove itself
for ( iterator it = next = m.begin(); it != m.end(); it = next ) {
   ++next;
   it->second(this);
}
// [2] Have the callback tell us whether we should remove it
for ( iterator it = m.begin(); it != m.end(); ) {
   if ( !it->second(this) ) {                   // false means "remove me"
      m.erase( it++ );
   } else {
      ++it;
   }
}

Среди этих двух вариантов я бы явно предпочел [2], так как вы отделяете обратный вызов от реализации обработчика. То есть обратный вызов в [2] вообще ничего не знает о контейнере, в котором он содержится. [1] имеет более высокую связь (обратный вызов знает о контейнере), и его сложнее рассуждать, так как контейнер изменяется из нескольких мест в коде. Через некоторое время вы можете даже оглянуться на код, подумать, что это странный цикл (не помня, что обратный вызов удаляет себя), и преобразовать его в нечто более разумное как for ( auto it = m.begin(), end = m.end(); it != end; ++it ) it->second(this);

Удаление других обратных вызовов

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

void removeElement( std::string const & name ) {
   to_remove.push_back(name);
}
...
for ( iterator it = m.begin(); it != m.end(); ++it ) {
   it->second( this );       // callback will possibly add the element to remove
}
// actually remove
for ( auto it = to_remove.begin(); it != to_begin.end(); ++it ) {
   m.erase( *it );
}

Если удаление элементов должно быть немедленным (т.е. они не должны вызываться даже на этой итерации, если они еще не были вызваны), то вы можете изменить этот подход, проверив, отмечен ли он для удаления перед выполнением вызова. , Отметка может быть сделана двумя способами, универсальный из которых будет изменять тип значения в контейнере на pair<bool,T>, где bool указывает, является ли он живым или нет. Если, как и в этом случае, содержащийся объект можно изменить, вы можете просто сделать это:

void removeElement( std::string const & name ) {
   auto it = m.find( name );           // add error checking...
   it->second = TranslationFinished(); // empty functor
}
...
for ( auto it = m.begin(); it != m.end(); ++it ) {
   if ( !it->second.empty() )
      it->second(this);
}
for ( auto it = m.begin(); it != m.end(); ) { // [3]
   if ( it->second.empty() )
      m.erase( it++ );
   else
      ++it;
}

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

3 голосов
/ 15 апреля 2011

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

void BaseSprite::DispatchTranslationEvents()
{
    typedef std::map<std::string, TranslationFinished> container_t;

    container_t tempEvents;
    tempEvents.swap(translationEvents);

    for(auto it = tempEvents.begin(); it != tempEvents.end(); ++it)
    {
        if (true == it->second(this))
            translationEvents.insert(it);
    }
}

И функции TranslationFinished должны возвращать true, если они хотят быть сохраненными, и возвращать false, чтобы получитьудалены.

bool BaseSprite::RemoveTranslationEvent(const std::string &index)
{
    bool keep = false;
    return keep;
}
2 голосов
/ 15 апреля 2011

Вы можете отложить удаление до цикла отправки:

typedef boost::function< some stuff > TranslationFunc;

bool BaseSprite::RemoveTranslationEvent(const std::string &index)
{
    bool removed = false;
    auto it = translationEvents.find(index);
    if (it != translationEvents.end())
    {
        it->second = TranslationFunc(); // a null function indicates invalid event for later
        removed = true;
    }
    return removed;
}

защита от вызова недопустимого события в самом цикле и очистка любых «удаленных» событий:

void BaseSprite::DispatchTranslationEvents()
{
    for(auto it = translationEvents.begin(); it != translationEvents.end();)
    {
        // here we invoke the event if it exists
        if(!it->second.empty())
        {
            it->second(this);
        }

        // if the event reset itself in the map, then we can cleanup
        if(it->second.empty())
        {
            translationEvents.erase(it++); // post increment saves hassles
        }
        else
        {
            ++it;
        }
    }
}

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

это означает, что фактическое удаление этого события будет отложено до следующего запуска цикла диспетчеризации.

2 голосов
/ 15 апреля 2011

Должен быть способ стереть элемент во время итерации, возможно, немного сложнее.

for(auto it = translationEvents.begin(); it != translationEvents.end();)
{
    //remove the "erase" logic from second call
    it->second(this); 
    //do erase and increase the iterator here, NOTE: ++ action is very important
    translationEvents.erase(it++);         
}

Итератор будет недействительным после удаления элемента, поэтому вы не сможете использовать этот итераторделать больше действия после того, как вы удалите его.Однако удаление элемента не повлияет на другой элемент в реализации карты, IIRC.Таким образом, суффикс ++ сначала скопирует iter и сразу после этого увеличит итератор, а затем вернет значение копии, что означает увеличение итератора перед действием удаления, это должно быть безопасно для вас.

1 голос
/ 15 апреля 2011

Проблема в ++it после возможного удаления. Будет ли это работать для вас?

void BaseSprite::DispatchTranslationEvents()
{
    for(auto it = translationEvents.begin(), next = it;
        it != translationEvents.end(); it = next)
    {
        next=it;
        ++next;
        it->second(this);
    }
}
...