O Fio que Une Tudo — Iteradores como Conceito Central

No artigo Buscas Instantâneas — map, set e suas Versões Hash fechamos o tour pelos containers da STL: vector, string, map, set e suas versões hash. Você deve ter notado algo se repetindo em todos eles — o par begin()/end(), o find que devolve "um iterador", o percurso que funciona igual em qualquer container. Isso não é coincidência: existe um conceito por baixo que costura todos esses containers num sistema único e permite que o mesmo algoritmo funcione sobre qualquer um deles. Esse conceito é o iterador, e ele é, talvez, a ideia mais elegante de toda a STL. Hoje você entende o que é um iterador, por que ele generaliza o "ponteiro que percorre" que você conhece do C, e como ele é a ponte que liga containers a algoritmos. Depois desta aula, a biblioteca <algorithm> — próximo artigo — fará todo o sentido.

A ideia: um ponteiro generalizado

Em C, para percorrer um array, você usa um ponteiro que anda de elemento em elemento: incrementa (++p), desreferencia (*p) e compara com o fim. Um iterador é exatamente essa ideia, generalizada para funcionar sobre qualquer container — não só arrays contíguos, mas também árvores (map), tabelas hash (unordered_set) e o que mais existir. Ele oferece a mesma gramática: ++ para avançar, * para acessar o elemento, ==/!= para comparar:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};

    // begin() aponta para o primeiro elemento; end() para UMA POSIÇÃO ALÉM do último.
    // O laço anda com ++it e para quando alcança end().
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << ' ';   // *it desreferencia, como *ponteiro
    }
    std::cout << '\n';   // 10 20 30

    return 0;
}

Esse std::vector<int>::iterator é longo — e é exatamente o tipo de situação onde o auto do artigo Adeus NULL, Bem-vindo à Dedução — nullptr e auto brilha. Escrevendo auto it = v.begin();, o compilador deduz o tipo e o código fica limpo. Guarde esse par mental: iteradores costumam ter tipos verbosos, e auto foi feito, em parte, para eles.

O conceito de "meio-aberto": por que end() fica além do fim

Um detalhe que confunde no início e ilumina depois: end() não aponta para o último elemento, mas para uma posição imaginária logo após ele. O intervalo é meio-aberto: [begin, end) inclui begin e exclui end. Isso parece estranho, mas é profundamente prático. Primeiro, torna o laço natural: it != end() para exatamente quando não há mais elementos. Segundo, um container vazio tem begin() == end(), então o laço simplesmente não executa — sem caso especial. Terceiro, permite representar "não encontrado": quando find devolve end(), significa "cheguei ao fim sem achar":

#include <iostream>
#include <vector>
#include <algorithm>   // std::find

int main() {
    std::vector<int> v = {1, 2, 3, 4};

    auto it = std::find(v.begin(), v.end(), 3);   // procura o 3
    if (it != v.end())                            // achou? (não chegou ao fim)
        std::cout << "encontrado: " << *it << '\n';   // encontrado: 3

    auto it2 = std::find(v.begin(), v.end(), 99);  // procura o 99
    if (it2 == v.end())                            // não achou (chegou ao fim)
        std::cout << "99 não está no vetor\n";
    return 0;
}

Esse padrão — comparar o resultado com end() para saber se achou — é onipresente na STL. Você já o viu com map::find no artigo Buscas Instantâneas — map, set e suas Versões Hash; agora entende que é o mesmo padrão, porque iteradores unificam a interface.

A grande sacada: o mesmo código para qualquer container

Aqui está o poder que justifica tudo. Porque map, set, vector e todos os outros expõem begin()/end() e iteradores com a mesma gramática (++, *, !=), um algoritmo escrito em termos de iteradores funciona sobre qualquer um deles, sem saber qual é. Veja a mesma função de impressão servir a três containers completamente diferentes por dentro:

#include <iostream>
#include <vector>
#include <set>
#include <map>

// Um template (Fase 5) que percorre QUALQUER container via iteradores.
// Não sabe nem se importa se é vector, set ou map — só usa begin/end.
template <typename Iterador>
void imprime(Iterador inicio, Iterador fim) {
    for (auto it = inicio; it != fim; ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> v = {3, 1, 2};
    std::set<int>    s = {3, 1, 2};   // conjunto ordenado

    imprime(v.begin(), v.end());   // 3 1 2 (ordem de inserção do vector)
    imprime(s.begin(), s.end());   // 1 2 3 (o set mantém ordenado)
    return 0;
}

A função imprime foi escrita uma vez e serve ao vector e ao set, cujas estruturas internas (array contíguo versus árvore balanceada) não têm nada em comum. O iterador é a interface que esconde essa diferença. Não se prenda ao template — ele é a Fase 5; o que importa agora é a ideia: iteradores desacoplam algoritmos de containers. Um algoritmo fala a língua dos iteradores; qualquer container que a fale pode usá-lo.

Uma honestidade sobre categorias e invalidação

Prometo sempre os limites, e há dois aqui. Primeiro, nem todos os iteradores são igualmente poderosos. O iterador de um vector é aleatório — você pode pular direto para o elemento it + 5, porque a memória é contígua. Já o de um set ou list é bidirecional — só anda de um em um (++/--), sem saltos, porque a estrutura não é contígua. Isso significa que alguns algoritmos (como ordenação, que precisa de saltos) funcionam com vector mas não com set. Você não precisa decorar as categorias agora, mas saiba que elas existem e explicam por que certos algoritmos exigem certos containers.

Segundo, a armadilha que já vimos em outra roupa: iteradores podem ser invalidados. Assim como uma referência a um elemento de vector fica pendente após uma realocação (artigo O Array que Cresce Sozinho — std::vector a Fundo), um iterador para esse elemento também fica. Modificar um container enquanto você o percorre com iteradores é uma fonte clássica de bugs. A regra de bolso: não altere o tamanho de um container enquanto itera sobre ele, a menos que você saiba exatamente como aquele container trata a invalidação.

O iterador é o que permite escrever uma função uma vez e usá-la sobre qualquer container: ela não conhece a estrutura, só sabe avançar e desreferenciar. O intervalo meio-aberto, com end() uma posição além do último, é a convenção que faz o container vazio ter begin() == end() e a subtração dar o tamanho direto. A parte que exige cuidado é a invalidação — cada container tem suas regras sobre quais operações derrubam iteradores obtidos antes, e o código quebra longe de onde o erro foi cometido.

Fontes e leituras recomendadas

• cppreference.com/w/cpp/iterator: a referência sobre iteradores, suas categorias (input, output, forward, bidirectional, random access) e operações.
• Bjarne Stroustrup, A Tour of C++ (3ª ed.), capítulo sobre a STL: a apresentação dos iteradores como o elo entre containers e algoritmos.
• cppreference.com/w/cpp/named_req/Iterator: os requisitos formais que definem cada categoria de iterador — útil para entender por que certos algoritmos exigem certos iteradores.
• Scott Meyers, Effective STL (2001), Itens 26–30 (sobre iteradores e sua invalidação): conselhos práticos sobre os perigos desta aula.
• ISO C++ Core Guidelines, seção sobre STL e iteradores: as diretrizes sobre uso seguro de intervalos.

Exercícios

Exercício 1

Percorra um std::vector<std::string> usando explicitamente iteradores (begin()/end() e ++it), imprimindo cada elemento com *it. Depois reescreva o mesmo laço usando auto e comente a diferença de legibilidade.

#include <iostream>
#include <vector>
#include <string>
int main() {
    std::vector<std::string> nomes = {"Ana", "Bruno", "Carla"};

    // Explícito: tipo verboso
    for (std::vector<std::string>::iterator it = nomes.begin(); it != nomes.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';

    // Com auto: idêntico em comportamento, muito mais legível
    for (auto it = nomes.begin(); it != nomes.end(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
    return 0;
}

Exercício 2

Explique, com suas palavras, por que end() aponta para "uma posição além do último" e não para o último elemento. Cite dois benefícios concretos dessa convenção.

Exercício 3

Use std::find para localizar um valor num std::vector<int> e trate os dois casos (achou / não achou) comparando o iterador com end(). Depois faça o mesmo com um std::set<int> e comente por que o padrão é idêntico.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
int main() {
    std::vector<int> v = {1, 2, 3};
    auto itv = std::find(v.begin(), v.end(), 2);
    std::cout << (itv != v.end() ? "achou no vector\n" : "não achou\n");

    std::set<int> s = {1, 2, 3};
    auto its = s.find(2);   // set tem seu próprio find (mais eficiente que std::find nele)
    std::cout << (its != s.end() ? "achou no set\n" : "não achou\n");
    return 0;
}

Exercício 4

O trecho abaixo tem um bug de invalidação de iterador. Explique o que dá errado e proponha uma correção (dica: erase devolve um iterador válido para o próximo elemento).

#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);   // remover enquanto itera...
}

#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0)
        it = v.erase(it);   // erase devolve iterador válido para o próximo; NÃO incrementa aqui
    else
        ++it;               // só avança quando NÃO removeu
}

Exercício 5

Explique por que a função imprime(inicio, fim) desta aula consegue funcionar tanto com um vector quanto com um set, apesar de suas estruturas internas serem completamente diferentes. O que exatamente os dois containers têm em comum que torna isso possível?