8. Iteradores, algorithm e lambdas¶
O que você escreveu à mão, agora em uma linha¶
No capítulo 5 você escreveu seis algoritmos com for e if. Todos eles já existem na biblioteca padrão, testados e mais rápidos que qualquer versão escrita à mão:
| Você escreveu no capítulo 5 | A biblioteca já tem |
|---|---|
busca_linear |
std::find |
maior_elemento |
std::max_element |
conta_pares |
std::count_if |
media (a soma) |
std::accumulate |
troca |
std::swap |
bubble_sort |
std::sort |
busca_binaria |
std::binary_search |
Lado a lado, o conta_pares daquele capítulo:
int conta_pares(const std::vector<int>& v) { // capitulo 5
int total = 0;
for (int x : v) {
if (x % 2 == 0) {
total++;
}
}
return total;
}
// a mesma coisa, agora:
int total = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
A troca não é só de tamanho. std::sort não é um bubble sort com nome bonito: ele é assintoticamente melhor (n·log n contra n²), o que para dez mil elementos é a diferença entre cerca de 130 mil comparações e cerca de cem milhões. E std::find não tem como errar o limite do laço.
Daqui para a frente, use as versões prontas. O capítulo 5 existiu para que você saiba o que elas fazem por dentro — e para que, quando uma delas se comportar de um jeito estranho, você tenha onde se apoiar para entender.
Iteradores, rapidamente¶
Um iterador é um objeto que "aponta" para um elemento dentro de um container e sabe andar para o próximo. Você já usa a ideia todo dia em C, na forma de um ponteiro andando por um vetor:
std::vector (e todo container da STL) oferece .begin() e .end(), que funcionam de forma parecida:
std::vector<int> v = {10, 20, 30};
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " "; // *it desreferencia, igual ponteiro
}
Na prática, você raramente escreve esse laço na mão — é exatamente o que o range-for (for (int x : v)) faz por baixo dos panos. Mas entender que existe é importante porque as funções de <algorithm> (próxima seção) trabalham recebendo um par de iteradores (begin, end), não o container inteiro — isso permite que a mesma função de <algorithm> funcione em vector, string, map, set, etc.
Lambdas: funções "descartáveis" no meio do código¶
Antes de <algorithm>, você precisa saber escrever uma lambda — uma função anônima, definida no lugar onde vai ser usada. É a resposta do C++ para "quero passar um comportamento como argumento", algo que em C você fazia com ponteiro de função:
// em C: ponteiro de funcao
int compara(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
qsort(vetor, tamanho, sizeof(int), compara);
Em C++, a lambda pode ser escrita ali mesmo, sem precisar de um nome nem de arquivo separado:
Anatomia de uma lambda: [captura](parâmetros) { corpo }.
[]— não captura nada do escopo ao redor.[x]— capturaxpor cópia (a lambda enxerga o valor dexno momento em que foi criada).[&x]— capturaxpor referência (a lambda enxerga oxde verdade, inclusive mudanças depois).[&]— captura tudo do escopo ao redor por referência;[=]— tudo por cópia. Evite essas duas formas "coringa" em código para os outros lerem — prefira ser explícito sobre o que a lambda usa.
int limite = 5;
auto maior_que_limite = [limite](int x) { return x > limite; };
maior_que_limite(10); // true
maior_que_limite(3); // false
<algorithm>: comportamento pronto para percorrer containers¶
Em vez de escrever um laço na mão toda vez, <algorithm> oferece funções genéricas que recebem begin()/end() (e, em vários casos, uma lambda dizendo o critério):
#include <algorithm>
#include <vector>
#include <numeric> // para std::accumulate
std::vector<int> v = {5, 3, 8, 1, 9};
std::sort(v.begin(), v.end());
// v agora e {1, 3, 5, 8, 9}
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
// ordem decrescente: {9, 8, 5, 3, 1}
auto it = std::find(v.begin(), v.end(), 5);
bool achou = (it != v.end());
int quantos_maiores_5 = std::count_if(v.begin(), v.end(),
[](int x) { return x > 5; });
bool algum_negativo = std::any_of(v.begin(), v.end(),
[](int x) { return x < 0; });
bool todos_positivos = std::all_of(v.begin(), v.end(),
[](int x) { return x > 0; });
int soma = std::accumulate(v.begin(), v.end(), 0);
// 0 e o valor inicial do acumulador
std::vector<int> dobrados(v.size());
std::transform(v.begin(), v.end(), dobrados.begin(),
[](int x) { return x * 2; });
Note o padrão comum: iterador de início, iterador de fim, e (quando precisa de um critério) uma lambda. Isso é o que torna sort, find, count_if etc. genéricos — a mesma função std::sort ordena vector<int>, vector<std::string> ou vector<Aluno> (com a lambda certa), sem precisar de uma versão para cada tipo.
Removendo elementos: erase e o idioma erase-remove¶
No capítulo 4 você viu
pop_back() e clear(), e ficou uma promessa: remover de uma posição
qualquer precisava de um iterador. Agora que você tem um, a promessa se paga.
erase: remover de uma posição¶
v.erase(posicao) remove o elemento para o qual o iterador aponta. Como
v.begin() aponta para o primeiro elemento, v.begin() + i aponta para o de
índice i:
std::vector<int> v = {10, 20, 30, 40};
v.erase(v.begin() + 1); // remove o de indice 1 (o 20): {10, 30, 40}
v.erase(v.begin()); // remove o primeiro: {30, 40}
E para remover uma faixa inteira, passa-se o começo e o fim — com o fim
excluído, como em todo o <algorithm>:
std::vector<int> w = {1, 2, 3, 4, 5};
w.erase(w.begin() + 1, w.begin() + 3); // remove os de indice 1 e 2: {1, 4, 5}
Lembre do custo que o capítulo 4 desenhou: erase no meio desloca todos os
elementos que vêm depois. Ele é conveniente, não barato.
remove_if não remove¶
Agora o caso que aparece o tempo todo: tirar do vector todos os elementos que
satisfazem um critério — as leituras negativas, as notas abaixo de 5. O nome
óbvio é std::remove_if, e ele engana:
std::vector<int> v = {5, -2, 9, -1, 3};
auto novo_fim = std::remove_if(v.begin(), v.end(), [](int x) { return x < 0; });
std::cout << v.size() << "\n"; // 5 -- nada foi removido!
v.erase(novo_fim, v.end());
std::cout << v.size() << "\n"; // 3
// v agora e {5, 9, 3}
remove_if não muda o tamanho do vector — e não pode: ele recebe só dois
iteradores, e iterador aponta para elementos, não tem como mexer no container.
O que ele faz é empurrar para a frente os elementos que ficam, na ordem
original, e devolver um iterador para onde essa parte boa termina. Do ponto
devolvido até o fim sobra lixo — valores que você não deve usar.
Quem encolhe o vector é o erase, apagando a faixa de novo_fim até end().
O idioma erase-remove¶
Como os dois passos andam sempre juntos, eles se escrevem numa linha só, e essa linha tem nome — erase-remove:
Leia de dentro para fora: o remove_if arruma e devolve o novo fim; o erase
apaga do novo fim até o fim de verdade. Para remover por valor em vez de por
critério, o parceiro é std::remove, sem lambda:
Compare com o que você faria sem isso, no capítulo 5: percorrer o vector e montar um vector novo só com os que ficam. Continua sendo uma resposta correta — e para quem está começando é a mais fácil de acertar. O erase-remove faz o mesmo sem criar o segundo vector, e numa passada só.
<algorithm> também funciona em std::string¶
std::string é, por baixo, um container de char — então os mesmos algoritmos se aplicam:
#include <algorithm>
#include <cctype>
std::string texto = "Programacao";
std::reverse(texto.begin(), texto.end());
// "oacamargorP" -- e aquela funcao "inverte" que voce escreveu na mao na Lista 01
std::sort(texto.begin(), texto.end());
// ordena os caracteres
std::transform(texto.begin(), texto.end(), texto.begin(),
[](unsigned char c) { return std::toupper(c); });
// converte tudo para maiuscula -- a mesma logica do exercicio "maiusculo" da Lista 02
Perceba: os exercícios que você resolveu "na mão" nas listas 01 e 02 (inverter string, converter para maiúsculo) agora têm uma versão de uma linha usando <algorithm>. Não é acaso — aprender a versão manual primeiro é o que torna óbvio o que <algorithm> está economizando.
Erros comuns¶
Chamei remove_if e o vector não encolheu — é o comportamento esperado, não um bug: remove_if só arruma os elementos e devolve o novo fim; o size() continua o mesmo, com lixo no final. Falta o erase: v.erase(std::remove_if(...), v.end());.
Usei os elementos do fim depois do remove_if e vieram valores estranhos — do iterador devolvido até end(), o conteúdo não é garantido. Nunca leia essa faixa; apague-a com erase.
"error: no matching function for call to..." ao usar lambda em std::sort — confira se a lambda de comparação retorna bool e recebe dois parâmetros do tipo do elemento (ex.: [](int a, int b)), nunca um só.
Esquecer #include <algorithm> ou #include <numeric> — sort/find/count_if/transform vêm de <algorithm>; accumulate vem especificamente de <numeric>. Mensagens de erro tipo 'sort' is not a member of 'std' geralmente significam um include faltando.
Capturar por referência ([&]) uma variável que sai de escopo antes da lambda ser chamada — se você guardar a lambda para usar depois (não é o caso mais comum nas listas, mas aparece em código real), uma referência capturada pode "morrer" antes da lambda ser chamada. Prefira captura por cópia ([x]) quando não tiver certeza.
Resumo¶
v.erase(v.begin() + i)remove o elemento de índicei;v.erase(inicio, fim)remove uma faixa, com o fim excluído.std::remove_ifnão remove: arruma os que ficam na frente e devolve o novo fim. Quem encolhe é oerase— o idioma év.erase(std::remove_if(v.begin(), v.end(), criterio), v.end());.- Iterador é um "ponteiro genérico" (
begin()/end()); range-for usa iteradores por baixo. - Lambda:
[captura](parâmetros) { corpo }— função anônima definida no lugar de uso, o equivalente moderno a passar um ponteiro de função. <algorithm>oferece operações prontas (sort,find,count_if,any_of,all_of,transform) que recebem um par de iteradores e, quando precisam de critério, uma lambda.<numeric>temaccumulatepara somar/reduzir uma sequência.- Os mesmos algoritmos funcionam em
std::string, porque ela também é um container dechar.