Guia Abrangente de Algoritmos da Standard Template Library (STL) em C++

A Standard Template Library (STL) do C++ oferece um vasto conjunto de algoritmos genéricos que operam em diferentes tipos de containers, utilizando iteradores para abstrair a estrutura de dados subjacente. Esses algoritmos são poderosos e otimizados, permitindo aos desenvolvedores realizar operações complexas de forma concisa e eficiente. Este guia explora as categorias principais de algoritmos da STL, apresentando exemplos práticos para ilustrar seu uso.

Algoritmos de Sequência Não Modificadores

Esta categoria de algoritmos examina elementos em um intervalo sem alterar seu conteúdo.

1. Busca: std::find, std::find_if, std::find_end

  • std::find(inicio, fim, valor): Localiza a primeira ocorrência de valor. Retorna um iterador para o elemento ou fim se não encontrado.
  • std::find_if(inicio, fim, predicado): Encontra o primeiro elemento que satisfaz a condição definida pelo predicado (uma função ou lambda).
  • std::find_end(inicio, fim, sub_inicio, sub_fim): Busca a última ocorrência de uma subsequência dentro de um intervalo.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numeros = {10, 20, 30, 40, 50, 20};

    // Procurar o valor 30
    auto it_val = std::find(numeros.begin(), numeros.end(), 30);
    if (it_val != numeros.end()) {
        std::cout << "Valor 30 encontrado: " << *it_val << std::endl; // Saída: 30
    }

    // Procurar o primeiro elemento menor que 25
    auto it_pred = std::find_if(numeros.begin(), numeros.end(), [](int x) {
        return x < 25;
    });
    std::cout << "Primeiro < 25: " << *it_pred << std::endl; // Saída: 10

    // Procurar a última ocorrência da subsequência {20}
    std::vector<int> sub_seq = {20};
    auto it_sub = std::find_end(numeros.begin(), numeros.end(), sub_seq.begin(), sub_seq.end());
    if (it_sub != numeros.end()) {
        std::cout << "Subsequencia {20} encontrada no indice: " << std::distance(numeros.begin(), it_sub) << std::endl; // Saída: 5
    }
    return 0;
}

2. Contagem: std::count, std::count_if

  • std::count(inicio, fim, valor): Retorna o número de elementos iguais a valor no intervalo.
  • std::count_if(inicio, fim, predicado): Retorna a contagem de elementos que satisfazem o predicado.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> dados = {7, 1, 3, 7, 5, 7, 9};
    int contagem_sete = std::count(dados.begin(), dados.end(), 7); 
    std::cout << "Quantidade de 7s: " << contagem_sete << std::endl; // Saída: 3

    int contagem_impares = std::count_if(dados.begin(), dados.end(), [](int n) { 
        return n % 2 != 0; 
    }); 
    std::cout << "Quantidade de impares: " << contagem_impares << std::endl; // Saída: 6
    return 0;
}

3. Iteração: std::for_each

Aplica uma função (ou objeto de função) a cada elemento dentro de um intervalo.

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

int main() {
    std::vector<int> valores = {1, 2, 3, 4};
    std::cout << "Valores originais: ";
    for (int v : valores) { std::cout << v << " "; }
    std::cout << std::endl;

    std::for_each(valores.begin(), valores.end(), [](int& x) { 
        x += 10; // Adiciona 10 a cada elemento
    });
    std::cout << "Valores apos for_each: ";
    for (int v : valores) { std::cout << v << " "; } // Saída: 11 12 13 14
    std::cout << std::endl;
    return 0;
}

4. Comparação de Intervalos: std::equal e std::mismatch

  • std::equal(b1, e1, b2): Verifica se dois intervalos são idênticos.
  • std::mismatch(b1, e1, b2): Retorna um par de iteradores apontando para o primeiro par de elementos diferentes.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> // Para std::pair

int main() {
    std::vector<int> arrA = {10, 20, 30};
    std::vector<int> arrB = {10, 20, 35};
    std::vector<int> arrC = {10, 20, 30};

    bool sao_iguais = std::equal(arrA.begin(), arrA.end(), arrC.begin());
    std::cout << "ArrA == ArrC? " << std::boolalpha << sao_iguais << std::endl; // Saída: true

    auto dif = std::mismatch(arrA.begin(), arrA.end(), arrB.begin());
    if (dif.first != arrA.end()) {
        std::cout << "Primeira diferenca: " << *dif.first << " em ArrA vs " << *dif.second << " em ArrB" << std::endl; // Saída: 30 vs 35
    }
    return 0;
}

5. Verificação de Propriedades: std::all_of, std::any_of, std::none_of (C++11)

Verificam se todos, pelo menos um ou nenhum dos elementos de um intervalo satisfazem um predicado.

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

int main() {
    std::vector<int> positivos = {10, 20, 30, 40};
    
    bool todos_positivos = std::all_of(positivos.begin(), positivos.end(), [](int x) { 
        return x > 0; 
    }); 
    std::cout << "Todos > 0? " << std::boolalpha << todos_positivos << std::endl; // Saída: true

    bool algum_div_tres = std::any_of(positivos.begin(), positivos.end(), [](int x) { 
        return x % 3 == 0; 
    }); 
    std::cout << "Algum divisivel por 3? " << std::boolalpha << algum_div_tres << std::endl; // Saída: true (30)

    bool nenhum_negativo = std::none_of(positivos.begin(), positivos.end(), [](int x) { 
        return x < 0; 
    }); 
    std::cout << "Nenhum negativo? " << std::boolalpha << nenhum_negativo << std::endl; // Saída: true
    return 0;
}

Algoritmos de Sequência Modificadores

Estes algoritmos alteram a ordem ou os valores dos elementos no intervalo em que operam.

1. Cópia: std::copy, std::copy_if

  • std::copy(inicio, fim, destino): Copia elementos para um novo local.
  • std::copy_if(inicio, fim, destino, predicado): Copia elementos que satisfazem um predicado.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator> // Para std::back_inserter

int main() {
    std::vector<int> fonte = {10, 11, 12, 13, 14};
    std::vector<int> destino(5); // Deve ter espaço suficiente ou usar back_inserter

    // Copia todos os elementos
    std::copy(fonte.begin(), fonte.end(), destino.begin());
    std::cout << "Destino (todos): ";
    for (int v : destino) { std::cout << v << " "; } // Saída: 10 11 12 13 14
    std::cout << std::endl;

    // Copia apenas os elementos ímpares
    std::vector<int> impares;
    std::copy_if(fonte.begin(), fonte.end(), std::back_inserter(impares), [](int x) {
        return x % 2 != 0;
    });
    std::cout << "Impares: ";
    for (int v : impares) { std::cout << v << " "; } // Saída: 11 13
    std::cout << std::endl;
    return 0;
}

2. Transformação: std::transform

Aplica uma função a cada elemento de um intervalo e armazena os resultados em outro intervalo. Pode ser unário ou binário.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // Para std::multiplies

int main() {
    std::vector<int> entrada = {2, 3, 4};
    std::vector<int> cubos(entrada.size());

    // Calcula o cubo de cada elemento (transformação unária)
    std::transform(entrada.begin(), entrada.end(), cubos.begin(), [](int x) {
        return x * x * x;
    });
    std::cout << "Cubos: ";
    for (int v : cubos) { std::cout << v << " "; } // Saída: 8 27 64
    std::cout << std::endl;

    // Multiplica elementos de duas coleções (transformação binária)
    std::vector<int> vA = {1, 2, 3};
    std::vector<int> vB = {5, 6, 7};
    std::vector<int> produto(vA.size());
    std::transform(vA.begin(), vA.end(), vB.begin(), produto.begin(), std::multiplies<int>());
    std::cout << "Produtos: ";
    for (int v : produto) { std::cout << v << " "; } // Saída: 5 12 21
    std::cout << std::endl;
    return 0;
}

3. Substituição: std::replace, std::replace_if, std::replace_copy

  • std::replace(b, e, old_val, new_val): Substitui todas as ocorrências de old_val por new_val.
  • std::replace_if(b, e, predicado, new_val): Substitui elementos que satisfazem o predicado.
  • std::replace_copy(b, e, dest, old_val, new_val): Copia elementos, substituindo os valores, sem modificar o original.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> dados_rep = {10, 60, 10, 70, 10, 80};

    // Substitui todos os 10s por 99
    std::replace(dados_rep.begin(), dados_rep.end(), 10, 99);
    std::cout << "Apos replace (10 -> 99): ";
    for (int v : dados_rep) { std::cout << v << " "; } // Saída: 99 60 99 70 99 80
    std::cout << std::endl;

    // Substitui elementos maiores que 50 por 0
    std::replace_if(dados_rep.begin(), dados_rep.end(), [](int x) {
        return x > 50;
    }, 0);
    std::cout << "Apos replace_if (>50 -> 0): ";
    for (int v : dados_rep) { std::cout << v << " "; } // Saída: 99 0 99 0 99 0
    std::cout << std::endl;

    // Copia substituindo 99 por 1000 (origem inalterada)
    std::vector<int> copia_substituida;
    std::replace_copy(dados_rep.begin(), dados_rep.end(), std::back_inserter(copia_substituida), 99, 1000);
    std::cout << "Copia substituida: ";
    for (int v : copia_substituida) { std::cout << v << " "; } // Saída: 1000 0 1000 0 1000 0
    std::cout << std::endl;
    return 0;
}

4. Remoção: std::remove, std::remove_if e erase

  • std::remove(inicio, fim, valor): Move todos os elementos iguais a valor para o final do intervalo e retorna um iterador para o novo "final lógico". Não reduz o tamanho do container.
  • std::remove_if(inicio, fim, predicado): Similar a remove, mas com base em um predicado.
  • Para remover fisicamente os elementos e redimensionar o container, é necessário combinar remove ou remove_if com o método erase do container.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int main() {
    std::vector<char> caracteres = {'a', 'b', 'c', 'b', 'd', 'b'};

    // Remove logicamente 'b's (move para o final)
    auto novo_fim = std::remove(caracteres.begin(), caracteres.end(), 'b');
    std::cout << "Apos remove (logico): ";
    for (char c : caracteres) { std::cout << c << " "; } // Saída: a c d b b b (tamanho ainda 6)
    std::cout << std::endl;

    // Remove fisicamente os elementos extra
    caracteres.erase(novo_fim, caracteres.end());
    std::cout << "Apos erase (fisico): ";
    for (char c : caracteres) { std::cout << c << " "; } // Saída: a c d (tamanho 3)
    std::cout << std::endl;

    // Exemplo combinado: remover vogais
    std::vector<char> letras = {'m', 'a', 'p', 'e', 'l', 'o', 'r'};
    letras.erase(std::remove_if(letras.begin(), letras.end(), [](char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }), letras.end());
    std::cout << "Apos remover vogais: ";
    for (char ch : letras) { std::cout << ch << " "; } // Saída: m p l r
    std::cout << std::endl;
    return 0;
}

5. Unicidade: std::unique

Remove elementos duplicados consecutivos de um intervalo. Retorna um iterador para o novo final lógico. Assim como remove, precisa ser combinado com erase para reduzir o tamanho físico.

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

int main() {
    std::vector<std::string> palavras = {"azul", "azul", "vermelho", "verde", "verde", "verde", "amarelo"};
    
    // Remove duplicados consecutivos
    auto ultimo = std::unique(palavras.begin(), palavras.end());
    palavras.erase(ultimo, palavras.end()); 
    std::cout << "Apos unique: ";
    for (const std::string& p : palavras) { std::cout << p << " "; } // Saída: azul vermelho verde amarelo
    std::cout << std::endl;
    return 0;
}

6. Reversão: std::reverse

Inverte a ordem dos elementos em um intervalo.

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

int main() {
    std::vector<double> precos = {10.5, 20.0, 35.7, 5.0};
    std::cout << "Precos originais: ";
    for (double p : precos) { std::cout << p << " "; }
    std::cout << std::endl;

    std::reverse(precos.begin(), precos.end()); 
    std::cout << "Precos invertidos: ";
    for (double p : precos) { std::cout << p << " "; } // Saída: 5 35.7 20 10.5
    std::cout << std::endl;
    return 0;
}

7. Rotação: std::rotate

Rotaciona os elementos em um intervalo de forma que o elemento apontado por meio se torne o novo primeiro elemento.

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

int main() {
    std::vector<int> sequencia = {10, 20, 30, 40, 50};
    std::cout << "Sequencia original: ";
    for (int v : sequencia) { std::cout << v << " "; }
    std::cout << std::endl;

    // Rotaciona a sequencia, com 30 como novo primeiro elemento
    std::rotate(sequencia.begin(), sequencia.begin() + 2, sequencia.end()); // +2 significa que o elemento no índice 2 (30) será o novo começo
    std::cout << "Sequencia rotacionada: ";
    for (int v : sequencia) { std::cout << v << " "; } // Saída: 30 40 50 10 20
    std::cout << std::endl;
    return 0;
}

8. Embaralhamento: std::shuffle (C++11)

Reorganiza aleatoriamente os elementos em um intervalo. Requer um gerador de números aleatórios.

#include <iostream>
#include <vector>
#include <algorithm>
#include <random> // Para std::random_device e std::mt19937

int main() {
    std::vector<int> itens = {1, 2, 3, 4, 5, 6, 7};
    std::cout << "Itens originais: ";
    for (int i : itens) { std::cout << i << " "; }
    std::cout << std::endl;

    std::random_device rd;
    std::mt19937 g(rd()); // Gerador de números aleatórios
    std::shuffle(itens.begin(), itens.end(), g); 
    std::cout << "Itens embaralhados: ";
    for (int i : itens) { std::cout << i << " "; } // Saída: Sequência aleatória
    std::cout << std::endl;
    return 0;
}

Algoritmos de Ordenação e Relacionados

Esses algoritmos são usados para organizar elementos em uma ordem específica ou para operar em intervalos ordenados.

1. Ordenação: std::sort, std::stable_sort, std::partial_sort

  • std::sort(inicio, fim): Ordena um intervalo. É geralmente uma implementação de introsort (híbrido de quicksort, heapsort e insertion sort), instável, com complexidade O(N log N).
  • std::stable_sort(inicio, fim): Ordena um intervalo, mantendo a ordem relativa de elementos iguais. Geralmente usa mergesort, estável, com complexidade O(N log N).
  • std::partial_sort(inicio, meio, fim): Ordena os meio - inicio menores elementos e os coloca na parte inicial do intervalo.
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // Para std::greater
#include <string>
#include <tuple>    // Para std::tuple e std::get

int main() {
    std::vector<int> desordenados = {8, 2, 6, 1, 9, 3};
    std::sort(desordenados.begin(), desordenados.end()); // Ordem crescente padrão
    std::cout << "Sort crescente: ";
    for (int v : desordenados) { std::cout << v << " "; } // Saída: 1 2 3 6 8 9
    std::cout << std::endl;

    std::sort(desordenados.begin(), desordenados.end(), std::greater<int>()); // Ordem decrescente
    std::cout << "Sort decrescente: ";
    for (int v : desordenados) { std::cout << v << " "; } // Saída: 9 8 6 3 2 1
    std::cout << std::endl;

    // Exemplo de stable_sort (mantém ordem relativa para elementos iguais)
    std::vector<std::tuple<int, char>> pessoas = {{2, 'B'}, {1, 'A'}, {2, 'C'}, {1, 'D'}};
    std::stable_sort(pessoas.begin(), pessoas.end(), [](const auto& p1, const auto& p2) {
        return std::get<0>(p1) < std::get<0>(p2);
    });
    std::cout << "Stable Sort (por idade): ";
    for (const auto& p : pessoas) { std::cout << "(" << std::get<0>(p) << "," << std::get<1>(p) << ") "; } 
    // Saída: (1,A) (1,D) (2,B) (2,C) - 'A' vem antes de 'D', 'B' antes de 'C'
    std::cout << std::endl;

    std::vector<int> todos_elementos = {10, 5, 20, 15, 30, 25};
    // Coloca os 3 menores elementos no início e os ordena
    std::partial_sort(todos_elementos.begin(), todos_elementos.begin() + 3, todos_elementos.end());
    std::cout << "Partial Sort (primeiros 3): ";
    for (int v : todos_elementos) { std::cout << v << " "; } // Saída: 5 10 15 30 25 20 (os 3 primeiros estão ordenados)
    std::cout << std::endl;
    return 0;
}

2. Particionamento: std::nth_element

Reorganiza um intervalo de modo que o elemento na posição n-ésima seja o mesmo que estaria nessa posição se o intervalo estivesse completamente ordenado. Todos os elementos antes dessa posição são menores ou iguais a ele, e todos os elementos depois são maiores ou iguais. Não ordena os outros elementos.

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

int main() {
    std::vector<int> amostra = {9, 1, 7, 3, 5, 2, 8};
    // Encontrar o 3º menor elemento (índice 2)
    std::nth_element(amostra.begin(), amostra.begin() + 2, amostra.end());
    std::cout << "Elemento na 3a posicao (ordenado): " << amostra[2] << std::endl; // Saída: 3
    std::cout << "Colecao apos nth_element: ";
    for (int v : amostra) { std::cout << v << " "; } // Ex: 1 2 3 9 5 7 8 (elementos à esquerda <=3, à direita >=3)
    std::cout << std::endl;
    return 0;
}

3. Busca em Intervalos Ordenados: std::binary_search, std::lower_bound, std::upper_bound

Esses algoritmos exigem que o intervalo de entrada esteja previamente ordenado.

  • std::binary_search(inicio, fim, valor): Verifica se valor existe no intervalo (retorna bool).
  • std::lower_bound(inicio, fim, valor): Retorna um iterador para o primeiro elemento que não é menor que valor.
  • std::upper_bound(inicio, fim, valor): Retorna um iterador para o primeiro elemento que é maior que valor.
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> ordenado = {10, 20, 20, 30, 40, 50}; // Deve estar ordenado

    bool existe = std::binary_search(ordenado.begin(), ordenado.end(), 20);
    std::cout << "O valor 20 existe? " << std::boolalpha << existe << std::endl; // Saída: true

    auto lb = std::lower_bound(ordenado.begin(), ordenado.end(), 20);
    std::cout << "lower_bound para 20 no indice: " << std::distance(ordenado.begin(), lb) << std::endl; // Saída: 1 (aponta para o primeiro 20)

    auto ub = std::upper_bound(ordenado.begin(), ordenado.end(), 20);
    std::cout << "upper_bound para 20 no indice: " << std::distance(ordenado.begin(), ub) << std::endl; // Saída: 3 (aponta para 30)
    return 0;
}

4. Combinação: std::merge

Combina dois intervalos ordenados em um terceiro intervalo, também ordenado.

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

int main() {
    std::vector<int> lista1 = {1, 3, 7};
    std::vector<int> lista2 = {2, 4, 6};
    std::vector<int> resultado_merge(lista1.size() + lista2.size());

    std::merge(lista1.begin(), lista1.end(), lista2.begin(), lista2.end(), resultado_merge.begin());
    std::cout << "Listas combinadas: ";
    for (int v : resultado_merge) { std::cout << v << " "; } // Saída: 1 2 3 4 6 7
    std::cout << std::endl;
    return 0;
}

Algoritmos de Heap

A STL oferece funções para manipular um intervalo como uma estrutura de dados de heap (pilha), tipicamente um max-heap por padrão, onde o maior elemento está sempre no início.

#include <iostream>
#include <vector>
#include <algorithm> // Contém os algoritmos de heap

int main() {
    std::vector<int> elementos_heap = {9, 3, 6, 2, 8};
    std::cout << "Original: ";
    for (int v : elementos_heap) { std::cout << v << " "; }
    std::cout << std::endl;

    std::make_heap(elementos_heap.begin(), elementos_heap.end()); // Transforma em max-heap
    std::cout << "Apos make_heap: ";
    for (int v : elementos_heap) { std::cout << v << " "; } // Saída (exemplo): 9 8 6 2 3
    std::cout << std::endl;

    elementos_heap.push_back(10); // Adiciona um novo elemento
    std::push_heap(elementos_heap.begin(), elementos_heap.end()); // Reorganiza para manter a propriedade de heap
    std::cout << "Apos push_heap(10): ";
    for (int v : elementos_heap) { std::cout << v << " "; } // Saída (exemplo): 10 9 6 2 8 3
    std::cout << std::endl;

    std::pop_heap(elementos_heap.begin(), elementos_heap.end()); // Move o maior elemento para o final
    int maior_elemento = elementos_heap.back(); // Pega o maior
    elementos_heap.pop_back(); // Remove o maior do heap (ele está no final)
    std::cout << "Maior elemento: " << maior_elemento << std::endl; // Saída: 10
    std::cout << "Heap apos pop_heap: ";
    for (int v : elementos_heap) { std::cout << v << " "; } // Saída (exemplo): 9 8 6 2 3
    std::cout << std::endl;

    std::sort_heap(elementos_heap.begin(), elementos_heap.end()); // Transforma o heap em uma coleção ordenada
    std::cout << "Apos sort_heap: ";
    for (int v : elementos_heap) { std::cout << v << " "; } // Saída: 2 3 6 8 9
    std::cout << std::endl;
    return 0;
}

Algoritmos de Mínimo/Máximo

Encontram os valores mínimo e/ou máximo em um conjunto de elementos.

1. Simples: std::min, std::max

Retornam o menor/maior de dois valores ou de uma lista de inicializadores.

#include <iostream>
#include <algorithm>
#include <vector> // Para initializer_list (C++11)

int main() {
    int val1 = 15, val2 = 25;
    int minimo = std::min(val1, val2); 
    int maximo = std::max(val1, val2); 
    std::cout << "Minimo entre " << val1 << " e " << val2 << ": " << minimo << std::endl; // Saída: 15
    std::cout << "Maximo entre " << val1 << " e " << val2 << ": " << maximo << std::endl; // Saída: 25

    auto min_lista = std::min({1, 5, 2, 9, 4}); 
    auto max_lista = std::max({1, 5, 2, 9, 4}); 
    std::cout << "Minimo da lista: " << min_lista << std::endl; // Saída: 1
    std::cout << "Maximo da lista: " << max_lista << std::endl; // Saída: 9
    return 0;
}

2. Em Intervalo: std::min_element, std::max_element, std::minmax_element (C++11)

Retornam iteradores para os elementos mínimo e/ou máximo em um intervalo.

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

int main() {
    std::vector<float> notas = {7.5f, 9.0f, 6.0f, 8.5f, 7.0f};
    auto min_it = std::min_element(notas.begin(), notas.end()); 
    auto max_it = std::max_element(notas.begin(), notas.end()); 
    std::cout << "Menor nota: " << *min_it << std::endl; // Saída: 6.0
    std::cout << "Maior nota: " << *max_it << std::endl; // Saída: 9.0

    std::vector<std::string> palavras_minmax = {"uva", "banana", "maca", "pera"};
    auto minmax_par = std::minmax_element(palavras_minmax.begin(), palavras_minmax.end());
    std::cout << "Palavra lexicograficamente menor: " << *minmax_par.first << std::endl; // Saída: banana
    std::cout << "Palavra lexicograficamente maior: " << *minmax_par.second << std::endl; // Saída: uva
    return 0;
}

Algoritmos Numéricos (do cabeçalho <numeric>)

Estes algoritmos realizam operações matemáticas em sequências.

1. Soma Acumulada: std::accumulate

Calcula a soma de todos os elementos em um intervalo, começando com um valor inicial dado. Pode usar uma operação personalizada.

#include <iostream>
#include <vector>
#include <numeric> // Para std::accumulate
#include <functional> // Para std::multiplies

int main() {
    std::vector<int> valores_numericos = {10, 20, 30, 40};
    int soma_total = std::accumulate(valores_numericos.begin(), valores_numericos.end(), 0); 
    std::cout << "Soma total: " << soma_total << std::endl; // Saída: 100

    int produto_total = std::accumulate(valores_numericos.begin(), valores_numericos.end(), 1, std::multiplies<int>()); 
    std::cout << "Produto total: " << produto_total << std::endl; // Saída: 240000 (10*20*30*40)
    return 0;
}

2. Produto Interno: std::inner_product

Calcula o produto interno de dois intervalos.

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

int main() {
    std::vector<int> v_a = {1, 2, 3};
    std::vector<int> v_b = {5, 6, 7};
    int produto_interno = std::inner_product(v_a.begin(), v_a.end(), v_b.begin(), 0); 
    std::cout << "Produto interno: " << produto_interno << std::endl; // Saída: (1*5 + 2*6 + 3*7) = 5 + 12 + 21 = 38
    return 0;
}

3. Preenchimento Sequencial: std::iota (C++11)

Preenche um intervalo com valores sequencialmente crescentes, começando de um valor inicial.

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

int main() {
    std::vector<int> serie(5);
    std::iota(serie.begin(), serie.end(), 100); // Preenche com 100, 101, 102, 103, 104
    std::cout << "Serie iota: ";
    for (int v : serie) { std::cout << v << " "; } // Saída: 100 101 102 103 104
    std::cout << std::endl;
    return 0;
}

4. Somas Parciais: std::partial_sum

Calcula as somas parciais de um intervalo, armazenando os resultados em um intervalo de destino.

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

int main() {
    std::vector<int> origem_sum = {1, 1, 1, 1, 1};
    std::vector<int> destino_sum(origem_sum.size());
    std::partial_sum(origem_sum.begin(), origem_sum.end(), destino_sum.begin()); 
    std::cout << "Somas parciais: ";
    for (int v : destino_sum) { std::cout << v << " "; } // Saída: 1 2 3 4 5
    std::cout << std::endl;
    return 0;
    return 0;
}

5. Diferenças Adjacentes: std::adjacent_difference

Calcula as diferenças entre elementos adjacentes em um intervalo, armazenando o rseultado em um intervalo de destino. O primeiro elemento é copiado diretamente.

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

int main() {
    std::vector<int> dados_diff = {10, 12, 15, 19, 25};
    std::vector<int> res_diff(dados_diff.size());
    std::adjacent_difference(dados_diff.begin(), dados_diff.end(), res_diff.begin()); 
    std::cout << "Diferencas adjacentes: ";
    for (int v : res_diff) { std::cout << v << " "; } // Saída: 10 2 3 4 6
    std::cout << std::endl;
    return 0;
}

Outros Algoritmos Úteis

1. Geração de Elementos: std::generate, std::generate_n

  • std::generate(inicio, fim, gerador): Preenche um intervalo com valores gerados por uma função (gerador).
  • std::generate_n(inicio, n, gerador): Preenche os primeiros n elementos de um intervalo.
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>

int main() {
    std::vector<int> random_nums(5);
    std::default_random_engine gerador_rand(std::random_device{}());
    std::uniform_int_distribution<int> dist(1, 100);

    // Preenche com números aleatórios
    std::generate(random_nums.begin(), random_nums.end(), [&](){ return dist(gerador_rand); });
    std::cout << "Numeros aleatorios (generate): ";
    for (int n : random_nums) { std::cout << n << " "; }
    std::cout << std::endl;

    std::vector<std::string> prefixes(5);
    int contador = 1;
    // Preenche os 3 primeiros elementos com prefixos
    std::generate_n(prefixes.begin(), 3, [&]() { 
        return "Item-" + std::to_string(contador++); 
    }); 
    std::cout << "Prefixos (generate_n): ";
    for (const std::string& s : prefixes) { std::cout << (s.empty() ? "(empty)" : s) << " "; } // Saída: Item-1 Item-2 Item-3 (empty) (empty)
    std::cout << std::endl;
    return 0;
}

2. Inclusão de Conjuntos: std::includes

Verifica se um intervalo ordenado contém todos os elementos de outro intervalo ordenado.

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

int main() {
    std::vector<int> superconjunto = {10, 20, 30, 40, 50};
    std::vector<int> subconjunto = {20, 40};
    std::vector<int> nao_subconjunto = {20, 60};

    bool inclui_sub = std::includes(superconjunto.begin(), superconjunto.end(), subconjunto.begin(), subconjunto.end()); 
    std::cout << "Superconjunto inclui {20, 40}? " << std::boolalpha << inclui_sub << std::endl; // Saída: true

    bool inclui_nao_sub = std::includes(superconjunto.begin(), superconjunto.end(), nao_subconjunto.begin(), nao_subconjunto.end()); 
    std::cout << "Superconjunto inclui {20, 60}? " << std::boolalpha << inclui_nao_sub << std::endl; // Saída: false
    return 0;
}

3. Operações de Conjunto: std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference

Esses algoritmos realizam operações de teoria de conjuntos em intervalos ordenados, produzindo um novo intervalo ordenado como resultado.

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

int main() {
    std::vector<int> conj1 = {1, 2, 3, 4};
    std::vector<int> conj2 = {3, 4, 5, 6};
    std::vector<int> resultado;

    // Uniao
    std::set_union(conj1.begin(), conj1.end(), conj2.begin(), conj2.end(), std::back_inserter(resultado));
    std::cout << "Uniao: ";
    for (int v : resultado) { std::cout << v << " "; } // Saída: 1 2 3 4 5 6
    std::cout << std::endl;

    // Intersecao
    resultado.clear();
    std::set_intersection(conj1.begin(), conj1.end(), conj2.begin(), conj2.end(), std::back_inserter(resultado));
    std::cout << "Intersecao: ";
    for (int v : resultado) { std::cout << v << " "; } // Saída: 3 4
    std::cout << std::endl;

    // Diferenca (conj1 - conj2)
    resultado.clear();
    std::set_difference(conj1.begin(), conj1.end(), conj2.begin(), conj2.end(), std::back_inserter(resultado));
    std::cout << "Diferenca (C1 - C2): ";
    for (int v : resultado) { std::cout << v << " "; } // Saída: 1 2
    std::cout << std::endl;

    // Diferenca Simetrica
    resultado.clear();
    std::set_symmetric_difference(conj1.begin(), conj1.end(), conj2.begin(), conj2.end(), std::back_inserter(resultado));
    std::cout << "Diferenca Simetrica: ";
    for (int v : resultado) { std::cout << v << " "; } // Saída: 1 2 5 6
    std::cout << std::endl;
    return 0;
}

Perguntas Frequentes sobre Algoritmos STL

1. Qual a distinção crucial entre std::sort e std::stable_sort?

A principal diferença reside na estabilidade da ordenação:

  • std::sort: Geralmente implementado como introsort (uma combinação de quicksort, heapsort e insertion sort). É mais rápido para a maioria dos casos, com complexidade de tempo média de O(N log N), mas é um algoritmo instável. Isso significa que a ordem relativa de elementos que são considerados "iguais" pelo critério de comparação não é garantida após a ordenação.
  • std::stable_sort: Geralmente implementado como mergesort. Garante que a ordem relativa de elementos iguais seja preservada. Sua complexidade de tempo também é O(N log N), mas pode ter um custo de desempenho ou uso de memória (O(N) espaço extra) ligeiramente maior em comparação com std::sort.

2. Por que os algoritmos std::remove e std::remove_if frequentemente necessitam de container.erase()?

Os algoritmos std::remove e std::remove_if são projetados para funcionar com qualquer tipo de iterador, incluindo iteradores de entrada/saída que não permitem a modificação do tamanho do container. Eles operam movendo os elementos "não removidos" para o início do intervalo e retornam um iterador para a nova "extremidade lógica" da sequência. Os elementos que seriam removidos ainda existem fisicamente no container, apenas em posições posteriores a essa nova extremidade lógica.

Para realmente remover esses elementos e reduzir o tamanho do container (liberando memória, se aplicável), é preciso usar o método erase() do próprio container, passando o iterador retornado por remove/remove_if como o início do intervalo a ser apagado, até o final físico do container: container.erase(std::remove(...), container.end()).

3. Quais algoritmos da STL exigem que seus intervalos de entrada estejam já ordenados?

Vários algoritmos dependem da propriedade de ordenação dos seus dados para funcionar corretamente e eficientemente. Alguns exemplos notáveis incluem:

  • Busca binária e relacionados: std::binary_search, std::lower_bound, std::upper_bound, std::equal_range.
  • Operações de fusão: std::merge.
  • Operações de conjunto: std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference, std::includes.

Usar esses algoritmos em intervalos não ordenados pode levar a resultados incorretos ou comportamento indefinido.

Tags: C++ STL Algoritmos containers iteradores

Publicado em 7-3 16:27

Tags em Destaque

©2026 Doido Dev