1. Algoritmos de Sequência Não Modificadora

---

Estes algoritmos não alteram os elementos dos recipientes sobre os quais operam.

1.1 find, find_if e find_end

• find(inicio, fim, valor): Localiza o primeiro elemento igual a valor, retornando um iterador (retorna fim se não encontrado).
• find_if(inicio, fim, predicado): Localiza o primeiro elemento que satisfaz o predicado.
• find_end(inicio, fim, sub_inicio, sub_fim): Encontra a última ocorrência de uma subsequência.

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

int main() {
    std::vector<int> numeros = {1, 3, 5, 7, 9};
    
    // Procurar pelo elemento 5
    auto iterador = std::find(numeros.begin(), numeros.end(), 5);
    if (iterador != numeros.end()) {
        std::cout << "Encontrado: " << *iterador << std::endl;
    }
    
    // Procurar primeiro elemento maior que 6
    auto iterador2 = std::find_if(numeros.begin(), numeros.end(), [](int valor) {
        return valor > 6;
    });
    std::cout << "Primeiro >6: " << *iterador2 << std::endl;
    
    // Procurar subsequência
    std::vector<int> subseq = {3, 5};
    auto iterador3 = std::find_end(numeros.begin(), numeros.end(), subseq.begin(), subseq.end());
    if (iterador3 != numeros.end()) {
        std::cout << "Subsequência inicia no índice: " << iterador3 - numeros.begin() << std::endl;
    }
}

1.2 count e count_if

• count(inicio, fim, valor): Conta elementos iguais a valor.
• count_if(inicio, fim, predicado): Conta elementos que satisfazme o predicado.

std::vector<int> dados = {1, 2, 3, 2, 4, 2};
int contagem = std::count(dados.begin(), dados.end(), 2); // Resultado: 3
int contagem_pares = std::count_if(dados.begin(), dados.end(), [](int x) { 
    return x % 2 == 0; 
}); // Resultado: 4

1.3 for_each

Aplica uma função a cada elemento dentro de um intervalo.

std::vector<int> valores = {1, 2, 3, 4, 5};
std::for_each(valores.begin(), valores.end(), [](int& x) { 
    x *= 2; 
});
// valores agora contém {2, 4, 6, 8, 10}

1.4 equal e mismatch

• equal(b1, e1, b2): Verifica se dois intervalos são iguais.
• mismatch(b1, e1, b2): Retorna um par de iteradores apontando para os primeiros elementos não correspondentes.

std::vector<int> seq1 = {1, 2, 3};
std::vector<int> seq2 = {1, 2, 4};
bool iguais = std::equal(seq1.begin(), seq1.end(), seq2.begin()); // false

auto resultado = std::mismatch(seq1.begin(), seq1.end(), seq2.begin());
if (resultado.first != seq1.end()) {
    std::cout << "Diferença: " << *resultado.first << " vs " << *resultado.second << std::endl;
}

1.5 all_of, any_of, none_of

Verificam se todos, algum ou nenhum elemento satisfazem uma condição.

std::vector<int> conjunto = {2, 4, 6, 8};
bool todos_pares = std::all_of(conjunto.begin(), conjunto.end(), [](int x) { 
    return x % 2 == 0; 
}); // true
bool algum_impar = std::any_of(conjunto.begin(), conjunto.end(), [](int x) { 
    return x % 2 != 0; 
}); // false
bool nenhum_negativo = std::none_of(conjunto.begin(), conjunto.end(), [](int x) { 
    return x < 0; 
}); // true

2. Algoritmos de Sequência Modificadora

---

Estes algoritmos alteram os elementos dos recipientes.

2.1 copy e copy_if

• copy(inicio, fim, destino): Copia elementos para o destino.
• copy_if(inicio, fim, destino, predicado): Copia apenas elementos que satisfazem o predicado.

std::vector<int> fonte = {1, 2, 3, 4, 5};
std::vector<int> destino(5);

// Copiar todos os elementos
std::copy(fonte.begin(), fonte.end(), destino.begin());

// Copiar apenas elementos pares
std::vector<int> pares;
std::copy_if(fonte.begin(), fonte.end(), std::back_inserter(pares), [](int x) {
    return x % 2 == 0;
});

2.2 transform

Aplica uma função e armazena os resultados em outro intervalo.

std::vector<int> numeros = {1, 2, 3};
std::vector<int> quadrados(3);

std::transform(numeros.begin(), numeros.end(), quadrados.begin(), [](int x) {
    return x * x;
});

// Soma de dois vetores
std::vector<int> vet1 = {1, 2, 3};
std::vector<int> vet2 = {4, 5, 6};
std::vector<int> soma(3);
std::transform(vet1.begin(), vet1.end(), vet2.begin(), soma.begin(), [](int a, int b) {
    return a + b;
});

2.3 replace, replace_if e replace_copy

• replace(inicio, fim, antigo, novo): Substitui todas as ocorrências.
• replace_if(inicio, fim, predicado, novo): Substitui elementos que satisfazem o predicado.
• replace_copy(inicio, fim, destino, antigo, novo): Cria uma cópia com substituições.

std::vector<int> elementos = {1, 2, 3, 2, 5};
std::replace(elementos.begin(), elementos.end(), 2, 20);

std::replace_if(elementos.begin(), elementos.end(), [](int x) {
    return x > 10;
}, 0);

std::vector<int> copia;
std::replace_copy(elementos.begin(), elementos.end(), std::back_inserter(copia), 3, 300);

2.4 remove, remove_if e erase

• remove e remove_if movem elementos indesejados para o final do recipiente (não removem fisicamente).
• A remoção física requer erase após a operação de remoção lógica.

std::vector<int> dados = {1, 2, 3, 2, 4};

// Remoção lógica
auto novo_fim = std::remove(dados.begin(), dados.end(), 2);

// Remoção física
dados.erase(novo_fim, dados.end());

// Combinação com erase e remove_if
dados = {1, 2, 3, 4, 5};
dados.erase(std::remove_if(dados.begin(), dados.end(), [](int x) {
    return x % 2 == 0;
}), dados.end());

2.5 unique

Remove elementos duplicados consecutivos, retornando iterador para o novo final lógico.

std::vector<int> itens = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto final_unico = std::unique(itens.begin(), itens.end());
itens.erase(final_unico, itens.end());
// itens agora contém {1, 2, 3, 4, 5}

2.6 reverse

Inverte a ordem dos elementos.

std::vector<int> seq = {1, 2, 3, 4, 5};
std::reverse(seq.begin(), seq.end());
// seq agora contém {5, 4, 3, 2, 1}

2.7 rotate

Rotaciona os elementos fazendo com que um elemento intermediário se torne o primeiro.

std::vector<int> dados = {1, 2, 3, 4, 5};
std::rotate(dados.begin(), dados.begin() + 2, dados.end());
// dados agora contém {3, 4, 5, 1, 2}

2.8 shuffle

Embaralha aleatoriamente os elementos (requer C++11 ou superior).

#include <random>
#include <algorithm>

std::vector<int> baralho = {1, 2, 3, 4, 5};
std::random_device dispositivo;
std::mt19937 gerador(dispositivo());
std::shuffle(baralho.begin(), baralho.end(), gerador);

3. Algoritmos de Ordenação

---

3.1 sort, stable_sort e partial_sort

• sort: Ordenação rápida (instável, complexidade média O(n log n)).
• stable_sort: Ordenação estável mantendo a ordem relativa de elementos iguais.
• partial_sort: Ordena parcialmente mantendo os menores elementos no início.

std::vector<int> numeros = {5, 3, 1, 4, 2};
std::sort(numeros.begin(), numeros.end());

// Ordenação estável
std::vector<std::pair<int, int>> pares = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pares.begin(), pares.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});

// Ordenação parcial
std::vector<int> dados = {5, 3, 1, 4, 2, 6};
std::partial_sort(dados.begin(), dados.begin() + 3, dados.end());

3.2 nth_element

Reorganiza os elementos de modo que o elemento na posição n seja o que seria se a sequência estivesse ordenada.

std::vector<int> dados = {5, 3, 1, 4, 2, 6};
std::nth_element(dados.begin(), dados.begin() + 2, dados.end());
// O terceiro menor elemento (índice 2) está na posição correta

3.3 binary_search, lower_bound e upper_bound

Requerem recipientes previamente ordenados.

• binary_search: Verifica se um valor existe.
• lower_bound: Encontra o primeiro elemento não menor que o valor.
• upper_bound: Encontra o primeiro elemento estritamente maior que o valor.

std::vector<int> ordenado = {1, 3, 3, 5, 7};

bool existe = std::binary_search(ordenado.begin(), ordenado.end(), 3);

auto limite_inferior = std::lower_bound(ordenado.begin(), ordenado.end(), 3);
auto limite_superior = std::upper_bound(ordenado.begin(), ordenado.end(), 3);

3.4 merge

Mescla dois intervalos ordenados mantendo a ordenação.

std::vector<int> v1 = {1, 3, 5};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> mesclado(v1.size() + v2.size());

std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), mesclado.begin());

4. Algoritmos de Heap

---

Permitem tratar um intervalo como um heap (árvore binária).

std::vector<int> dados = {4, 1, 3, 2, 5};
std::make_heap(dados.begin(), dados.end()); // Cria heap máximo

dados.push_back(6);
std::push_heap(dados.begin(), dados.end()); // Insere mantendo propriedades

std::pop_heap(dados.begin(), dados.end()); // Move maior para o final
int maximo = dados.back();
dados.pop_back();

std::sort_heap(dados.begin(), dados.end()); // Ordena completamente

5. Algoritmos de Mínimo/Máximo

---

5.1 min e max

Retornam o menor ou maior entre dois valores ou uma lista inicializadora.

int minimo = std::min(5, 3);
int maximo = std::max(5, 3);

auto min_lista = std::min({4, 2, 8, 5, 1});
auto max_lista = std::max({4, 2, 8, 5, 1});

5.2 min_element e max_element

Retornam iteradores para os elementos mínimo e máximo.

std::vector<int> dados = {3, 1, 4, 2, 5};
auto it_min = std::min_element(dados.begin(), dados.end());
auto it_max = std::max_element(dados.begin(), dados.end());

5.3 minmax_element

Retorna simultaneamente os iteradores para mínimo e máximo.

std::vector<int> dados = {3, 1, 4, 2, 5};
auto [min_it, max_it] = std::minmax_element(dados.begin(), dados.end());

6. Algoritmos Numéricos

---

Implementados no cabeçalho <numeric>.

6.1 accumulate

Calcula a soma acumulada (ou operação personalizada).

#include <numeric>

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

6.2 inner_product

Calcula o produto escalar de dois intervalos.

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
int escalar = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);

6.3 iota

Preenche um intervalo com valores sequenciais crescentes.

std::vector<int> sequencia(5);
std::iota(sequencia.begin(), sequencia.end(), 10);
// sequencia contém {10, 11, 12, 13, 14}

6.4 partial_sum

Calcula somas parciais.

std::vector<int> fonte = {1, 2, 3, 4, 5};
std::vector<int> somas_parciais(fonte.size());
std::partial_sum(fonte.begin(), fonte.end(), somas_parciais.begin());
// somas_parciais contém {1, 3, 6, 10, 15}

6.5 adjacent_difference

Calcula diferenças entre elementos adjacentes.

std::vector<int> dados = {1, 2, 3, 4, 5};
std::vector<int> diferencas(dados.size());
std::adjacent_difference(dados.begin(), dados.end(), diferencas.begin());
// diferencas contém {1, 1, 1, 1, 1}

7. Outros Algoritmos Importantes

---

7.1 generate e generate_n

Preenchem intervalos usando funções geradoras.

std::vector<int> v(5);
int contador = 0;
std::generate(v.begin(), v.end(), [&contador]() { 
    return contador++; 
});

std::vector<int> v2(5);
int valor = 10;
std::generate_n(v2.begin(), 3, [&valor]() { 
    return valor++; 
});

7.2 includes

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

std::vector<int> principal = {1, 2, 3, 4, 5};
std::vector<int> subconjunto = {2, 4};
bool contem = std::includes(principal.begin(), principal.end(), subconjunto.begin(), subconjunto.end());

7.3 Operações de Conjunto

Algoritmos para união, interseção, diferença e diferença simétrica em intervalos ordenados.

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> resultado;

// União
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(resultado));

// Interseção
resultado.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(resultado));

// Diferença (a - b)
resultado.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(resultado));

// Diferença simétrica
resultado.clear();
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(resultado));

8. Perguntas Frequentes

---

Diferença entre sort e stable_sort?

sort utiliza introsort (instável), enquanto stable_sort utiliza mergesort (estável), preservando a ordem relativa de elementos equivalentes.

Por que remove precisa de erase?

remove apenas reorganiza elementos, retornando um iterador para o novo final lógico. erase efetivamente modifica o tamanho do recipiente, removendo os elementos indesejados.

Algoritmos que exigem recipiente ordenado?

Busca binária (binary_search, lower_bound, upper_bound), operações de conjunto, merge e includes requerem dados previamente ordenados para funcionamento correto.