Excluindo elementos de std :: set durante a iteração

147

Preciso passar por um conjunto e remover elementos que atendam a um critério predefinido.

Este é o código de teste que escrevi:

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

Inicialmente, pensei que apagar um elemento do conjunto ao iterá-lo invalidaria o iterador, e o incremento no loop for teria um comportamento indefinido. Mesmo assim, eu executei esse código de teste e tudo correu bem, e não sei explicar o porquê.

Minha pergunta: esse é o comportamento definido para conjuntos std ou essa implementação é específica? Estou usando o gcc 4.3.3 no ubuntu 10.04 (versão de 32 bits), a propósito.

Obrigado!

Solução proposta:

Essa é uma maneira correta de iterar e apagar elementos do conjunto?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

Edit: SOLUÇÃO PREFERIDA

Encontrei uma solução que me parece mais elegante, embora faça exatamente o mesmo.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

Se houver várias condições de teste durante esse período, cada uma delas deverá incrementar o iterador. Gosto mais desse código porque o iterador é incrementado apenas em um lugar , tornando o código menos propenso a erros e mais legível.

pedromanoel
fonte
1
Perguntado e respondido: stackoverflow.com/questions/263945/…
Martin York
3
Na verdade, li essa pergunta (e outras) antes de fazer a minha, mas como elas estavam relacionadas a outros contêineres da STL e como meu teste inicial aparentemente funcionou, achei que havia alguma diferença entre elas. Somente após a resposta de Matt pensei em usar o valgrind. Mesmo assim, prefiro minha NOVA solução que as outras, pois reduz as chances de erros aumentando o iterador em apenas um lugar. Obrigado a todos pela ajuda!
pedromanoel 6/07/10
1
O @pedromanoel ++itdeve ser um pouco mais eficiente do que it++porque não requer o uso de uma cópia temporária invisível do iterador. A versão da Kornel, embora mais longa, garante que os elementos não filtrados sejam iterados com mais eficiência.
Alnitak
@ Alnitak Eu não pensei nisso, mas acho que a diferença no desempenho não seria tão grande. A cópia também é criada em sua versão, mas apenas para os elementos correspondentes. Portanto, o grau de otimização depende totalmente da estrutura do conjunto. Por algum tempo, pré-otimizei o código, prejudicando a legibilidade e a velocidade de codificação no processo ... Então, eu realizava alguns testes antes de usar o outro caminho.
pedromanoel 22/10/12

Respostas:

178

Isso depende da implementação:

Norma 23.1.2.8:

Os membros de inserção não devem afetar a validade dos iteradores e referências ao contêiner, e os membros de exclusão devem invalidar apenas iteradores e referências aos elementos apagados.

Talvez você possa tentar isso - isso é padrão:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Observe que ++ é postfix, portanto, passa a posição antiga para apagar, mas primeiro salta para uma mais nova devido ao operador.

Atualização 10/10/2015: C ++ 11 resolveu o defeito. iterator erase (const_iterator position);retorne um iterador para o elemento que segue o último elemento removido (ou set::end, se o último elemento foi removido). Portanto, o estilo C ++ 11 é:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}
Kornel Kisielewicz
fonte
2
Isso não funciona deque no MSVC2013. A implementação deles é com erros ou ainda há outro requisito que impede que isso funcione deque. A especificação STL é tão complicada que você não pode esperar que todas as implementações a sigam, muito menos seu programador casual memorizá-la. O STL é um monstro além de domesticar, e como não há uma implementação exclusiva (e os conjuntos de testes, se houver) aparentemente não cobrem casos tão óbvios como a exclusão de elementos em um loop), que fazem do STL um brinquedo quebradiço brilhante que pode ser usado com um estrondo quando você olha de lado.
Kuroi neko
@MatthieuM. Faz no C ++ 11. No C ++ 17, é necessário o iterador (const_iterator no C ++ 11) agora.
tartaruga_casco_mole 23/01
18

Se você executar seu programa através do valgrind, verá vários erros de leitura. Em outras palavras, sim, os iteradores estão sendo invalidados, mas você está tendo sorte no seu exemplo (ou muito azar, pois não está vendo os efeitos negativos do comportamento indefinido). Uma solução para isso é criar um iterador temporário, aumentar a temperatura, excluir o iterador de destino e definir o destino para a temperatura. Por exemplo, reescreva seu loop da seguinte maneira:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 
Matt
fonte
Se é apenas uma condição que importa e não requer inicialização ou pós-operação no escopo, é melhor usar o whileloop. ou seja, for ( ; it != numbers.end(); )é melhor visível comwhile (it != numbers.end())
iammilind 28/04
7

Você entende mal o que significa "comportamento indefinido". Comportamento indefinido não significa "se você fizer isso, seu programa irá falhar ou produzir resultados inesperados." Significa "se você fizer isso, seu programa poderá travar ou produzir resultados inesperados" ou fazer qualquer outra coisa, dependendo do compilador, do sistema operacional, da fase da lua, etc.

Se algo for executado sem travar e se comportar como você espera, isso é não prova que não é um comportamento indefinido. Tudo o que prova é que seu comportamento foi o observado para essa execução específica após a compilação com esse compilador específico naquele sistema operacional específico.

A exclusão de um elemento de um conjunto invalida o iterador para o elemento apagado. O uso de um iterador invalidado é um comportamento indefinido. Aconteceu que o comportamento observado era o que você pretendia nesse caso em particular; isso não significa que o código está correto.

Tyler McHenry
fonte
Estou ciente de que um comportamento indefinido também pode significar "funciona para mim, mas não para todos". Foi por isso que fiz essa pergunta, porque não sabia se esse comportamento era correto ou não. Se fosse, então eu iria embora assim. Usar um loop while resolveria meu problema, então? Editei minha pergunta com minha solução proposta. Por favor, confira.
Pedromanoel 20/05/10
Funciona pra mim também. Mas quando eu mudo a condição para if (n > 2 && n < 7 ), obtenho 0 1 2 4 7 8 9. - O resultado específico aqui provavelmente depende mais dos detalhes de implementação do método erase e dos iteradores definidos, em vez da fase da lua (não aquela deve sempre confiar nos detalhes da implementação). ;)
UncleBens
1
O STL acrescenta muitos novos significados ao "comportamento indefinido". Por exemplo: "A Microsoft considerou inteligente aprimorar as especificações, permitindo std::set::eraseretornar um iterador, para que seu código MSVC funcione rapidamente quando compilado pelo gcc" ou "A Microsoft faz verificações vinculadas std::bitset::operator[]para que seu algoritmo de conjunto de bits cuidadosamente otimizado diminua para um rastrear quando compilado com o MSVC ". STL não tem nenhuma implementação único e sua especificação é uma bagunça inchado crescimento exponencial, por isso não admira exclusão de elementos de dentro de um loop exige conhecimentos sênior programador ...
kuroi neko
2

Apenas para avisar que, no caso de um contêiner deque, todas as soluções que verificam a igualdade do iterador de deque para numbers.end () provavelmente falharão no gcc 4.8.4. Ou seja, apagar um elemento do deque geralmente invalida o ponteiro para numbers.end ():

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Resultado:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

Observe que, embora a transformação de deque esteja correta nesse caso específico, o ponteiro final foi invalidado ao longo do caminho. Com o deque de um tamanho diferente, o erro é mais aparente:

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Resultado:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Aqui está uma das maneiras de corrigir isso:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}
McKryak
fonte
O ser chave do not trust an old remembered dq.end() value, always compare to a new call to dq.end().
Jesse Chisholm
2

O C ++ 20 terá "apagamento uniforme de contêiner" e você poderá escrever:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

E que irá trabalhar para vector, set, deque, etc. Veja cppReference para mais informações.

Marshall Clow
fonte
1

Esse comportamento é específico da implementação. Para garantir a correção do iterador, você deve usar "it = numbers.erase (it);" instrução se você precisar excluir o elemento e simplesmente iterador de incertezas em outro caso.

Vitaly Bogdanov
fonte
1
Set<T>::eraseversão não retorna o iterador.
Arkaitz Jimenez
4
Na verdade, sim, mas apenas na implementação do MSVC. Portanto, essa é realmente uma resposta específica da implementação. :)
Eugene
1
@Eugene Ele faz isso para todas as implementações com C ++ 11
Mašťov
Alguma implementação de gcc 4.8com c++1ytem um erro em apagar. it = collection.erase(it);é suposto para trabalhar, mas pode ser mais seguro usarcollection.erase(it++);
Jesse Chisholm
1

Eu acho que o uso do método STL ' remove_if' from poderia ajudar a evitar algum problema estranho ao tentar excluir o objeto envolvido pelo iterador.

Esta solução pode ser menos eficiente.

Digamos que temos algum tipo de contêiner, como vetor ou uma lista chamada m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

' it' é o iterador que ' remove_if' retorna, o terceiro argumento é uma função lambda que é executada em todos os elementos do contêiner. Como o contêiner contém Bullet::Ptr, a função lambda precisa obter esse tipo (ou uma referência a esse tipo) passado como argumento.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

' remove_if' remove o contêiner em que a função lambda retornou true e muda esse conteúdo para o início do contêiner. O ' it' aponta para um objeto indefinido que pode ser considerado lixo. Objetos de 'it' a m_bullets.end () podem ser apagados, pois ocupam memória, mas contêm lixo, portanto, o método 'erase' é chamado nesse intervalo.

John Behm
fonte
0

Me deparei com o mesmo problema antigo e encontrei abaixo o código mais compreensível, que é de certa forma as soluções acima.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}
Anurag
fonte
Isso só funciona se você sempre apagar todos os itens. O OP trata de apagar seletivamente os itens e ainda ter iteradores válidos.
Jesse Chisholm