Java Like Iterators

De ccppbrasil.org

Não gosto de muitas coisas em Java, mas o Iterator a la Java (1.4) pode-se dizer que é legal e fácil de ler, tanto é que a Trolltech adicionou este estilo Java de iterar na Qt4, para quem não conheçe é algo como:

Container::Iterator i = Container.iterator();
while (i.hasNext()) {
 cout << i.next() << endl;
}

Só que em Java Iterator é uma interface. O jeito Java de iterar é mais fácil de ler porém um pouco mais lento, se você for um daqueles maníacos que sequer usa métodos virtuais por achar lento, pode esquecer.

Implementação

A questão é, criar um iterador Java-like em uma coleção STL sem um overhead tão grande, a solução que fiz foi com templates, porém ainda não é perfeita:

template<typename Container>
class IteratorOverSTL {
 Container& mData;
 typename Container::iterator mI;
public:
 IteratorOverSTL(Container& c) : mData(c), mI(mData.begin()) {}
 bool hasNext() const {
  return mI != mData.end();
 }

 typename Container::value_type next() {
  return *(mI++);
 }
};

Exemplo de uso, suponha que você tenha uma classe Empresa que guarda uma coleção de instancias da classe Funcionario e você quer retornar um iterator para todos os funcionários da empresa.

class Empresa {
 typedef std::list<Funcionario> FuncList;
 FuncList mFuncionarios; // lista de funcionarios
public:
 typedef IteratorOverSTL<FuncList> Iterator;
 // retorna um iterator para a lista de funcionarios
 Iterator iterator() { return Iterator(mFuncionarios); };
};

Overhead

O overhead deste Iterator em relação ao uso de memória em comparação os iterators normais da STL é apenas uma referência a mais que é criada, o que não altera em nada... afinal o que são 4 bytes? ;-).

O problema maior esta no método next(), que utiliza pós-incremento ao invés de pré-incremento, isso faz diferença pois utilizando pós incremento eu tenho que criar uma cópia do iterator (o da STL), incrementar o iterator original e retornar a cópia, são mais alguns nano segundos perdidos.

Problemas

• Ele usa post-increment nos iterators, que é mais lento que o pre-increment para alguns iterators, já que o pos-increment cria uma cópia do iterator, faz a soma, e depois retorna a cópia criada, além disso alguns containers (como os da Qt) não possuem pos-increment.
• E se eu quiser um iterator const? Em algumas biliotecas (novamente a Qt é uma delas), iterar com um iterator const é mais rápido que com um iterator não const.
• Eu não fiz cache de mData.end(), em coleções muito grandes isso pode fazer diferença, pois tenho que criar uma cópia do iterator "end" a cada iteração do loop.

Sugestões é só falar.

--Hugo 12:25, 31 Março 2006 (CST)