Dominando os Algoritmos da Biblioteca Padrão C++

  1. Algoritmos de Leitura e Consulta

Esta categoria de algoritmos examina os elementos dentro de um intervalo sem alterar o estado do contêiner original.

1.1 Localização de Elementos (find)

  • std::find(inicio, fim, valor): Retorna um iterador para a primeira ocorrência de valor.
  • std::find_if(inicio, fim, predicado): Retorna um iterador para o primeiro elemento que satisfaça a condição lógica.
  • std::find_end(inicio, fim, sub_inicio, sub_fim): Localiza a última ocorrência de uma subsequência.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> historico = {10, 25, 30, 45, 50};

    // Busca por um valor exato
    auto ocorrencia = std::find(historico.begin(), historico.end(), 30);
    if (ocorrencia != historico.end()) {
        std::cout << "Valor localizado: " << *ocorrencia << "\n";
    }

    // Busca condicional
    auto primeiro_par = std::find_if(historico.begin(), historico.end(), [](int n) {
        return n % 2 == 0;
    });
    std::cout << "Primeiro par: " << *primeiro_par << "\n";

    return 0;
}

1.2 Contagem de Ocorrências (count)

  • std::count(inicio, fim, valor): Retorna a quantidade de elementos iguais a valor.
  • std::count_if(inicio, fim, predicado): Conta quantos elementos atendem a uma condição específica.
std::vector<char> sequencia = {'a', 'b', 'a', 'c', 'a'};
int total_a = std::count(sequencia.begin(), sequencia.end(), 'a'); // Resultado: 3

std::vector<int> notas = {8, 5, 9, 4, 7, 6};
int aprovados = std::count_if(notas.begin(), notas.end(), [](int nota) {
    return nota >= 6;
}); // Resultado: 4

1.3 Iteração com for_each

Aplica uma função ou functor a cada elemento no intervalo especificado.

std::vector<double> precos = {100.0, 250.0, 75.0};
// Aplicando um desconto de 10% em todos os itens
std::for_each(precos.begin(), precos.end(), [](double& preco) {
    preco *= 0.90;
});

1.4 Comparação de Sequências (equal e mismatch)

  • std::equal(inicio1, fim1, inicio2): Verifica se dois intervalos possuem os mesmos elementos na mesma ordem.
  • std::mismatch(inicio1, fim1, inicio2): Retorna um par de iteradores apontando para a primeira posição onde os intervalos divergem.
std::vector<int> config_a = {1, 2, 3};
std::vector<int> config_b = {1, 2, 4};

bool identico = std::equal(config_a.begin(), config_a.end(), config_b.begin()); // false

auto divergencia = std::mismatch(config_a.begin(), config_a.end(), config_b.begin());
std::cout << "Diferença: " << *divergencia.first << " vs " << *divergencia.second << "\n";

1.5 Validação de Condições Globais

  • std::all_of: Verdadeiro se todos os elementos satisfizerem o predicado.
  • std::any_of: Verdadeiro se pelo menos um elemento satisfizer o predicado.
  • std::none_of: Verdadeiro se nenhum elemento satisfizer o predicado.
std::vector<int> idades = {20, 25, 30, 18};
bool todos_maiores = std::all_of(idades.begin(), idades.end(), [](int i) { return i >= 18; }); // true
bool algum_idoso = std::any_of(idades.begin(), idades.end(), [](int i) { return i > 60; }); // false
  1. Algoritmos de Transformação e Mutação

Estes algoritmos alteram diretamente os valores ou a estrutura dos elementos dentro do contêiner.

2.1 Cópia de Dados (copy)

  • std::copy(inicio, fim, destino): Copia elementos para outro intervalo.
  • std::copy_if: Copia apenas os elementos que passam em um teste lógico.
std::vector<int> origem = {1, 2, 3, 4, 5};
std::vector<int> destino(5);
std::copy(origem.begin(), origem.end(), destino.begin());

std::vector<int> apenas_pares;
std::copy_if(origem.begin(), origem.end(), std::back_inserter(apenas_pares), [](int x) {
    return x % 2 == 0;
});

2.2 Transformação (transform)

Aplica uma operação e armazena o resultado, seja no próprio contêiner ou em um novo.

std::vector<int> celsius = {0, 20, 30};
std::vector<int> fahrenheit(celsius.size());

// Conversão de unidade
std::transform(celsius.begin(), celsius.end(), fahrenheit.begin(), [](int c) {
    return (c * 9/5) + 32;
});

2.3 Substituição (replace)

  • std::replace: Troca todas as ocorrências de um valor antigo por um novo.
  • std::replace_if: Substitui elementos com base em uma condição.
  • std::replace_copy: Realiza a substituição durante a cópia, preservando o original.
std::vector<int> status = {1, 0, 1, 0, 2};
// Troca 0 (inativo) por -1
std::replace(status.begin(), status.end(), 0, -1);

// Substitui valores negativos por 0
std::replace_if(status.begin(), status.end(), [](int s) { return s < 0; }, 0);

2.4 O Padrão Erase-Remove

Para remover elementos de um contêiner sequencial, usa-se std::remove seguido do método erase do contêiner.

std::vector<int> tokens = {1, 2, 3, 2, 4};
// Move os '2' para o final e retorna o novo iterador lógico de fim
auto novo_fim = std::remove(tokens.begin(), tokens.end(), 2);
// Redimensiona o contêiner fisicamente
tokens.erase(novo_fim, tokens.end());

2.5 Remoção de Duplicatas Consecutivas (unique)

Remove elementos duplicados que estejam adjacentes. Frequentemente usado após uma ordenação.

std::vector<int> dados = {1, 1, 2, 2, 2, 3};
auto fim_unico = std::unique(dados.begin(), dados.end());
dados.erase(fim_unico, dados.end()); // Resultado: {1, 2, 3}

2.6 Reorganização Geométrica

  • std::reverse: Inverte a ordem dos elementos.
  • std::rotate: Desloca os elementos de forma que um ponto médio se torne o início.
  • std::shuffle: Randomiza a posição dos elementos usando um gerador de números aleatórios.
std::vector<int> fila = {1, 2, 3, 4, 5};
std::rotate(fila.begin(), fila.begin() + 2, fila.end()); // Resultado: {3, 4, 5, 1, 2}

std::random_device rd;
std::mt19937 gerador(rd());
std::shuffle(fila.begin(), fila.end(), gerador);
  1. Ordenação e Busca Binária

3.1 Estratégias de Ordenação

  • std::sort: Ordenação rápida (Introsort), não garante estabilidade.
  • std::stable_sort: Ordenação estável (Mergesort), preserva a ordem relativa de elementos equivalentes.
  • std::partial_sort: Ordena apenas os primeiros N elementos menores/maiores.
std::vector<int> ranking = {50, 20, 40, 10, 30};
std::sort(ranking.begin(), ranking.end(), std::greater<int>()); // Ordem decrescente

std::vector<std::pair<int, std::string>> usuarios = {{2, "B"}, {1, "A"}, {2, "C"}};
std::stable_sort(usuarios.begin(), usuarios.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
}); // Mantém "B" antes de "C" pois ambos têm ID 2

3.2 Seleção Rápida (nth_element)

Reorganiza o intervalo de modo que o elemento na posição especificada seja exatamente o que estaria lá se o intervalo estivesse ordenado. Os elementos à esquerda são menores e à direita são maiores.

std::vector<int> metricas = {9, 1, 8, 2, 7, 3};
// Encontra a mediana (ou o 3º menor elemento)
std::nth_element(metricas.begin(), metricas.begin() + 2, metricas.end());

3.3 Busca em Intervalos Ordenados

Estes algoritmos exigem que o contêiner esteja previamente ordenado.

  • std::binary_search: Verifica a existência de um valor.
  • std::lower_bound: Encontra o primeiro elemento maior ou igual ao valor.
  • std::upper_bound: Encontra o primeiro elemento estritamente maior que o valor.
std::vector<int> indice = {10, 20, 20, 30, 40};
bool existe = std::binary_search(indice.begin(), indice.end(), 20);

auto primeiro_20 = std::lower_bound(indice.begin(), indice.end(), 20);
auto primeiro_maior_20 = std::upper_bound(indice.begin(), indice.end(), 20);

3.4 Fusão de Dados (merge)

Combina dois intervalos já ordenados em um terceiro, mantendo a ordenação.

std::vector<int> lote_a = {1, 3, 5};
std::vector<int> lote_b = {2, 4, 6};
std::vector<int> consolidado(lote_a.size() + lote_b.size());

std::merge(lote_a.begin(), lote_a.end(), lote_b.begin(), lote_b.end(), consolidado.begin());
  1. Manipulação de Heap

Permite tratar um contêiner sequencial como uma árvore binária heap (geralmente max-heap).

std::vector<int> tarefas = {3, 1, 4, 1, 5};
std::make_heap(tarefas.begin(), tarefas.end()); // Cria um max-heap

tarefas.push_back(9);
std::push_heap(tarefas.begin(), tarefas.end()); // Insere o 9 mantendo a propriedade do heap

std::pop_heap(tarefas.begin(), tarefas.end()); // Move o maior elemento para o final
int prioridade_maxima = tarefas.back();
tarefas.pop_back(); // Remove o elemento do contêiner
  1. Extração de Valores Extremos

5.1 Mínimos e Máximos

  • std::min / std::max: Comparam dois valores ou uma lista de inicialização.
  • std::min_element / std::max_element: Retornam iteradores para os extremos em um intervalo.
  • std::minmax_element: Retorna um par de iteradores (min, max) em uma única passagem.
std::vector<double> latencia = {12.5, 8.2, 15.1, 9.0};
auto [minima, maxima] = std::minmax_element(latencia.begin(), latencia.end());
std::cout << "Min: " << *minima << ", Max: " << *maxima << "\n";
  1. Operações Numéricas (<numeric>)

6.1 Acumulação e Produtos Internos

  • std::accumulate: Calcula a soma (ou outra operação binária) de um intervalo.
  • std::inner_product: Calcula o produto escalar entre dois intervalos.
#include <numeric>

std::vector<int> valores = {1, 2, 3, 4};
int soma_total = std::accumulate(valores.begin(), valores.end(), 0);

std::vector<int> pesos = {2, 2, 2, 2};
int soma_ponderada = std::inner_product(valores.begin(), valores.end(), pesos.begin(), 0);

6.2 Geração e Diferenciação

  • std::iota: Preenche o intervalo com valores sequenciais incrementais.
  • std::partial_sum: Calcula a soma cumulativa (prefix sum).
  • std::adjacent_difference: Calcula a diferença entre elementos adjacentes.
std::vector<int> ids(5);
std::iota(ids.begin(), ids.end(), 100); // 100, 101, 102, 103, 104

std::vector<int> transacoes = {10, 20, 30};
std::vector<int> saldo(3);
std::partial_sum(transacoes.begin(), transacoes.end(), saldo.begin()); // 10, 30, 60
  1. Geração e Teoria dos Conjuntos

7.1 Preenchimento com Funções (generate)

Atribui valores a um intervalo baseando-se no retorno de uma função geradora.

std::vector<int> sequencia(5);
int contador = 0;
std::generate(sequencia.begin(), sequencia.end(), [&contador]() {
    return contador += 5; // 5, 10, 15, 20, 25
});

7.2 Operações de Conjuntos

Requer que ambos os intervalos de entrada estejam ordenados.

  • std::includes: Verifica se um conjunto é subconjunto de outro.
  • std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference: Executam as operações matemáticas clássicas de conjuntos.
std::vector<int> grupo_a = {1, 2, 3, 4};
std::vector<int> grupo_b = {3, 4, 5, 6};
std::vector<int> resultado;

std::set_intersection(grupo_a.begin(), grupo_a.end(), 
                      grupo_b.begin(), grupo_b.end(), 
                      std::back_inserter(resultado)); // Resultado: {3, 4}
  1. Dúvidas Comuns e Boas Práticas

Qual a diferença prática entre std::sort e std::stable_sort?

O std::sort utiliza o algoritmo Introsort, que é extremamente rápido (complexidade O(n log n)), mas não garante que elementos com chaves idênticas mantenham sua ordem original de inserção. O std::stable_sort utiliza uma variação do Mergesort, garantindo a estabilidade (ordem relativa preservada), mas geralmente exige alocação de memória extra (complexidade de espaço O(n)).

Por que o std::remove não diminui o tamanho do contêiner?

Os algoritmos da biblioteca padrão operam em iteradores e não têm conhecimento sobre a estrutura do contêiner subjacente. O std::remove apenas desloca os elementos não-removidos para o início do intervalo e retorna um novo iterador de "fim lógico". Para liberar a memória e alterar o tamanho real do contêiner, é obrigatório chamar o método erase do contêiner passando esse novo iterador de fim, consolidando o padrão Erace-Remove.

Quais algoritmos exigem que o contêiner esteja ordenado previamente?

Algoritmos que utilizam busca binária ou mesclagem dependem da propriedade de ordenação para funcionar corretamente e manter sua complexidade de tempo otimizada. Isso inclui a família binary_search, lower_bound, upper_bound, além de todas as operações de conjuntos (set_union, set_intersection, etc.) e o std::merge.

Tags: C++ STL Algoritmos programação-genérica Biblioteca-Padrao

Publicado em 6-26 16:27

Tags em Destaque

©2026 Doido Dev