Iteradores em C++ – 5 tipos de iteradores

Você provavelmente já deve ter usado iteradores em C++, seja direta ou indiretamente. Você também deve tê-lo feito sem saber que existem diferentes tipos de iteradores, e que cada um deles (com exceção dos dois mais simples) é uma “evolução” do tipo anterior. Logo, para que mais pessoas saibam que existam diferentes tipos de iteradores em C++, e quais eles são, decidi escrever este artigo para falar deste assunto um tanto quanto negligenciado.

Os 5 tipos de iteradores em C++ são os seguintes:

• Entrada
• Saída
• Avanço
• Bidirecionais
• Acesso aleatório

Como foi dito acima, os iteradores de uma categoria são “evoluções” da categoria anterior, o que significa, por exemplo, que os iteradores de avanço, por exemplo, possuem todas as funcionalidades dos operadores de entrada e saída (que pertencem a um mesmo nível na “hierarquia” dos iteradores) e algumas a mais. Do mesmo modo, os operadores bidirecionais possuem tudo aquilo que os de avanço têm, e algumas coisas a mais – e assim por diante. Vejamos, então, quais são as diferenças entre cada um dos tipos de iteradores.

Tipos de iteradores em C++ – Entrada

Os iteradores de entrada constituem (junto com os iteradores de saída) a categoria mais básica dos iteradores em C++. Eles permitem ler os valores dos elementos para os quais eles apontam, mas não permitem escrever no elemento. Logo, não é possível usar o operador de desreferenciação * no lado esquerdo de uma operação de atribuição (com o símbolo =). Veja a seguir dois exemplos disto que acabo de dizer, um válido e outro inválido.

/**************************************************
* Quais são os 5 tipos de iteradores em C++?
* Exemplo #1 - Operador * com iteradores de entrada
**************************************************/
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    istream_iterator<int> inputIt(cin), eof;
    vector<int> intVector(inputIt, eof);
    
    for (const int anInt : intVector){
        cout << anInt << " ";
    }
    
    // A linha abaixo causa um erro, pois não é permitido
    // atribuir valores usando um iterador de entrada.
    *inputIt = 2;

}

No exemplo #1, na linha 12, são criados dois iteradores do tipo istream_iterator, que pertence à categoria dos iteradores de entrada: inputIt, que é inicializado a partir do cin (o stream de entrada padrão, que utilizamos para ler dados do terminal no programa), e que permite ler dados de entrada como se estivéssemos escrevendo diretamente no próprio cin – é importante notar que apenas inteiros podem ser lidos através do iterador, por isso que se indica o tipo dos dados que serão lidos na declaração da variável; e eof, inicializado com o construtor padrão do tipo istream_iterator, o que equivale ao valor \n (end-of-file, ou “terminador” de linha ou arquivo).

Esses dois iteradores são usados para inicializar o vetor de inteiros intVector na linha 13. O programa, nesse ponto, espera que valores inteiros sejam fornecidos na entrada pelo usuário até que o valor \n seja recebido, o que encerra a inicialização do vetor. Todos os inteiros recebidos na entrada são então adicionados ao vetor, e os valores contidos no vetor são exibidos na saída na linha 16.

Além disso, na linha 21 há uma expressão que causa um erro, pois tentamos usar um iterador de entrada do lado esquerdo de uma operação de atribuição (à esquerda de um =), o que não é permitido. Por fim, é importante notar que os iteradores de entrada podem invalidar todos os iteradores na sequência para a qual ele aponta após se fazer *inputIt++ (acesso ao elemento atual e deslocamento do iterador em uma posição), e portanto eles só convêm ser usados para algoritmos de varredura única, como o find e o accumulate do header <algorithm>.

Operadores necessários aos iteradores de entrada em C++

Resumo das funcionalidades dos iteradores de entrada
Operadores de comparação == e !=
Operador de incremento ++ pré e pós-fixado (++it e it++)
Operador * (apenas para leitura do valor do objeto apontado pelo iterador)
operador -> (para acessar um membro do objeto apontado – it->mem equivale a (*it).mem)

Tipos de iteradores em C++ – Saída

Junto com os iteradores de entrada (e de certa forma os complementando), os iteradores de saída constituem a categoria mais básica dos iteradores em C++. Os iteradores de saída, como é sugerido pelo seu nome, permitem apenas escrever nos seus elementos subjacentes; ou seja, um iterador deste tipo não pode aparecer no lado direito de uma operação de atribuição (usando =).

Além do mais, os iteradores de saída também possuem uma limitação semelhante aos de entrada: eles só convêm ser usados por algorítmos de varredura única, como o copy da biblioteca <algorithm> do C++. Vejamos abaixo um exemplo de uso de um iterador de saída associado ao cout (o fluxo de saída padrão – para saber mais sobre o assunto, visite o artigo Para que serve o endl em C++?).

/**************************************************
* Quais são os 5 tipos de iteradores em C++?
* Exemplo #2 - Operador * com iteradores de saída
**************************************************/
#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    // O iterador de saída outputIt é inicializado
    // a partir do cout, e a cada leitura é adicionado um
    // espaço (o segundo argumento da inicialização)
    ostream_iterator<int> outputIt(cout, " ");
    vector<int> intVector{1, 2, 3, 4, 5};
    
    // O operador * usado no outputIt é desnecessário,
    // e omití-lo não mudaria o funcionamento do programa.
    for (const int anInt : intVector){
        *outputIt = anInt;
    }
    
    // Essa linha causa um erro porque não é possível
    // usar um iterador de saída do lado direito de uma
    // operação de atribuição
    const int x = *outputIt;
}

Operadores necessários aos iteradores de saída em C++

Resumo das funcionalidades dos iteradores de saída
Operador de incremento ++ pré e pós-fixado (++it e it++)
Operador * (apenas para escrita sobre o objeto apontado pelo iterador)

Tipos de iteradores em C++ – Avanço

A categoria seguinte à dos iteradores de entrada e saída é a dos iteradores de avanço. Esses iteradores representam uma evolução com relação aos dois tipos anteriores por fundir as capacidades de ambos: os iteradores de avanço permitem tanto ler quanto escrever a um elemento. Além disso, os iteradores de avanço também podem ser usados em algorítmos de varredura múltipla (que podem atravessar a sequência ou container várias vezes), pois o acesso a elementos através deles não invalida outros iteradores de mesmo tipo na sequência.

Portanto, é possível usar um iterador de avanço para “guardar” o valor (ou estado) de um elemento enquanto se manipula a sequência com outros iteradores semelhantes. Um algoritmo que usar esse tipo de iterador é o replace.

Vejamos a seguir um exemplo de utilização de iteradores de avanço, obtidos através dos métodos begin() e end() de uma lista encadeada simples – forward_list – de inteiros. Os iteradores são utilizados como argumentos da função replace, que substitui todos os valores 2 por 0 na lista de inteiros intFwdList.

/**************************************************
* Quais são os 5 tipos de iteradores em C++?
* Exemplo #3 - Utilização de iteradores de avanço
**************************************************/
#include <iostream>
#include <forward_list>
#include <algorithm>

int main() {
    // Inicialização de uma lista encadeada de avanço com
    // os valores 1, 2, 2 e 4
    std::forward_list<int> intFwdList{1, 2, 2, 4};
    
    // Uso de replace para substituir todos os valores 2
    // por 0 na lista.
    std::replace(intFwdList.begin(), intFwdList.end(), 2, 0);
    for (const auto anInt : intFwdList)
        std::cout << anInt << " ";
    
    return 0;
}

Operadores necessários aos iteradores de avanço em C++

Resumo das funcionalidades dos iteradores de avanço
Operadores de comparação == e !=
Operador de incremento ++ pré e pós-fixado (++it e it++)
Operador * (pode ser usado para leitura e escrita)
operador -> (para acessar um membro do objeto apontado – it->mem equivale a (*it).mem

Tipos de iteradores em C++ – Bidirecionais

Os iteradores de avanço são legais, mas lhes falta uma funcionalidade importante: a capacidade de se deslocar para tràs. Essa é a diferença marcantes entre aqueles e os iteradores bidirecionais. Além de tudo o que oferecem os iteradores de avanço, os bidirecionais possuem o operador de decremento –, que os permite ler e escrever elementos em uma sequência ou container para trás, assim como para a frente. Um exemplo de algorítmo que utiliza iteradores bidirecionais é o reverse, que permite inverter a ordem dos elementos de uma sequência.

Vejamos, assim, um exemplo do uso de iteradores bidirecionais com uma lista (não a confunda com a forward_list do exemplo número 3).

/******************************************************
* Quais são os 5 tipos de iteradores em C++?
* Exemplo #4 - Utilização de iteradores bidirecionais
******************************************************/
#include <iostream>
#include <list>
#include <algorithm>

int main() {
    // Inicialização de uma lista encadeada
    // com os valores 1, 2, 3 e 4
    std::list<int> intList{1, 2, 3, 4};
    
    // Uso de reverse para inverter a ordem dos elementos na lista
    std::reverse(intList.begin(), intList.end());
    for (const auto anInt : intList)
        std::cout << anInt << " ";
    
    return 0;
}

Operadores necessários aos iteradores bidirecionais em C++

Resumo das funcionalidades dos iteradores bidirecionais
Operadores de comparação == e !=
Operador de incremento ++ pré e pós-fixado (++it e it++)
Operador de decremento ++ pré e pós-fixado (--it e it–)
Operador * (pode ser usado para leitura e escrita)
operador -> (para acessar um membro do objeto apontado – it->mem equivale a (*it).mem)

Tipos de iteradores em C++ – Acesso aleatório

Esse, entre todos os tipos de iteradores em C++, é provavelmente o que mais utilizamos nos nossos programas, por ser aquele usado pelos contâineres da biblioteca padrão, o vector, array, deque, string etc. Ou seja, quando escrevemos aVector.begin() o que obtemos como retorno, se aVector for um std::vector<int>, por exemplo, é um iterador de acesso aleatório.

Os iteradores de acesso aleatório são os mais poderosos dentre todos os tipos de iteradores em C++ que vimos até aqui. Eles possuem todas as funcionalidades dos iteradores bidirecionais, além de suportarem algumas operações aritméticas (+, -, += e -=) e relacionais (<, <=, > e >=), com uso semelhante ao das operações com ponteiros. Por suportarem as operações aritméticas, que permitem realizar somas e subtrações entre ponteiros e valores inteiros para deslocar o iterador para a frente ou para trás na sequência, os iteradores de acesso aleatório têm o operador [], que permite acessar uma posição qualquer do contâiner com custo de tempo constante (O(1)).

A título de curiosidade convém saber, portanto, que os ponteiros ordinários se comportam como iteradores de acesso aleatório quando usados para acessar os elementos de arrays estáticos.

Vejamos abaixo alguns exemplos de utilização dessas funcionalidades adicionais dos iteradores de acesso aleatório (com comentários no código).

/**********************************************************
* Quais são os 5 tipos de iteradores em C++?
* Exemplo #5 - Utilização de iteradores de acesso aleatório
***********************************************************/
#include <iostream>
#include <vector>

int main() {
    std::vector<int> intVector{0, 1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<int>::const_iterator vectorIt = intVector.cbegin();
    
    // Cálculo do tamanho do vetor usando iteradores e o operador -
    std::cout << "intVector possui " << intVector.cend() - intVector.cbegin() << " elementos."<< std::endl;
    // Uso do operador [] para acessar um elemento qualquer do vetor
    std::cout << "intVector[5]: " << intVector[5] << std::endl;
    // Forma equivalente usando os operadores +, - e *
    std::cout << "intVector[6]: " << *(vectorIt + 6) << std::endl;
    // Lembre-se que cend() aponta para uma posição além do fim do vetor
    std::cout << "intVector[4]: " << *(intVector.cend() - 5) << std::endl;
    
    // Comparação de posições (e não valores de elementos) entre 
    // dois iteradores usando > e <.
    if ((vectorIt + 3) > vectorIt)
    {
        std::cout << "A posição 4 está mais à frente que a 0" << std::endl;
    }
    
    std::cout << ((intVector.cend() < vectorIt) ? "O fim do vetor vem antes do seu início?!!?!" : "Ufa! Pensei que estivesse louco.") << std::endl;

    return 0;
}

Operadores necessários aos iteradores bidirecionais em C++

Resumo das funcionalidades dos iteradores de acesso aleatório
Operadores de comparação == e !=
Operador de incremento ++ pré e pós-fixado (++it e it++)
Operador de decremento ++ pré e pós-fixado (--it e it–)
Operador * (pode ser usado para leitura e escrita)
operador -> (para acessar um membro do objeto apontado – it->mem equivale a (*it).mem)
Operadores aritméticos +, -, += e -= (usados para deslocar o iterador)
Operador – para uso entre dois iteradores (retorna a distância entre eles)
Operadores relacionais <, <=, > e >= (comparação de posição)
Operador de acesso direto [ ]

Conclusão

Neste artigo vimos brevemente quais são os 5 tipos de iteradores em C++, e quais são as diferenças entre eles: entrada (suportam operações de leitura e apenas deslocamento para a frente); saída (operações de escrita e deslocamento para a frente); avanço (leitura e escrita e deslocamento para a frente); bidirecionais (leitura e escrita, e deslocamento para a frente e para trás); e acesso aleatório (todas as operações anteriores além de operações aritméticas, relacionais e o operador []).