1. Algoritmos de Busca Não-Modificadores

Estes algoritmos realizam buscas em intervalos sem alterar os elementos do container.

1.1 find e find_if

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

std::vector<int> numeros = {2, 4, 6, 8, 10};

// Localizar elemento igual a 6
auto it = std::find(numeros.begin(), numeros.end(), 6);
if (it != numeros.end()) {
    std::cout << "encontrado: " << *it << std::endl;  // saída: 6
}

// Buscar primeiro elemento maior que 7
auto it2 = std::find_if(numeros.begin(), numeros.end(), [](int valor) {
    return valor > 7;
});
std::cout << "primeiro >7: " << *it2 << std::endl;  // saída: 8

// Encontrar subsequência
std::vector<int> sub = {4, 6};
auto it3 = std::find_end(numeros.begin(), numeros.end(), sub.begin(), sub.end());
if (it3 != numeros.end()) {
    std::cout << "subsequência inicia no índice: " << std::distance(numeros.begin(), it3) << std::endl;  // saída: 1
}

1.2 count e count_if

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

std::vector<int> dados = {5, 3, 7, 3, 9, 3};
int qtd_tres = std::count(dados.begin(), dados.end(), 3); // resultado: 3
int qtd_pares = std::count_if(dados.begin(), dados.end(), [](int x) { 
    return x % 2 == 0; 
}); // elementos pares: 2

1.3 for_each

Aplica uma função a cada elemento do intervalo.

std::vector<int> valores = {1, 2, 3, 4, 5};
std::for_each(valores.begin(), valores.end(), [](int& elemento) { 
    elemento += 10; // adiciona 10 a cada elemento
});
// valores: {11, 12, 13, 14, 15}

1.4 equal e mismatch

• equal(inicio1, fim1, inicio2): Verifica se dois intervalos são iguais.
• mismatch(inicio1, fim1, inicio2): Retorna o primeiro par de iteradores onde os elementos diferem.

std::vector<int> col_a = {10, 20, 30};
std::vector<int> col_b = {10, 20, 40};
std::vector<int> col_c = {10, 20, 30};

// Verificar igualdade entre a e b
bool sao_iguais = std::equal(col_a.begin(), col_a.end(), col_b.begin());
std::cout << "a == b? " << std::boolalpha << sao_iguais << std::endl;  // saída: false

// Encontrar primeira diferença entre a e c
auto diferenca = std::mismatch(col_a.begin(), col_a.end(), col_c.begin());
if (diferenca.first != col_a.end()) {
    std::cout << "diferença: " << *diferenca.first << " vs " << *diferenca.second << std::endl;
}

1.5 all_of, any_of, none_of

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

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

2. Algoritmos Modificadores

Estes algoritmos alteram os elementos dos containers processados.

2.1 copy e copy_if

• copy(origem, destino): Copia elementos de um intervalo para outro.
• copy_if(origem, 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());  // destino: [1,2,3,4,5]

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

2.2 transform

Aplica uma função a cada elemento e armazena o resultado.

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

// Calcular cubo (transformação unária)
std::transform(entrada.begin(), entrada.end(), cubos.begin(), [](int x) {
    return x * x * x;
});  // cubos: [8, 27, 64]

// Somar dois vetores (transformação binária)
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {10, 20, 30};
std::vector<int> resultado(3);
std::transform(a.begin(), a.end(), b.begin(), resultado.begin(), [](int x, int y) {
    return x + y;
});  // resultado: [11, 22, 33]

2.3 replace, replace_if e replace_copy

• replace(inicio, fim, valor_antigo, valor_novo): Substitui todas as ocorrências.
• replace_if(inicio, fim, predicado, valor_novo): Substitui elementos que satisfazem o predicado.
• replace_copy(origem, destino, valor_antigo, valor_novo): Copia substituindo (preserva original).

std::vector<int> nums = {5, 10, 15, 10, 20};

// Substituir todas as ocorrências de 10 por 100
std::replace(nums.begin(), nums.end(), 10, 100);  // nums: [5,100,15,100,20]

// Substituir elementos menores que 12
std::replace_if(nums.begin(), nums.end(), [](int x) {
    return x < 12;
}, 0);  // nums: [0,100,0,100,20]

// Copiar substituindo 15 por 150 (sem alterar original)
std::vector<int> copia;
std::replace_copy(nums.begin(), nums.end(), std::back_inserter(copia), 15, 150);  // copia: [0,100,150,100,20]

2.4 remove, remove_if e erase

• remove(inicio, fim, valor): Move elementos diferentes de valor para o início (retorna novo fim lógico).
• remove_if(inicio, fim, predicado): Move elementos que não satisfazem o predicado.

std::vector<int> dados = {5, 10, 15, 10, 20};

// Remover logicamente todas as ocorrências de 10
auto novo_fim = std::remove(dados.begin(), dados.end(), 10);  // dados: [5,15,20,10,10]

// Remover fisicamente
dados.erase(novo_fim, dados.end());  // dados: [5, 15, 20]

// Remover números pares
dados = {3, 6, 9, 12, 15};
dados.erase(std::remove_if(dados.begin(), dados.end(), [](int x) {
    return x % 2 == 0;
}), dados.end());  // dados: [3, 9, 15]

2.5 unique

Remove elementos duplicados consecutivos, retornando novo fim lógico.

std::vector<int> seq = {1, 1, 2, 2, 2, 3, 3, 4, 5, 5};
auto ultimo = std::unique(seq.begin(), seq.end());
seq.erase(ultimo, seq.end()); // seq: {1, 2, 3, 4, 5}

2.6 reverse

Inverte a ordem dos elementos.

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

2.7 rotate

Rotaciona os elementos, movendo um elemento específico para o início.

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

2.8 shuffle

Reordena elementos aleatoriamente (requer C++11).

#include <random>
#include <algorithm>

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

3. Algoritmos de Ordenação

3.1 sort, stable_sort e partial_sort

• sort(inicio, fim): Ordena com Introsort (O(n log n), não-estável).
• stable_sort(inicio, fim): Ordena mentendo ordem relativa de elementos iguais.
• partial_sort(inicio, meio, fim): Coloca os menores elementos em [inicio, meio).

std::vector<int> numeros = {8, 3, 1, 6, 2};
std::sort(numeros.begin(), numeros.end()); // crescente: {1, 2, 3, 6, 8}
std::sort(numeros.begin(), numeros.end(), std::greater<int>()); // decrescente
std::sort(numeros.begin(), numeros.end(), [](int a, int b) { 
    return a > b; 
}); // personalizado

std::vector<std::pair<int, std::string>> itens = {{1, "b"}, {2, "a"}, {1, "c"}, {2, "d"}};
std::stable_sort(itens.begin(), itens.end(), [](const auto& p1, const auto& p2) {
    return p1.first < p2.first; // mantém ordem de "b" e "c"
});

std::vector<int> vals = {9, 5, 2, 7, 3, 8};
std::partial_sort(vals.begin(), vals.begin() + 3, vals.end());
// Primeiros 3 elementos: {2, 3, 5}

3.2 nth_element

Reorganiza o intervalo para que o elemento na posição especificada seja o mesmo quewould estar após ordenação completa.

std::vector<int> dados = {9, 5, 1, 8, 3, 7, 2, 6, 4};
std::nth_element(dados.begin(), dados.begin() + 4, dados.end());
// dados[4] contém o 5º menor elemento

3.3 binary_search, lower_bound, upper_bound

Requer container ordenado.

• binary_search(inicio, fim, valor): Retorna booleano.
• lower_bound(inicio, fim, valor): Primeiro elemento >= valor.
• upper_bound(inicio, fim, valor): Primeiro elemento > valor.

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

bool existe = std::binary_search(ord.begin(), ord.end(), 3);  // true

auto it_low = std::lower_bound(ord.begin(), ord.end(), 3);
auto it_high = std::upper_bound(ord.begin(), ord.end(), 3);
std::cout << "lower_bound: " << std::distance(ord.begin(), it_low) << std::endl;  // 1
std::cout << "upper_bound: " << std::distance(ord.begin(), it_high) << std::endl;  // 3

3.4 merge

Mescla dois intervalos ordenados.

std::vector<int> x = {1, 3, 5};
std::vector<int> y = {2, 4, 6};
std::vector<int> combinado(x.size() + y.size());

std::merge(x.begin(), x.end(), y.begin(), y.end(), combinado.begin()); 
// combinado: {1,2,3,4,5,6}

4. Algoritmos de Heap

STL oferece operações de heap para Priority Queues.

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

heap.push_back(8);
std::push_heap(heap.begin(), heap.end()); 
// heap: {8, 3, 7, 2, 1, 5}

std::pop_heap(heap.begin(), heap.end()); 
// maior elemento movido para o final
int maior = heap.back();
heap.pop_back();

std::sort_heap(heap.begin(), heap.end()); 
// heap: {1, 2, 3, 5}

5. Algoritmos de Mínimo e Máximo

5.1 min e max

Retornam menor/maior entre dois valores ou lista.

int p = 7, q = 4;
int menor = std::min(p, q); // 4
int maior = std::max(p, q); // 7

auto minimo = std::min({9, 1, 7, 3, 5}); // 1
auto maximo = std::max({9, 1, 7, 3, 5}); // 9

5.2 min_element e max_element

Retornam iteradores para menor/maior elemento.

std::vector<int> vals = {6, 2, 8, 1, 9};
auto it_min = std::min_element(vals.begin(), vals.end()); // aponta para 1
auto it_max = std::max_element(vals.begin(), vals.end()); // aponta para 9

5.3 minmax_element (C++11)

Retorna ambos em uma operação.

std::vector<int> vals = {6, 2, 8, 1, 9};
auto resultado = std::minmax_element(vals.begin(), vals.end());
// resultado.first -> 1, resultado.second -> 9

6. Algoritmos Numéricos (numeric)

6.1 accumulate

Soma elementos ou executa outra operação binária.

#include <numeric>

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

int produto = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 120

6.2 inner_product

Calcula produto escalar de dois vetores.

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

6.3 iota

Preenche intervalo com valores consecutivos.

std::vector<int> vec(5);
std::iota(vec.begin(), vec.end(), 100); // 100, 101, 102, 103, 104

6.4 partial_sum

Calcula somas acumuladas.

std::vector<int> entrada = {1, 2, 3, 4, 5};
std::vector<int> saida(entrada.size());
std::partial_sum(entrada.begin(), entrada.end(), saida.begin()); 
// saida: {1, 3, 6, 10, 15}

6.5 adjacent_difference

Calcula diferenças entre elementos adjacentes.

std::vector<int> entrada = {5, 5, 5, 5, 5};
std::vector<int> saida(entrada.size());
std::adjacent_difference(entrada.begin(), entrada.end(), saida.begin()); 
// saida: {5, 0, 0, 0, 0}

7. Outros Algoritmos Úteis

7.1 generate

Preenche intervalo usando função geradora.

std::vector<int> vec(4);
int contador = 5;
std::generate(vec.begin(), vec.end(), [&contador]() { 
    return contador++; 
}); // 5, 6, 7, 8

7.2 generate_n

Preenche os primeiros n elementos.

std::vector<int> vec(5);
int inicio = 10;
std::generate_n(vec.begin(), 3, [&inicio]() { 
    return inicio++; 
}); // 10, 11, 12, 0, 0

7.3 includes

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

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

7.4 Operações de Conjuntos

Realiza operações de teoria de conjuntos em intervalos ordenados.

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

// União
std::set_union(conjunto1.begin(), conjunto1.end(), 
               conjunto2.begin(), conjunto2.end(),
               std::back_inserter(resultado)); 
// resultado: {1, 2, 3, 4, 5, 6, 7}

// Interseção
resultado.clear();
std::set_intersection(conjunto1.begin(), conjunto1.end(),
                      conjunto2.begin(), conjunto2.end(),
                      std::back_inserter(resultado));
// resultado: {3, 4, 5}

// Diferença (conjunto1 - conjunto2)
resultado.clear();
std::set_difference(conjunto1.begin(), conjunto1.end(),
                    conjunto2.begin(), conjunto2.end(),
                    std::back_inserter(resultado));
// resultado: {1, 2}

// Diferença simétrica
resultado.clear();
std::set_symmetric_difference(conjunto1.begin(), conjunto1.end(),
                               conjunto2.begin(), conjunto2.end(),
                               std::back_inserter(resultado));
// resultado: {1, 2, 6, 7}

8. Questões Frequentes

1. Qual a diferença entre sort e stable_sort?

• sort usa Introsort, não mantém ordem relativa de elementos iguais, O(n log n).
• stable_sort usa merge sort adaptado, mantém ordem relativa, O(n log n) com mais memória.

2. Por que remove precisa de erase?

• remove apenas move elementos para o início (remoção lógica), retornando novo fim.
• erase remove fisicamente os elementos do container.
• Padrão: vec.erase(std::remove(...), vec.end()).

3. Quais algoritmos requerem container ordenado?

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