1. Algoritmos de Sequência Não Modificadores

Estes algoritmos não alteram os elementos dos contêineres em que operam.

1.1 find e find_if

• find(inicio, fim, valor): Encontra o primeiro elemento igual a valor, retornando um iterador (retorna 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): Encontra a última ocorrência de uma subsequência.

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

// Encontrar o valor 6
auto iterador = find(valores.begin(), valores.end(), 6);
if (iterador != valores.end()) {
    cout << "encontrado: " << *iterador << endl;  // Saída: 6
}

// Encontrar o primeiro elemento maior que 7
auto iterador2 = find_if(valores.begin(), valores.end(), [](int x) {
    return x > 7;
});
cout << "primeiro >7: " << *iterador2 << endl;  // Saída: 8

// Encontrar uma subsequência
std::vector<int> sub = {4, 6};
auto iterador3 = find_end(valores.begin(), valores.end(), sub.begin(), sub.end());
if (iterador3 != valores.end()) {
    cout << "subsequência começa no índice: " << iterador3 - valores.begin() << endl;  // Saída: 1
}

1.2 count e count_if

• count(inicio, fim, valor): Conta o número de elementos iguais a valor.
• count_if(inicio, fim, predicado): Conta o número de elementos que satisfazem o predicado.

std::vector<int> dados = {2, 3, 4, 3, 5, 3};
int contagem = std::count(dados.begin(), dados.end(), 3); // Conta ocorrências de 3, resultado: 3
int pares_contagem = std::count_if(dados.begin(), dados.end(), [](int x) { 
    return x % 2 == 0; 
}); // Números pares, resultado: 3

1.3 for_each

Aplica uma função a cada elemento em um intervalo

std::vector<int> elementos = {1, 2, 3, 4, 5};
std::for_each(elementos.begin(), elementos.end(), [](int& x) { 
    x *= 2; // Multiplica cada elemento por 2
});
// Agora elementos é {2, 4, 6, 8, 10}

1.4 equal e mismatch

• equal(b1, e1, b2): Verifica se os intervalos [b1,e1) e [b2, b2+(e1-b1)) são iguais.
• mismatch(b1, e1, b2): Retorna um par de iteradores para os primeiros elementos diferentes nos dois intervalos.

std::vector<int> v1 = {2, 4, 6};
std::vector<int> v2 = {2, 4, 7};
std::vector<int> v3 = {2, 4, 6, 8};

// Comparar v1 e v2
bool sao_iguais = equal(v1.begin(), v1.end(), v2.begin());
cout << "v1 == v2? " << boolalpha << sao_iguais << endl;  // Saída: false

// Encontrar primeiro elemento diferente entre v1 e v3
auto dif = mismatch(v1.begin(), v1.end(), v3.begin());
if (dif.first != v1.end()) {
    cout << "diferença: " << *dif.first << " vs " << *dif.second << endl;  // Sem saída (primeiros 3 elementos iguais)
}

1.5 all_of, any_of, none_of

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

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

2. Algoritmos de Sequência Modificadores

Estes algoritmos modificam os elementos dos contêineres em que operam.

2.1 copy e copy_if

• copy(inicio, fim, destino): Copia elementos do intervalo [inicio, fim) para a posição começando em destino.
• copy_if(inicio, fim, destino, predicado): Copia elementos que satisfazem o predicado para destino.

std::vector<int> fonte = {1, 2, 3, 4, 5};
std::vector<int> destino(5);  // Precisa de espaço pré-alocado

// Copiar todos os elementos
copy(fonte.begin(), fonte.end(), destino.begin());  // destino: [1,2,3,4,5]

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

Nota: back_inserter(destino) automaticamente chama push_back, sem necessidade de pré-alocar espaço.

2.2 transform

Aplica uma função a cada elemento em um intervalo, armazenando o resultado em outro intervalo

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

// Calcular quadrados (transformação de um parâmetro)
transform(numeros.begin(), numeros.end(), quadrados.begin(), [](int x) {
    return x * x;
});  // quadrados: [1,4,9]

// Somar elementos de dois contêineres (transformação de dois parâmetros)
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> soma(3);
transform(a.begin(), a.end(), b.begin(), soma.begin(), [](int x, int y) {
    return x + y;
});  // soma: [5,7,9]

2.3 replace, replace_if e replace_copy

• replace(inicio, fim, antigo, novo): Substitui todas ocorrências de antigo por novo.
• replace_if(inicio, fim, predicado, novo): Substitui elementos que satisfazem o predicado.
• replace_copy(inicio, fim, destino, antigo, novo): Copia elementos com substituição (não modifica contêiner original).

std::vector<int> valores = {2, 3, 4, 3, 6};

// Substituir todos 3s por 30
replace(valores.begin(), valores.end(), 3, 30);  // valores: [2,30,4,30,6]

// Substituir elementos maiores que 5 por 0
replace_if(valores.begin(), valores.end(), [](int x) {
    return x > 5;
}, 0);  // valores: [2,30,4,30,0]

// Copiar com substituição de 4s por 40 (contêiner original inalterado)
std::vector<int> resultado;
replace_copy(valores.begin(), valores.end(), back_inserter(resultado), 4, 40);  // resultado: [2,30,40,30,0]

2.4 remove, remove_if e erase

• remove(inicio, fim, valor): "Move" elementos iguais a valor para o final do contêiner, retornando um novo iterador lógico final (não remove fisicamente elementos, precisa ser combinado com erase).
• remove_if(inicio, fim, predicado): Move elementos que satisfazem o predicado para o final.

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

// Remoção lógica de todos 3s (movidos para o final)
auto novo_fim = remove(dados.begin(), dados.end(), 3);  // dados: [2,4,5,3,3]

// Remoção física (realmente remove elementos)
dados.erase(novo_fim, dados.end());  // dados: [2,4,5]

// Combinar com lambda para remover pares
dados = {2, 3, 4, 5, 6};
dados.erase(remove_if(dados.begin(), dados.end(), [](int x) {
    return x % 2 == 0;
}), dados.end());  // dados: [3,5]

2.5 unique

Remove elementos duplicados consecutivos em um intervalo, retornando um novo iterador final. Geralmente combinado com erase.

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

2.6 reverse

Inverte a ordem dos elementos em um intervalo

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

2.7 rotate

Rotaciona elementos em um intervalo, tornando o elemento do meio o novo primeiro elemento

std::vector<int> elementos = {1, 2, 3, 4, 5};
std::rotate(elementos.begin(), elementos.begin() + 2, elementos.end()); // Rotaciona a partir de 3, elementos se torna {3, 4, 5, 1, 2}

2.8 shuffle

Embaralha aleatoriamente elementos em um intervalo (requere C++11 ou superior)

#include <random>
#include <algorithm>

std::vector<int> elementos = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(elementos.begin(), elementos.end(), g); // Embaralha aleatoriamente elementos

3. Ordenação e Algoritmos Relacionados

3.1 sort, stable_sort e partial_sort

• sort(inicio, fim): Ordena elementos usando quicksort (instável, complexidade média O(n log n)).
• stable_sort(inicio, fim): Ordenação estável (posição relativa de elementos iguais mantida).
• partial_sort(inicio, meio, fim): Ordenação parcial, fazendo com que [inicio, meio) contenha os menores elementos do intervalo e ordenados.

std::vector<int> dados = {5, 3, 2, 4, 1};
std::sort(dados.begin(), dados.end()); // Ordenação crescente padrão, dados se torna {1, 2, 3, 4, 5}
std::sort(dados.begin(), dados.end(), std::greater<int>()); // Ordenação decrescente, dados se torna {5, 4, 3, 2, 1}
std::sort(dados.begin(), dados.end(), [](int a, int b) { 
    return a < b; 
}); // Crescente, comparador personalizado

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 pelo first, mantém ordem relativa de elementos iguais
});

std::vector<int> dados = {5, 3, 2, 4, 1, 6};
// Coloca os 3 menores elementos no início e ordena
std::partial_sort(dados.begin(), dados.begin() + 3, dados.end());
// Agora os 3 primeiros elementos de dados são 1, 2, 3, os restantes 4, 5, 6 permanecem desordenados

3.2 nth_element

Reorganiza o intervalo de forma que o elemento na posição especificada seja igual ao elemento ordenado, com elementos à esquerda menores ou iguais e elmeentos à direita maiores ou iguais

std::vector<int> dados = {5, 3, 2, 4, 1, 6};
// Encontra o terceiro menor elemento (índice 2)
std::nth_element(dados.begin(), dados.begin() + 2, dados.end());
// Agora dados[2] é 3, elementos à esquerda são <=3, elementos à direita são >=3

3.3 binary_search, lower_bound, upper_bound

Devem ser usados em contêineres ordenados

• binary_search(inicio, fim, valor): Verifica se valor existe (retorna bool).
• lower_bound(inicio, fim, valor): Retorna iterador para o primeiro elemento não menor que valor.
• upper_bound(inicio, fim, valor): Retorna iterador para o primeiro elemento maior que valor.

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

// Verificar se 3 existe
bool existe = binary_search(ordenado.begin(), ordenado.end(), 3);  // true

// Encontrar primeiro elemento >=3
auto lb = lower_bound(ordenado.begin(), ordenado.end(), 3);
cout << "índice lower_bound: " << lb - ordenado.begin() << endl;  // Saída: 1

// Encontrar primeiro elemento >3
auto ub = upper_bound(ordenado.begin(), ordenado.end(), 3);
cout << "índice upper_bound: " << ub - ordenado.begin() << endl;  // Saída: 3

3.4 merge

Mescla dois intervalos ordenados em um novo contêiner (mantendo ordanação)

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

// Mesclar a e b (ambos devem estar ordenados)
merge(a.begin(), a.end(), b.begin(), b.end(), mesclado.begin());  // mesclado: [1,2,3,4,5,6]

4. Algoritmos de Heap

A STL fornece algoritmos para operar em intervalos como heaps, incluindo make_heap, push_heap, pop_heap, sort_heap, etc.

std::vector<int> dados = {4, 1, 3, 2, 5};
std::make_heap(dados.begin(), dados.end()); // Constrói um max-heap, dados se torna {5, 4, 3, 2, 1}

dados.push_back(6);
std::push_heap(dados.begin(), dados.end()); // Adiciona novo elemento ao heap, dados se torna {6, 4, 5, 2, 1, 3}

std::pop_heap(dados.begin(), dados.end()); // Move o maior elemento para o final, dados se torna {5, 4, 3, 2, 1, 6}
int max_val = dados.back(); // Obtém o maior elemento 6
dados.pop_back(); // Remove o maior elemento

std::sort_heap(dados.begin(), dados.end()); // Ordena o heap em sequência crescente, dados se torna {1, 2, 3, 4, 5}

5. Algoritmos de Mínimo/Máximo

5.1 min e max

Retornam o menor/maior valor entre dois valores ou uma lista inicializada

int x = 5, y = 3;
int min_val = std::min(x, y); // 3
int max_val = std::max(x, y); // 5

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

5.2 min_element e max_element

Retornam iteradores para o menor/maior elemento em um intervalo

std::vector<int> dados = {3, 1, 4, 2, 5};
auto min_it = std::min_element(dados.begin(), dados.end()); // Aponta para 1
auto max_it = std::max_element(dados.begin(), dados.end()); // Aponta para 5

5.3 minmax_element (C++11)

Retorna iteradores para o menor e maior elementos em um intervalo simultaneamente

std::vector<int> dados = {3, 1, 4, 2, 5};
auto minmax = std::minmax_element(dados.begin(), dados.end());
// minmax.first aponta para 1, minmax.second aponta para 5

6. Algoritmos Numéricos (em <numeric>)

6.1 accumulate

Calcula a soma acumulada de elementos em um intervalo (ou operação personalizada)

#include <numeric>

std::vector<int> dados = {1, 2, 3, 4, 5};
int soma = std::accumulate(dados.begin(), dados.end(), 0); // Soma, valor inicial 0, resultado 15
int produto = std::accumulate(dados.begin(), dados.end(), 1, std::multiplies<int>()); // Produto, valor inicial 1, resultado 120

6.2 inner_product

Calcula o produto interno de dois intervalos (ou operação personalizada)

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

6.3 iota

Preenche um intervalo com valores incrementalmente crescentes

std::vector<int> dados(5);
std::iota(dados.begin(), dados.end(), 10); // Preenche com 10, 11, 12, 13, 14

6.4 partial_sum

Calcula somas parciais, armazenando resultados em um intervalo de destino

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

6.5 adjacent_difference

Calcula diferenças entre elementos adjacentes, armazenando resultados em um intervalo de destino

std::vector<int> fonte = {1, 2, 3, 4, 5};
std::vector<int> destino(fonte.size());
std::adjacent_difference(fonte.begin(), fonte.end(), destino.begin()); // destino se torna {1, 1, 1, 1, 1}

7. Outros Algoritmos

7.1 generate

Preenche um intervalo com valores gerados por uma função

std::vector<int> dados(5);
int n = 0;
std::generate(dados.begin(), dados.end(), [&n]() { 
    return n++; 
}); // Preenche com 0, 1, 2, 3, 4

7.2 generate_n

Preenche os primeiros n elementos de um intervalo com valores gerados por uma função

std::vector<int> dados(5);
int n = 10;
std::generate_n(dados.begin(), 3, [&n]() { 
    return n++; 
}); // Os primeiros 3 elementos são 10, 11, 12, os outros 2 permanecem inalterados

7.3 includes

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

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

7.4 set_union, set_intersection, set_difference, set_symmetric_difference

Executa operações de conjuntos: união, interseção, diferença e diferença simétrica

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

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

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

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

// Diferença simétrica (c1 ∪ c2 - c1 ∩ c2)
resultado.clear();
std::set_symmetric_difference(c1.begin(), c1.end(), c2.begin(), c2.end(), std::back_inserter(resultado));
// resultado é {1, 2, 6, 7}

8. Perguntas Comuns

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

• sort utiliza quicksort (na verdade é o algoritmo introsort), é instável (posição relativa de elementos iguais pode mudar), complexidade média O(n log n).
• stable_sort utiliza merge sort, é estável (posição relativa de elementos iguais é mantida), complexidade O(n log n), mas tem um pouco mais de uso de memória.

2. Por que o algoritmo remove precisa ser combinado com erase? O princípio do algoritmo remove é "sobrescrever" os elementos a serem removidos, movendo os elementos preservados para o início e retornando um novo iterador final lógico, mas não modifica o tamanho real do contêiner. O erase remove fisicamente os elementos pelo intervalo de iteradores, modificando o tamanho do contêiner. Por isso eles precisam ser combinados: contêiner.erase(remove(...), contêiner.end()).
3. Quais algoritmos exigem que o contêiner esteja ordenado? Algoritmos de busca binária (binary_search, lower_bound, upper_bound), algoritmos de conjunto (set_intersection, set_union, etc.), e merge, dependem da ordenação para operações eficientes (como busca binária em O(log n)).