Virtual Iterators

De ccppbrasil.org

Tabela de conteúdo 1 Introdução 2 Uso 3 Código 4 Exemplo final 5 Conclusão

Introdução

Algumas vezes temos um programa que se utiliza de uma grande quantidade de repetições. Por exemplo, um mesmo estilo de loop.
Nestes casos, diminuir a quantidade de código e especializar o algorítmo pode tornar mais fácil a manutenção e deixar o código livre de erros do tipo "copiar e colar".
Seguindo as idéias do artigo Java Like Iterators, darei uma segunda alternativa. Nesta, o que difere do iterator mostrado no artigo anterior é que neste caso ele é indiferente ao container utilizado.

Uso

O get retorna ao elemento atual apontado pelo iterator e next retorna true se existe um próximo elemento movendo em seguida o iterator para ele.

    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);

    v_iterator<int> it(vec);
    while(it.next())
    {
        cout << it.get() << endl;
    }

Note que o tipo de container, no caso vector, não precisou ser informado para o tipo de iterator. A mesma declaração poderia ser usada numa lista.

    list<int> lst;
    lst.push_back(1);
    lst.push_back(2);
    v_iterator<int> it(vec);
    ...

O método reset coloca o iterator na posição inválida ou equivalente a uma posição antes da begin. Não é a mesma posição do end e o iterator é inválido neste estado até que seja dado o próximo next. Este é estado após a contrução do objeto.

Código

template<class T>
struct virtual_iterator
{
    virtual void start() = 0;
    virtual bool end() const = 0;
    virtual void next() = 0;
    virtual const T & get() const = 0;
    virtual virtual_iterator * clone() const = 0;
    virtual ~virtual_iterator() {}
};

template<class T>
class virtual_iterator_imp : public virtual_iterator< typename T::value_type >
{
    const typename T::const_iterator m_begin;
    const typename T::const_iterator m_end;
          typename T::const_iterator m_it;
 
    void start() { m_it = m_begin;  }

    void next()  { ++m_it; }

    bool end() const { return m_it != m_end; }

    typename const T::value_type & get() const { return *m_it; }

    virtual_iterator_imp * clone() const { return new virtual_iterator_imp(*this); }

    bool operator == (const virtual_iterator_imp &); //not imp
    bool operator != (const virtual_iterator_imp &); //not imp

public:
    virtual_iterator_imp(const T & container) :
        m_begin(container.begin()),
        m_end(container.end()),
        m_it()       
    {
    }
    
    virtual_iterator_imp(const virtual_iterator_imp & it) :
        m_begin(it.m_begin),
        m_end(it.m_end),
        m_it(it.m_it)       
    {
    }

     virtual_iterator_imp & operator = (const virtual_iterator_imp & it)
     {
        m_begin =it.m_begin;
        m_end =it.end;
        m_it = it.m_it;       
      return *this;
    }
};


template<class T>
class v_iterator
{
    virtual_iterator<T> * m_pIt;    
    bool m_first;

public:

    template<class ContainerType>
      v_iterator(const ContainerType & container) : 
      m_first(true), 
      m_pIt(new virtual_iterator_imp<ContainerType>(container))
    {
    }

    v_iterator() : m_first(true), m_pIt(0)
    {
    }

    v_iterator(const v_iterator &it) : 
      m_first(it.m_first), 
      m_pIt(it.m_pIt->clone())
    {
    }

    void swap(v_iterator &it)
    {
        std::swap(it.m_first, m_first);
        std::swap(it.m_pIt, m_pIt);
    }

    ~v_iterator() { delete m_pIt;  }
    void reset() {  m_first = true;  }
   
    template<class ContainerType>
    void reset(const ContainerType & container)
    {
       virtual_iterator<T> * temp = new virtual_iterator_imp<ContainerType>(container);
       m_first = true;
       delete m_pIt;
       m_pIt = temp;
    }

    v_iterator& operator =(const v_iterator & it)
    {
      v_iterator temp(it);
      swap(temp);
      return *this;
    }

    bool next()
    {
        if (!m_pIt)
            return false;

        if (m_first)
        {
           m_pIt->start();
           m_first = false;
        }
        else
        {
           m_pIt->next();
        }

        return m_pIt->end();
    }

    const T & get() const
    {
        return m_pIt->get();
    }

    const T & operator *() const
    {
        return get();
    }
};

Exemplo final

using namespace std;

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);

    list<int> lst;
    lst.push_back(3);
    lst.push_back(4);

    v_iterator<int> it(vec);
    while(it.next())
    {
        cout << it.get() << endl;
    }

    it.reset();
    while(it.next())
    {
        cout << it.get() << endl;
    }

    it.reset(lst);
    while(it.next())
    {
        cout << *it << endl;
    }

    it.reset();
    if (it.next())
    {
      v_iterator<int> it2(it);
      cout << *it2;
      v_iterator<int> it3;
      it3 = it2;
      cout << *it3;
    }
}

Conclusão

Apesar do nome "iterator", esta classe não chega a ser um iterator completo que possa ser usado nos algorítmos da STL. Caso fosse desejado poderia ser transformado em um iterator compatível exigindo mais detalhes de implementação. Mas isto não vem ao caso. A performance deste iterator virtual é abaixo de um iterator definido em tempo de compilação. Existem dois cenários em que ele poderia ser usado:

• Economia de código quando a performance é irrelevante e quando existe muita repetição de algorítmo.
• Nos casos em que a característica polimórfica do iterator seja importante. Por exemplo, se precisa ser definido um mesmo algorítimo para enumeração do COM ou container da STL (enumeração do COM, é definida com interfaces).

Observação: O código mostrado foi criado para o artigo e pode conter erros, este código não foi testado em um programa real e se destina apenas como exemplo.

---

Thiago R. Adams, 18/04/06

Veja também:
Java Like Iterators
Templates