C++ Algoritmos

A biblioteca padrão do C++ traz dezenas de algoritmos prontos: funções que ordenam, procuram, contam, somam, copiam e apagam itens de uma coleção. Esta página é uma consulta rápida: cada linha tem a forma de chamar (simplificada), o que a função faz, um exemplo e o resultado real, conferido com o g++ 15 na máquina da Ana. Para aprender com calma, veja as aulas Algoritmos, Iteradores, Lambdas e Ranges.

Atalhos: Cabeçalhos · Ordenar · Procurar · Contar e testar · Mínimo e máximo · Somar e acumular · Transformar, copiar, preencher · Remover · Busca binária · std::ranges · Views · Armadilhas

A ideia: uma caixa de ferramentas

Imagine que a Ana tem uma pilha de provas para corrigir. Ela pode inventar, toda vez, um jeito de pôr as provas em ordem, achar a maior nota ou contar quantos passaram. Ou pode abrir a caixa de ferramentas da escola, onde já existe uma ferramenta pronta para cada tarefa, testada por milhares de pessoas.

Os algoritmos são essa caixa. Em vez de escrever um laço for para achar o maior número, você chama std::max_element. O código fica menor, diz o que faz (e não só como) e tem menos chance de erro.

Um programa completo, com quatro algoritmos:

#include <algorithm>   // sort, count, max_element...
#include <iostream>
#include <numeric>     // accumulate
#include <vector>

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

    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';

    std::cout << "quantos 3: " << std::count(v.begin(), v.end(), 3) << '\n';
    std::cout << "soma: " << std::accumulate(v.begin(), v.end(), 0) << '\n';
    std::cout << "maior: " << *std::max_element(v.begin(), v.end()) << '\n';
}

$ g++ -std=c++23 -Wall -Wextra exemplo.cpp -o exemplo
$ ./exemplo
1 3 3 5 8
quantos 3: 2
soma: 20
maior: 8

#include <algorithm>

Traz a maioria dos algoritmos: sort, find, count, max_element… Inclua sempre. Às vezes o programa compila sem ele, porque outro cabeçalho o traz "de carona" (no g++ 15, um programa só com <iostream> e <vector> aceitou o std::sort), mas isso não é garantido e pode quebrar em outro compilador.

#include <numeric>

Traz os algoritmos "de conta": accumulate, reduce, iota.

std::sort(v.begin(), v.end())

Ordena do começo ao fim, do menor para o maior. Muda o próprio vetor.

std::count(v.begin(), v.end(), 3)

Conta quantos itens são iguais a 3. Não muda nada.

std::accumulate(…, 0)

Soma tudo, começando do valor inicial 0.

*std::max_element(…)

max_element devolve um iterador que aponta o maior; o * pega o valor que está lá.

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

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

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

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

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

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

    std::sort(v.begin(), v.end(), std::greater<>());

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

Cabeçalhos: onde mora cada um

Ordenar

Texto é ordenado pelo código de cada letra: maiúsculas vêm antes das minúsculas, e letras acentuadas vão para o fim. Ordenando {"uva", "Maçã", "banana", "abacaxi"} com std::ranges::sort, o resultado é ["Maçã", "abacaxi", "banana", "uva"]. Veja Acentos e UTF-8.

Procurar

Contar e testar

O count funciona também em texto: std::ranges::count(std::string{"banana"}, 'a') dá 3.

Mínimo e máximo

Somar e acumular (<numeric>)

Média de notas: some com 0.0 e divida pela quantidade. Com std::vector<double> notas{9.5, 7.0, 8.5};, std::accumulate(notas.begin(), notas.end(), 0.0) / notas.size() dá 8.333333333333334.

Transformar, copiar e preencher

Remover itens

Aqui mora a maior surpresa da biblioteca: std::remove e std::unique não apagam nada. Eles só empurram os itens que ficam para a frente e devolvem um iterador para o "novo fim"; o tamanho do vetor continua o mesmo, e o que sobra depois do novo fim é lixo. Quem apaga de verdade é o método erase do vetor. Desde o C++20, std::erase e std::erase_if fazem tudo numa linha só.

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

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

    // escreva aqui a linha que tira todos os 3

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

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

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

    std::erase(v, 3);

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

Busca binária (só em coleções ordenadas)

Num vetor ordenado, dá para achar um valor muito mais rápido: olha-se o meio, descarta-se a metade em que ele não pode estar, e repete-se. É como procurar uma palavra no dicionário. Os exemplos abaixo usam o vetor já ordenado [1, 3, 3, 5, 8].

A família std::ranges C++20

Desde o C++20, quase todo algoritmo tem uma versão em std::ranges:: que recebe o container inteiro, sem begin()/end(). Ela também aceita uma projeção: o campo pelo qual comparar. E dá mensagens de erro mais diretas quando o container não serve. Veja a aula Ranges.

Projeção: com struct Aluno { std::string nome; int nota; }; e a turma {Caio 8, Ana 9, Bia 8, Davi 9}:

Views: filtrar e transformar sem copiar C++20

Uma view ("visão") é uma janela sobre a coleção: ela mostra os itens de outro jeito (só os pares, multiplicados por 10, de trás para a frente) sem copiar nem mudar o original. Os itens só são calculados quando alguém percorre a view (ela é "preguiçosa"). As views se encadeiam com a barra |, como canos. Ficam em <ranges>.

Encadeando: os itens maiores que 2, multiplicados por 10, depois de ordenar. Repare que, nas views, a ordem da leitura é a ordem em que as coisas acontecem.

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

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

    std::ranges::sort(v);

    auto grandes = v | std::views::filter([](int x) { return x > 2; })
                     | std::views::transform([](int x) { return x * 10; });

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

$ g++ -std=c++23 -Wall -Wextra views.cpp -o views
$ ./views
30 30 50 80

Armadilhas (resultados reais)

$ g++ -std=c++23 -Wall -Wextra rem.cpp -o rem
rem.cpp: In function ‘int main()’:
rem.cpp:7:16: warning: ignoring return value of ‘constexpr _FIter std::remove(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Tp = int]’, declared with attribute ‘nodiscard’ [-Wunused-result]
    7 |     std::remove(v.begin(), v.end(), 3);
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/15/algorithm:63,
                 from rem.cpp:1:
/usr/include/c++/15/bits/stl_algo.h:772:5: note: declared here
  772 |     remove(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~

#include <algorithm>
#include <list>

int main() {
    std::list<int> l{5, 3, 8};
    std::sort(l.begin(), l.end());
}

$ g++ -std=c++23 -Wall -Wextra lista.cpp -o lista
In file included from /usr/include/c++/15/algorithm:63,
                 from lista.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.cpp:6:14:   required from here
    6 |     std::sort(l.begin(), l.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,
      |                                           ~~~~~~~^~~~~~~~~
«  … mais 20 linhas de "note: candidate" …

Exercícios

Missão final: o boletim da turma

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

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

    // 1. conte as notas maiores ou iguais a 7 com std::count_if
    int aprovados = 0;

    // 2. ache a maior nota com std::max_element
    int maior = 0;

    // 3. some todas as notas com std::accumulate
    int soma = 0;

    std::cout << "aprovados: " << aprovados << '\n';
    std::cout << "maior: " << maior << '\n';
    std::cout << "soma: " << soma << '\n';
}

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

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

    // 1. conte as notas maiores ou iguais a 7 com std::count_if
    auto aprovados = std::count_if(notas.begin(), notas.end(),
                                   [](int n) { return n >= 7; });

    // 2. ache a maior nota com std::max_element
    int maior = *std::max_element(notas.begin(), notas.end());

    // 3. some todas as notas com std::accumulate
    int soma = std::accumulate(notas.begin(), notas.end(), 0);

    std::cout << "aprovados: " << aprovados << '\n';
    std::cout << "maior: " << maior << '\n';
    std::cout << "soma: " << soma << '\n';
}

Resumo

• Os algoritmos ficam em <algorithm> (quase todos) e <numeric> (accumulate, reduce, iota); as views, em <ranges>.
• Forma clássica: algoritmo(v.begin(), v.end(), …). Forma C++20: std::ranges::algoritmo(v, …).
• find, min_element, max_element e lower_bound devolvem iteradores: compare com v.end() antes de usar *.
• remove e unique não apagam: use std::erase/std::erase_if (C++20) ou a dupla erase-remove. unique só junta vizinhos.
• binary_search, lower_bound e upper_bound só funcionam em coleções ordenadas.
• No accumulate, o tipo do valor inicial manda: 0.0 para somar double.
• Views (filter, transform, take…) mostram os itens de outro jeito sem copiar nem mudar o original.