C++ Algoritmos

Ordenar as notas da turma, achar um item na lista de compras, contar quantas vezes saiu 6 no dado, somar os preços do carrinho. Você já sabe fazer tudo isso com um for. Mas são tarefas tão comuns que a biblioteca padrão traz cada uma pronta, testada e rápida, no cabeçalho <algorithm> (e algumas em <numeric>). Nesta aula você vai conhecer os algoritmos que aparecem em quase todo programa C++ e aprender a ler o "par de iteradores" que todos eles recebem.

Os programas foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. Você vai precisar de std::vector, Iteradores e Lambdas. A lista completa de algoritmos fica em Referência: Algoritmos; aqui estão os que você vai usar toda semana.

A ideia: ferramentas prontas na caixa

Imagine que a Ana precisa apertar parafusos. Ela pode fabricar uma chave de fenda (escrever o for na mão) ou pegar a que está na caixa de ferramentas. A da caixa já foi usada por milhões de pessoas, não tem defeito e tem um nome: quem lê std::sort(…) entende na hora "aqui se ordena", enquanto um for com dois índices obriga a ler linha por linha.

Quase todos os algoritmos recebem um intervalo: dois iteradores que dizem "de onde até onde" trabalhar.

std::sort(

O nome do algoritmo, sempre com std::.

v.begin(),

Onde o trabalho começa: o primeiro elemento.

v.end()

Onde o trabalho termina: uma posição depois do último (o "fim", que não é um elemento).

, …)

Alguns algoritmos recebem mais coisas: um valor para procurar, uma lambda com uma regra.

Como recebem um intervalo, os algoritmos funcionam em vector, std::array, string, deque e até numa parte de um vetor (v.begin() + 1 até v.end()). Existe uma forma mais curta, std::ranges::sort(v), sem begin/end; ela é o assunto da próxima aula, Ranges. Vale aprender a forma clássica primeiro: ela está em todo o código C++ que você vai ler.

1. std::sort: ordenar

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

int main() {
    std::vector<int> notas = {7, 10, 4, 8, 6};
    std::sort(notas.begin(), notas.end());
    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';

    std::vector<std::string> nomes = {"Carla", "ana", "Bruno", "Ana"};
    std::sort(nomes.begin(), nomes.end());
    for (const auto& nome : nomes) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra ordenar.cpp -o ordenar
$ ./ordenar
4 6 7 8 10
Ana Bruno Carla ana                  « "ana" minúsculo foi para o fim!

O std::sort muda o próprio vetor: não cria outro. Números ficam do menor para o maior. Textos ficam em ordem "de dicionário", mas com um detalhe: o computador compara os códigos das letras, e todas as maiúsculas vêm antes de todas as minúsculas (por isso ana ficou depois de Carla). Letras acentuadas também caem no fim (veja Acentos e UTF-8).

Com uma regra sua: a lambda de comparação

O terceiro argumento do sort é opcional: uma função que recebe dois elementos a e b e responde true se a deve vir antes de b. A forma mais prática de escrever essa função é uma lambda:

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

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

    std::sort(notas.begin(), notas.end(), [](int a, int b) {
        return a > b;
    });
    for (int n : notas) std::cout << n << ' ';
    std::cout << '\n';

    std::sort(notas.begin(), notas.end(), std::greater<int>());
    for (int n : notas) std::cout << n << ' ';
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra decrescente.cpp -o decrescente
$ ./decrescente
10 8 7 6 4
10 8 7 6 4                           « std::greater faz a mesma coisa que a lambda

[](int a, int b) { return a > b; }

"a vem antes de b quando a é maior": ordem decrescente. Com a < b, seria a ordem normal.

std::greater<int>()

Uma comparação pronta, de <functional>, que faz a > b. Útil para o caso simples; a lambda serve para qualquer regra.

Onde a lambda brilha é em ordenar structs por um campo:

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

struct Aluno {
    std::string nome;
    double nota;
};

int main() {
    std::vector<Aluno> turma = {
        {"Bruno", 7.5}, {"Ana", 9.0}, {"Carla", 6.0}, {"Davi", 9.0}
    };

    // da maior nota para a menor
    std::sort(turma.begin(), turma.end(), [](const Aluno& a, const Aluno& b) {
        return a.nota > b.nota;
    });

    for (const auto& aluno : turma) {
        std::cout << aluno.nome << ": " << aluno.nota << '\n';
    }
}

$ g++ -std=c++23 -Wall -Wextra alunos.cpp -o alunos
$ ./alunos
Ana: 9
Davi: 9
Bruno: 7.5
Carla: 6

Os parâmetros são const Aluno& (referência constante, aula Por Valor × Por Referência) para não copiar cada aluno a cada comparação. Um detalhe: Ana e Davi empataram em 9. O std::sort não promete manter a ordem original entre empatados; aqui saiu Ana antes, mas poderia ser o contrário. Se a ordem dos empatados importar, use std::stable_sort ("ordenação estável"), com os mesmos argumentos.

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

struct Aluno {
    std::string nome;
    double nota;
};

int main() {
    std::vector<Aluno> turma = {
        {"Bruno", 7.5}, {"Ana", 9.0}, {"Carla", 6.0}, {"Davi", 8.0}
    };

    std::sort(turma.begin(), turma.end(), [](const Aluno& a, const Aluno& b) {
        return a.nota > b.nota;
    });

    for (const auto& aluno : turma) {
        std::cout << aluno.nome << ": " << aluno.nota << '\n';
    }
}

2. std::find e std::find_if: buscar

std::find procura um valor e devolve um iterador (aula Iteradores) apontando para ele. E se não achar? Ele devolve o end(), o "fim". Por isso, sempre compare com end() antes de usar o resultado.

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

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

    auto it = std::find(compras.begin(), compras.end(), "café");
    if (it != compras.end()) {
        std::cout << "Achei " << *it << " na posição "
                  << (it - compras.begin()) << '\n';
    } else {
        std::cout << "Não está na lista\n";
    }

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

$ g++ -std=c++23 -Wall -Wextra buscar.cpp -o buscar
$ ./buscar
Achei café na posição 2              « posições contam a partir de 0
chocolate não está na lista

std::find_if procura o primeiro elemento que satisfaz uma condição, escrita numa lambda que responde true/false:

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

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

    auto it = std::find_if(notas.begin(), notas.end(), [](int n) {
        return n < 5;
    });
    if (it != notas.end()) {
        std::cout << "Primeira nota abaixo de 5: " << *it << '\n';
    }
}

$ g++ -std=c++23 -Wall -Wextra buscar_if.cpp -o buscar_if
$ ./buscar_if
Primeira nota abaixo de 5: 4         « o 3 também é, mas o find_if para no primeiro

Uma lambda que responde sim ou não tem um nome técnico: predicado. Você vai ver essa palavra na documentação de vários algoritmos com _if no nome.

3. std::count e std::count_if: contar

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

int main() {
    std::vector<int> dados = {3, 6, 6, 1, 6, 2, 5};

    auto seis = std::count(dados.begin(), dados.end(), 6);
    std::cout << "Saiu 6: " << seis << " vezes\n";

    auto altos = std::count_if(dados.begin(), dados.end(), [](int d) {
        return d >= 5;
    });
    std::cout << "5 ou mais: " << altos << " vezes\n";
}

$ g++ -std=c++23 -Wall -Wextra contar.cpp -o contar
$ ./contar
Saiu 6: 3 vezes
5 ou mais: 4 vezes                   « 6, 6, 6 e 5

count conta quantos são iguais a um valor; count_if conta quantos satisfazem a lambda. O resultado é um número inteiro com sinal (por isso o auto; se quiser, guarde num long).

4. std::min_element e std::max_element: o menor e o maior

Assim como o find, eles devolvem um iterador, não o valor. Use * para ver o valor e a subtração para saber a posição:

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

int main() {
    std::vector<double> precos = {4.5, 12.9, 2.75, 8.0};

    auto menor = std::min_element(precos.begin(), precos.end());
    auto maior = std::max_element(precos.begin(), precos.end());

    std::cout << "Mais barato: " << *menor << '\n';
    std::cout << "Mais caro: " << *maior << '\n';
    std::cout << "O mais caro está na posição " << (maior - precos.begin()) << '\n';
}

$ g++ -std=c++23 -Wall -Wextra extremos.cpp -o extremos
$ ./extremos
Mais barato: 2.75
Mais caro: 12.9
O mais caro está na posição 1

Eles também aceitam uma lambda de comparação, igual à do sort: std::max_element(turma.begin(), turma.end(), [](const Aluno& a, const Aluno& b) { return a.nota < b.nota; }) acha o aluno de maior nota. Cuidado com o vetor vazio: aí o resultado é o end(), e usar * nele é um erro grave (veja "Quando dá errado"). Para comparar só dois valores soltos, existem std::min(a, b) e std::max(a, b).

5. std::accumulate: somar (e a armadilha do 0)

O accumulate ("acumular") fica em outro cabeçalho, <numeric>. Ele recebe o intervalo e um valor inicial, e soma tudo a partir dele:

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> quantidades = {3, 5, 2};
    int total = std::accumulate(quantidades.begin(), quantidades.end(), 0);
    std::cout << "Itens: " << total << '\n';

    std::vector<double> precos = {4.5, 12.9, 2.75};
    double errado = std::accumulate(precos.begin(), precos.end(), 0);
    double certo = std::accumulate(precos.begin(), precos.end(), 0.0);
    std::cout << "Com 0:   " << errado << '\n';
    std::cout << "Com 0.0: " << certo << '\n';
}

$ g++ -std=c++23 -Wall -Wextra somar.cpp -o somar      « nenhum aviso!
$ ./somar
Itens: 10
Com 0:   18                          « ERRADO: 4.5 + 12.9 + 2.75 = 20.15
Com 0.0: 20.15

O que aconteceu? O accumulate usa o tipo do valor inicial para guardar a soma parcial. 0 é um int, então a soma é guardada num int, e a cada passo a parte decimal é jogada fora (conversão de double para int, aula Conversão de Tipos):

1. Começa com 0 (int).
2. 0 + 4.5 = 4.5 → guardado como int: 4.
3. 4 + 12.9 = 16.9 → 16.
4. 16 + 2.75 = 18.75 → 18. O resultado final, 18, é convertido para o double errado.

O accumulate também aceita uma lambda no fim, para "acumular" de outro jeito (multiplicar, juntar textos com vírgula). Para médias, divida a soma pelo size(), como na missão final.

6. std::reverse: inverter

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::reverse(v.begin(), v.end());
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    std::string palavra = "socorram";
    std::reverse(palavra.begin(), palavra.end());
    std::cout << palavra << '\n';
}

$ g++ -std=c++23 -Wall -Wextra inverter.cpp -o inverter
$ ./inverter
5 4 3 2 1
marrocos                             « "socorram" de trás para frente

Funciona em vetores e em strings, porque os dois têm begin() e end(). Em textos com acento, cuidado: em UTF-8 uma letra como "ã" ocupa 2 bytes, e inverter byte a byte estraga a letra (aula Acentos e UTF-8).

7. std::unique + erase: tirar repetidos

Este é o algoritmo mais traiçoeiro da lista. Veja três tentativas:

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

void mostrar(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << "(tamanho " << v.size() << ")\n";
}

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

    std::vector<int> a = v;
    std::unique(a.begin(), a.end());
    std::cout << "unique sem sort:      ";
    mostrar(a);

    std::vector<int> b = v;
    std::sort(b.begin(), b.end());
    auto novo_fim = std::unique(b.begin(), b.end());
    std::cout << "sort + unique:        ";
    mostrar(b);

    b.erase(novo_fim, b.end());
    std::cout << "sort + unique + erase: ";
    mostrar(b);
}

$ g++ -std=c++23 -Wall -Wextra repetidos.cpp -o repetidos
repetidos.cpp: In function ‘int main()’:
repetidos.cpp:14:16: warning: ignoring return value of ‘constexpr _FIter std::unique(_FIter, _FIter) [with _FIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]’, declared with attribute ‘nodiscard’ [-Wunused-result]
   14 |     std::unique(a.begin(), a.end());
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/15/algorithm:63,
                 from repetidos.cpp:1:
/usr/include/c++/15/bits/stl_algo.h:875:5: note: declared here
  875 |     unique(_ForwardIterator __first, _ForwardIterator __last)
      |     ^~~~~~
$ ./repetidos
unique sem sort:      5 1 5 3 1 5 (tamanho 6)       « nada mudou!
sort + unique:        1 3 5 5 5 5 (tamanho 6)       « 1 3 5 na frente, sobras atrás
sort + unique + erase: 1 3 5 (tamanho 3)            « agora sim

Duas lições:

• unique só junta repetidos que estão lado a lado. Em 5 1 5 3 1 5, nenhum número se repete encostado no outro, então nada mudou. Por isso, quase sempre se faz sort antes: ordenado, os iguais ficam juntos.
• unique não apaga nada. Um algoritmo recebe só iteradores e não consegue mudar o tamanho do vetor. Ele empurra os valores únicos para a frente e devolve um iterador para o "novo fim". O que fica depois dele são sobras (aqui, 5 5 5, mas podem ser quaisquer valores). Quem apaga de verdade é o erase do próprio vetor, do novo fim até o fim.

O g++ ajudou: o unique é marcado como nodiscard ("não descarte"), e ignorar o que ele devolve dá o aviso ignoring return value ("ignorando o valor de retorno"). Se aparecer esse aviso, quase certamente falta o erase. A receita completa, numa linha, é:

std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

8. std::transform: aplicar uma conta em cada elemento

O transform ("transformar") passa cada elemento por uma lambda e escreve o resultado em outro lugar (ou no mesmo):

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<double> precos = {10.0, 25.0, 4.0};
    std::vector<double> com_desconto(precos.size());

    std::transform(precos.begin(), precos.end(), com_desconto.begin(),
                   [](double p) { return p * 0.9; });

    for (double p : com_desconto) std::cout << p << ' ';
    std::cout << '\n';

    std::string nome = "ana maria";
    std::transform(nome.begin(), nome.end(), nome.begin(),
                   [](unsigned char c) { return std::toupper(c); });
    std::cout << nome << '\n';
}

$ g++ -std=c++23 -Wall -Wextra transformar.cpp -o transformar
$ ./transformar
9 22.5 3.6                           « 10% de desconto em cada preço
ANA MARIA

precos.begin(), precos.end()

De onde ler.

com_desconto.begin()

Onde começar a escrever. O destino precisa ter espaço: por isso o vetor foi criado com precos.size() elementos.

[](double p) { return p * 0.9; }

O que fazer com cada elemento.

nome.begin() como destino

No segundo exemplo, origem e destino são a mesma string: ela é transformada "no lugar". O unsigned char evita um problema do std::toupper com bytes de letras acentuadas (aula Caracteres).

9. std::any_of, std::all_of e std::none_of: perguntas de sim ou não

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

int main() {
    std::vector<int> notas = {7, 10, 4, 8, 6};
    auto aprovada = [](int n) { return n >= 6; };

    std::cout << std::boolalpha;
    std::cout << "Alguém passou?      " << std::any_of(notas.begin(), notas.end(), aprovada) << '\n';
    std::cout << "Todos passaram?     " << std::all_of(notas.begin(), notas.end(), aprovada) << '\n';
    std::cout << "Ninguém passou?     " << std::none_of(notas.begin(), notas.end(), aprovada) << '\n';
}

$ g++ -std=c++23 -Wall -Wextra perguntas.cpp -o perguntas
$ ./perguntas
Alguém passou?      true
Todos passaram?     false             « o 4 não passou
Ninguém passou?     false

Repare que a lambda foi guardada numa variável (aprovada) e reaproveitada nas três chamadas. Any = "algum", all = "todos", none = "nenhum". Eles param assim que sabem a resposta: o all_of desistiu no 4, sem olhar o resto.

Algoritmo ou for? Qual usar

Regra de bolso: se existe um algoritmo com o nome exato do que você quer fazer, use-o. Ele documenta a intenção e não tem o erro de "um a mais" do for com índice.

Quando dá errado

$ g++ -std=c++23 -Wall -Wextra sem_numeric.cpp -o sem_numeric
sem_numeric.cpp: In function ‘int main()’:
sem_numeric.cpp:6:23: error: ‘accumulate’ is not a member of ‘std’
    6 |     std::cout << std::accumulate(v.begin(), v.end(), 0) << '\n';
      |                       ^~~~~~~~~~

std::vector<int> v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 99);
std::cout << "Achei: " << *it << '\n';

$ ./fim
Achei: 0                             « 99 não existe; esse 0 é lixo da memória

$ ./vazio_max
Falha de segmentação     (imagem do núcleo gravada) ./vazio_max
$ echo $?
139

$ g++ -std=c++23 -Wall -Wextra lista_sort.cpp -o lista_sort
In file included from /usr/include/c++/15/algorithm:63,
                 from lista_sort.cpp:1:
/usr/include/c++/15/bits/stl_algo.h: In instantiation of ‘constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = _List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’:
/usr/include/c++/15/bits/stl_algo.h:4841:18:   required from ‘constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = _List_iterator<int>]’
 4841 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lista_sort.cpp:6:14:   required from here
    6 |     std::sort(numeros.begin(), numeros.end());
      |     ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/15/bits/stl_algo.h:1907:50: error: no match for ‘operator-’ (operand types are ‘std::_List_iterator<int>’ and ‘std::_List_iterator<int>’)
 1907 |                                 std::__lg(__last - __first) * 2,
      |                                           ~~~~~~~^~~~~~~~~
                                     « … e mais umas 15 linhas de notes

Referência rápida

Mais de cem outros (binary_search, fill, copy_if, remove_if, shuffle…) estão em Referência: Algoritmos.

Exercícios

Missão: o total do carrinho

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> precos = {2.5, 3.5, 1.25};
    double total = std::accumulate(precos.begin(), precos.end(), 0);
    std::cout << "Total: " << total << '\n';
}

#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> precos = {2.5, 3.5, 1.25};
    double total = std::accumulate(precos.begin(), precos.end(), 0.0);
    std::cout << "Total: " << total << '\n';
}

Missão final: o boletim da turma

Maior: 9.5
Média: 7.25
Aprovados: 3

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

int main() {
    std::vector<double> notas = {6.5, 9.5, 4.0, 9.0};

    // sua vez: maior, média e aprovados

}

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

int main() {
    std::vector<double> notas = {6.5, 9.5, 4.0, 9.0};

    auto maior = std::max_element(notas.begin(), notas.end());
    double soma = std::accumulate(notas.begin(), notas.end(), 0.0);
    double media = soma / notas.size();
    auto aprovados = std::count_if(notas.begin(), notas.end(), [](double n) {
        return n >= 6.0;
    });

    std::cout << "Maior: " << *maior << '\n';
    std::cout << "Média: " << media << '\n';
    std::cout << "Aprovados: " << aprovados << '\n';
}

Resumo

• Os algoritmos recebem um intervalo: v.begin(), v.end(). Estão em <algorithm>; accumulate está em <numeric>.
• std::sort ordena no lugar; com uma lambda (a, b) que diz "a vem antes de b?", você escolhe a ordem.
• find, find_if, min_element e max_element devolvem iteradores: compare com end() antes de usar *.
• count/count_if contam; any_of/all_of/none_of respondem sim ou não.
• accumulate soma no tipo do valor inicial: 0.0 para double, senão perde os decimais sem aviso.
• unique só junta vizinhos e não apaga: sort + unique + erase.
• transform aplica uma lambda em cada elemento; reverse inverte.
• Próxima aula: Ranges, a forma do C++20 que dispensa o begin/end e encadeia etapas.