C++ Iteradores

Na aula O que é a STL, você viu que os algoritmos recebem notas.begin() e notas.end(). Essas duas coisas são iteradores: pequenos objetos que apontam um item de um container e sabem andar para o próximo. Nesta aula você vai usá-los com as próprias mãos: pegar o item apontado, avançar, percorrer o container inteiro, e entender o erro mais traiçoeiro deles, o iterador que fica "apontando para o nada" depois de você apagar um item.

Todos os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp/it, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. É bom conhecer std::vector e ter uma ideia de ponteiros (o iterador se parece muito com eles).

A ideia: o dedo na lista de chamada

A professora faz a chamada com o dedo na lista: o dedo começa no primeiro nome, ela lê o nome em que o dedo está, desce o dedo para o próximo, lê, desce… Quando o dedo passa do último nome e chega na margem de baixo da folha, a chamada acabou.

Um iterador é esse dedo:

A margem não é um nome: não dá para "ler" a margem. Do mesmo jeito, end() não aponta item nenhum; ele só marca onde a lista acabou. Guarde isso, porque é a fonte de vários erros.

1. begin(), *it e ++it, um passo de cada vez

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 4, 10};

    auto it = notas.begin();
    std::cout << *it << '\n';

    ++it;
    std::cout << *it << '\n';

    ++it;
    ++it;
    std::cout << *it << '\n';

    ++it;
    if (it == notas.end()) {
        std::cout << "chegou no fim\n";
    }
}

auto it = notas.begin();

Cria o iterador it (nome tradicional, de iterator) apontando o primeiro item. O auto deixa o compilador escrever o tipo, que é comprido (seção 3).

*it

"O item para onde it aponta". O * é o mesmo dos ponteiros: lê-se "o conteúdo de".

++it;

Avança o dedo um item. Prefira ++it a it++ com iteradores: fazem o mesmo aqui, e o ++it nunca precisa guardar uma cópia (aula ++ e --).

it == notas.end()

Compara dois iteradores: "o dedo chegou na margem?". Iteradores do mesmo container podem ser comparados com == e !=.

$ g++ -std=c++23 -Wall -Wextra dedo.cpp -o dedo
$ ./dedo
7
9
10                       « dois ++ pularam o 4 e pararam no 10
chegou no fim

2. O end() fica depois do último

E se você tentar ler o end(), como se fosse um item?

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 4, 10};
    auto it = notas.end();
    std::cout << *it << '\n';
}

$ g++ -std=c++23 -Wall -Wextra fim.cpp -o fim
$ ./fim
0                        « um número qualquer: ninguém sabe de onde veio

Compilou sem aviso e mostrou 0. Não se engane: esse 0 é lixo, o que estava na memória logo depois do vetor. É comportamento indefinido: em outro computador, ou amanhã, pode sair outro número ou o programa pode cair.

Para pegar esse tipo de erro, a biblioteca do g++ tem um modo de depuração: compile com -D_GLIBCXX_DEBUG e os iteradores passam a se vigiar:

$ g++ -std=c++23 -Wall -Wextra -D_GLIBCXX_DEBUG fim.cpp -o fim
$ ./fim
$ ./fim
/usr/include/c++/15/debug/safe_iterator.h:352:
In function:
    constexpr gnu_debug::_Safe_iterator<_Iterator, _Sequence, 
    _Category>::reference gnu_debug::_Safe_iterator<_Iterator, _Sequence, 
    _Category>::operator*() const [with _Iterator = gnu_cxx::
    normal_iterator<int*, std::vector<int, std::allocator<int> > >; 
    _Sequence = std::debug::vector<int>; _Category = 
    std::forward_iterator_tag; reference = int&]

Error: attempt to dereference a past-the-end iterator.

Objects involved in the operation:
    iterator "this" @ 0x7ffeecb465a0 {
      type = gnu_cxx::normal_iterator<int*, std::vector<int, std::allocator<int> > > (mutable iterator);
      state = past-the-end;
      references sequence with type 'std::debug::vector<int, std::allocator<int> >' @ 0x7ffeecb465d0
    }
Abortado                   (imagem do núcleo gravada) ./fim

A linha que importa é Error: attempt to dereference a past-the-end iterator: "tentativa de desreferenciar (ler com *) um iterador que passou do fim". O resto mostra qual iterador (state = past-the-end, "estado: depois do fim"). O programa foi parado na hora (Abortado), em vez de seguir com lixo. Use -D_GLIBCXX_DEBUG enquanto estiver testando; ele deixa o programa mais lento, então não use na versão final.

3. Percorrer o container inteiro

Juntando as peças, o laço clássico com iterador:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 4, 10};

    for (auto it = notas.begin(); it != notas.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    for (auto it = notas.begin(); it != notas.end(); ++it) {
        *it = *it + 1;
    }

    for (std::vector<int>::iterator it = notas.begin(); it != notas.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra percorrer.cpp -o percorrer
$ ./percorrer
7 9 4 10
8 10 5 11

E o for de intervalo?

O for (int n : notas) da aula range-for é esse mesmo laço, escrito pelo compilador: por baixo, ele chama begin(), end(), !=, ++ e *. Então quando usar cada um?

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{8, 10, 5, 11};

    // dobre as notas aqui, com um laço de iterador

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{8, 10, 5, 11};

    for (auto it = notas.begin(); it != notas.end(); ++it) {
        *it = *it * 2;
    }

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

Iteradores devolvidos pelos algoritmos

Muitos algoritmos devolvem um iterador. O std::find devolve o dedo apontando o item achado, ou o end() se não achou. E existe o dedo que anda ao contrário: rbegin() (o último item) e rend() (antes do primeiro).

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 4, 10};

    auto pos = std::find(notas.begin(), notas.end(), 4);
    if (pos != notas.end()) {
        std::cout << "achei o " << *pos << " na posição "
                  << pos - notas.begin() << '\n';
    }

    auto nada = std::find(notas.begin(), notas.end(), 5);
    if (nada == notas.end()) {
        std::cout << "5 não está na lista\n";
    }

    for (auto it = notas.rbegin(); it != notas.rend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra achar.cpp -o achar
$ ./achar
achei o 4 na posição 2
5 não está na lista
10 4 9 7

pos - notas.begin() é "quantos passos do começo até o dedo": a posição. Essa conta (e it + 3, para pular três) só existe nos iteradores de vector, array, deque e string, que podem pular direto para qualquer lugar. Nos outros containers, use std::next(it, 3) e std::distance(a, b), do cabeçalho <iterator>. Sempre confira != end() antes de usar *pos: se o find não achou, pos é o end(), e você já viu o que acontece ao ler o end().

4. O dedo que só lê: const_iterator, cbegin() e cend()

Quando você só quer ler, use cbegin() e cend() (o c é de const). Eles devolvem um const_iterator, um iterador que não deixa mudar o item. Se você tentar, o compilador recusa:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 4, 10};

    for (auto it = notas.cbegin(); it != notas.cend(); ++it) {
        *it = 0;
    }
}

$ g++ -std=c++23 -Wall -Wextra constante.cpp -o constante
constante.cpp: In function ‘int main()’:
constante.cpp:8:13: error: assignment of read-only location ‘it.__gnu_cxx::__normal_iterator<const int*, std::vector<int> >::operator*()’
    8 |         *it = 0;
      |         ~~~~^~~

"Atribuição a um local somente leitura". No meio do nome comprido, repare em const int*: por dentro, esse iterador é um ponteiro para int constante (aula const com Ponteiros). No editor do guia, o Clang diz cannot assign to return value because function 'operator*' returns a const value.

Regra prática: se o laço só lê, use cbegin()/cend(). Assim, se alguém escrever *it = … por engano, o compilador avisa.

5. Invalidação: o dedo que aponta para o nada

A Ana quer apagar as notas abaixo de 5. O vector tem o método erase(it), que apaga o item apontado por um iterador. Ela escreveu o laço que parece óbvio:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 3, 4, 10, 2};

    for (auto it = notas.begin(); it != notas.end(); ++it) {
        if (*it < 5) {
            notas.erase(it);
        }
    }

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra apagar-errado.cpp -o apagar-errado
$ ./apagar-errado
Falha de segmentação     (imagem do núcleo gravada) ./apagar-errado
$ echo $?
139                      « 128 + 11: morto pelo sinal 11 (SIGSEGV)

Compilou sem aviso e caiu com falha de segmentação: o programa tentou ler memória que não é dele. Para descobrir onde, compile com o AddressSanitizer (-fsanitize=address, aula Sanitizers) e -g (para ele saber os números das linhas). A saída é longa; aqui vão as 21 primeiras linhas:

$ g++ -std=c++23 -Wall -Wextra -g -fsanitize=address apagar-errado.cpp -o apagar-errado
$ ./apagar-errado 2>&1 | head -n 21
=================================================================
==542060==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6c987c5e0054 at pc 0x5bec0afaa637 bp 0x7ffdf7b04d40 sp 0x7ffdf7b04d30
READ of size 4 at 0x6c987c5e0054 thread T0
    #0 0x5bec0afaa636 in main /home/ana/cpp/it/apagar-errado.cpp:8
    #1 0x70687d22a600 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:59
    #2 0x70687d22a717 in __libc_start_main_impl ../csu/libc-start.c:360
    #3 0x5bec0afaa384 in _start (/home/ana/cpp/it/apagar-errado+0x2384) (BuildId: 9495fc923138f7f87bd5f930cbd7fc9534a260d1)

0x6c987c5e0054 is located 0 bytes after 20-byte region [0x6c987c5e0040,0x6c987c5e0054)
allocated by thread T0 here:
    #0 0x70687db2c73f in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:109
    #1 0x5bec0afabd6d in std::__new_allocator<int>::allocate(unsigned long, void const*) /usr/include/c++/15/bits/new_allocator.h:151
    #2 0x5bec0afab7b4 in std::allocator<int>::allocate(unsigned long) /usr/include/c++/15/bits/allocator.h:203
    #3 0x5bec0afab7b4 in std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) /usr/include/c++/15/bits/alloc_traits.h:614
    #4 0x5bec0afab7b4 in std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) /usr/include/c++/15/bits/stl_vector.h:387
    #5 0x5bec0afab0af in void std::vector<int, std::allocator<int> >::_M_range_initialize_n<int const*, int const*>(int const*, int const*, unsigned long) /usr/include/c++/15/bits/stl_vector.h:1985
    #6 0x5bec0afaad4e in std::vector<int, std::allocator<int> >::vector(std::initializer_list<int>, std::allocator<int> const&) /usr/include/c++/15/bits/stl_vector.h:712
    #7 0x5bec0afaa56f in main /home/ana/cpp/it/apagar-errado.cpp:5
    #8 0x70687d22a600 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:59
    #9 0x70687d22a717 in __libc_start_main_impl ../csu/libc-start.c:360
    #10 0x5bec0afaa384 in _start (/home/ana/cpp/it/apagar-errado+0x2384) (BuildId: 9495fc923138f7f87bd5f930cbd7fc9534a260d1)

heap-buffer-overflow

"Estouro de área do heap": o programa leu além do fim de um bloco de memória (o bloco onde o vetor guarda as notas).

READ of size 4

Foi uma leitura de 4 bytes: um int.

#0 … in main /home/ana/cpp/it/apagar-errado.cpp:8

Onde: linha 8, o if (*it < 5). O *it leu fora do vetor.

located 0 bytes after 20-byte region

A leitura foi "0 bytes depois de uma região de 20 bytes": exatamente na primeira casa depois das 5 notas (5 × 4 bytes = 20). O dedo passou do fim.

allocated by thread T0 here: … apagar-errado.cpp:5

Quem criou esse bloco: a linha 5, a criação do vetor notas.

O que aconteceu, volta a volta

Quando o erase apaga um item, ele empurra os seguintes uma casa para a esquerda, para não deixar buraco. O iterador it, que apontava o item apagado, passa a ser inválido: oficialmente, ele não aponta mais nada que se possa usar. Na prática, ele fica parado na mesma casa, que agora tem o próximo item. Aí o ++it do for pula esse item:

1. {7, 3, 4, 10, 2}, dedo no 7: fica. ++it → dedo no 3.
2. 3 < 5: erase. Vira {7, 4, 10, 2}; o dedo, parado na casa 1, agora vê o 4. O ++it pula para o 10: o 4 nunca foi testado.
3. 10: fica. ++it → dedo no 2.
4. 2 < 5: erase. Vira {7, 4, 10}; o dedo, na casa 3, agora está exatamente no end(). O ++it o leva para depois do end().
5. O teste it != notas.end() continua verdadeiro (o dedo passou da margem sem parar nela), e o *it lê fora do vetor: a falha de segmentação.

O conserto: o erase devolve o próximo

O erase devolve um iterador novo e válido, apontando o item que veio depois do apagado. Use esse retorno, e só avance o dedo quando não apagar:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{7, 3, 4, 10, 2};

    for (auto it = notas.begin(); it != notas.end(); ) {
        if (*it < 5) {
            it = notas.erase(it);
        } else {
            ++it;
        }
    }

    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

for (auto it = …; it != notas.end(); )

Repare: a terceira parte do for está vazia. O dedo não avança sozinho; quem decide é o corpo.

it = notas.erase(it);

Apaga e já põe o dedo no próximo item (ou no end(), se apagou o último). Nada é pulado.

else { ++it; }

Só avança quando o item fica.

$ g++ -std=c++23 -Wall -Wextra apagar-certo.cpp -o apagar-certo
$ ./apagar-certo
7 10

O que mais invalida iteradores

Não é só o erase. Quando um vector cresce além do espaço reservado (por exemplo, num push_back), ele se muda para um bloco de memória maior e devolve o antigo. Todo iterador que apontava para o bloco antigo fica apontando para memória devolvida. Um laço que faz push_back no mesmo vetor que percorre leva o AddressSanitizer a acusar outro erro, heap-use-after-free ("uso do heap depois de liberado"):

$ g++ -std=c++23 -Wall -Wextra -g -fsanitize=address crescer.cpp -o crescer     « um laço com notas.push_back(10) dentro
$ ./crescer 2>&1 | head -n 6
=================================================================
==542399==ERROR: AddressSanitizer: heap-use-after-free on address 0x79f9861e0014 at pc 0x600097e496db bp 0x7ffd3402a130 sp 0x7ffd3402a120
READ of size 4 at 0x79f9861e0014 thread T0
    #0 0x600097e496da in main /home/ana/cpp/it/crescer.cpp:11
    #1 0x7dd986e2a600 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:59
    #2 0x7dd986e2a717 in __libc_start_main_impl ../csu/libc-start.c:360

Regra de bolso: se o laço muda o tamanho do container, desconfie dos iteradores. Os outros containers têm regras próprias (na std::list, por exemplo, apagar um item só invalida o iterador dele); cada aula de container conta as suas.

Quando dá errado

Referência rápida

Exercícios

Missão final: tirar o café da lista

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> compras{"café", "arroz", "café", "café", "leite", "pão"};

    for (auto it = compras.begin(); it != compras.end(); ++it) {
        // troque este laço por um que apague os "café" sem pular nenhum
    }

    for (const auto& item : compras) {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> compras{"café", "arroz", "café", "café", "leite", "pão"};

    for (auto it = compras.begin(); it != compras.end(); ) {
        if (*it == "café") {
            it = compras.erase(it);
        } else {
            ++it;
        }
    }

    for (const auto& item : compras) {
        std::cout << item << ' ';
    }
    std::cout << '\n';
}

Resumo

• Um iterador é um dedo que aponta um item de um container. *it lê (ou muda) o item; ++it avança.
• begin() aponta o primeiro item; end() aponta a posição depois do último, que não é item. Nunca leia *end().
• O laço: for (auto it = c.begin(); it != c.end(); ++it). O for de intervalo faz isso por você e é o padrão.
• cbegin()/cend() dão um const_iterator, que só lê.
• Apagar ou inserir num vector invalida iteradores. Ao apagar num laço: it = c.erase(it); e ++it só no else. Ou std::erase_if C++20.
• -D_GLIBCXX_DEBUG e -fsanitize=address transformam esses erros silenciosos em mensagens claras.
• Próximo passo: containers que não são o vector, em list e deque.