Iteradores não são constantes

Um bug que já encontrei uma dúzia de vezes entre os novatos da STL é a utilização de iteradores como se eles não fossem mudar nunca. Porém, a verdade é bem diferente: iteradores se tornam inválidos sim, e com muito mais freqüência do que normalmente se imagina. Entre as situações em que iteradores podem mudar estão as seguintes:

• Inserção de novo elemento no contêiner
• Remoção de novo elemento no contêiner
• Redimensionamento no tamanho do contêiner

Por exemplo, o tradicional código do exemplo abaixo contém o tradicional erro de iterador inválido:

for( container::iterator it = obj.begin(); it != obj.end(); ++it )
{
  if( it->member == 0 ) // condição para apagar elemento
  {
    obj.erase(it);  // a partir daqui it é inválido,
                    // e não adianta incrementá-lo
  }
}

Para operações como essa, o retorno geralmente nos dá uma dica de para onde vamos na varredura do contêiner. No caso do método erase, o retorno é o próximo iterador válido, ou o final (retornado pelo método end). Um código mais esperto gera um erro mais sutil:

for( container::iterator it = obj.begin(); it != obj.end(); ++it )
{
  if( it->member == 0 ) // condição para apagar elemento
  {
    it = obj.erase(it); // ótimo, atualizou it. só
                        // que se ele for o final,
                        // será incrementado
  }
}

Algo de errado irá acontecer se o elemento removido for o último localizado no contêiner. Porém, mesmo que não for, um item será pulado durante a iteração, pois o iterador apontando para o próximo elemento será incrementado antes de passar pelo loop.

Esse é um erro comum para os acostumados com outros tipos de iteração (ex: ponteiros) e que não estudaram os princípios básicos da STL, entre eles o da reutilização de algoritmos. Se fosse usado este princípio, nada disso teria acontecido:

struct remove_if_zero
{
  bool operator() (ObjElement& element)
  {
    return element->member == 0;
  }
};

obj.remove_if( remove_if_zero() ); // pronto!

Quando precisamos fazer algo nos elementos de um contêiner STL, é quase certo que existirá um algoritmo genérico para essa tarefa, seja no próprio contêiner ou na forma de função (`<algorithm>`). Nunca se esqueça disso na hora de desenvolver seus próprios algoritmos e não precisará reinventar a roda todos os dias.

// Comments

2008-04-18 Luiz Salamon:

Recentemente coloquei um post na lista CCPPBRASIL sobre um problema que tive recentemente. Na verdade resolvi com o uso de sincronicação, mas gostaria de sua sugestão, pois penso que deveria existir uma forma mais simples de resolver o problema.

Reproduzindo o texto:

Partindo do código abaixo, que simplifica a situação real onde o problema se apresentou, tenho um problema que resolvi por sincronização, pois o sistema é multithread.

map map_test;
map::iterator iter_map_test;

map_test [ "AAAAA" ] = "11111";
map_test [ "BBBBB" ] = "22222";
map_test [ "CCCCC" ] = "33333";

// iterator esta apontando para uma posição válida
iter_map_test = map_test.find ("BBBBB");

// neste ponto o iterator deixa de ser válido
map_test.erase ("BBBBB");

A questão é como faço para verificar se o iterator iter_map_test é válido ? Pois qualquer operação que tento a partir do momento que o mesmo fica inválido causa uma exceção.

2008-03-06 Thiago R Adams:

Uma curiosidade é que o map não retorna o iterator no erase.

Mas a implementação da STL que vem no VC++ retorna. Tive este problema uma vez quando fui compilar um código no gcc. Eu não imaginava que isso não era padrão.

Mas vendo a documentação da msdn tem uma nota:

"This return type does not conform to the C++ standard."

A solução sem usar o retorno é:

if (condition)
  map.erase(it++);
else
  ++it;

2008-04-22 Caloni:

Olá, Luiz.

As respostas da lista de discussão foram ótimas, e de fato não há muito o que fazer (2026-03-23 exceto talvez o comentário do Thiago acima). Considere um iterador um ponteiro que não aponta mais para nada válido. Nesse caso, não há como você validá-lo.

[]s

2008-03-23 Caloni:

Olá, Thiago.

Mais um problema com a compatibilidade do Visual Studio. Desse jeito foi começar a usar o GCC para meus testes.

Valeu o aviso!

[]s