Algoritmos de Sequência Não Modificadores

Estes algoritmos não alteram os elementos do contêiner com o qual operam.

find, find_if e find_end

A função find localiza o primeiro elemento igual a um valor específico. find_if encontra o primeiro elemento que satisfaz um predicado. find_end busca a última ocorrência de uma subsequência.

vector<int> numeros = {10, 15, 20, 25, 30};

// Localizar o elemento com valor 20
auto iterador = find(numeros.begin(), numeros.end(), 20);
if (iterador != numeros.end()) {
    cout << "Encontrado: " << *iterador << endl;  // Saída: 20
}

// Localizar o primeiro elemento maior que 22
auto it_condicional = find_if(numeros.begin(), numeros.end(), [](int valor) {
    return valor > 22;
});
cout << "Primeiro >22: " << *it_condicional << endl;  // Saída: 25

// Localizar subsequência {15, 20}
vector<int> subsequencia = {15, 20};
auto it_sub = find_end(numeros.begin(), numeros.end(), subsequencia.begin(), subsequencia.end());
if (it_sub != numeros.end()) {
    cout << "Subsequência inicia no índice: " << it_sub - numeros.begin() << endl;  // Saída: 1
}

count e count_if

count conta quantas vezes um valor aparece. count_if conta quantos elementos satisfazem um predicado.

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

for_each

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

std::vector<double> precos = {10.5, 20.0, 15.75};
std::for_each(precos.begin(), precos.end(), [](double& preco) { 
    preco *= 1.1; // Aplica um aumento de 10%
});

equal e mismatch

equal verifica se dois intervalos são idênticos. match retorna um par de iteradores apontando para o primeiro elemento não correspondente.

vector<int> conjunto_a = {10, 20, 30};
vector<int> conjunto_b = {10, 20, 40};

bool sao_iguais = equal(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin());
cout << "Conjuntos iguais? " << boolalpha << sao_iguais << endl;  // Saída: false

auto divergencia = mismatch(conjunto_a.begin(), conjunto_a.end(), conjunto_b.begin());
if (divergencia.first != conjunto_a.end()) {
    cout << "Divergência em: " << *divergencia.first << " vs " << *divergencia.second << endl; // Saída: 30 vs 40
}

all_of, any_of, none_of

Verificam se todos, algum, ou nenhum elemento de um intervalo atende a uma condição.

std::vector<int> valores = {4, 6, 8, 10};
bool todos_positivos = std::all_of(valores.begin(), valores.end(), [](int v) { 
    return v > 0; 
}); // true
bool existe_negativo = std::any_of(valores.begin(), valores.end(), [](int v) { 
    return v < 0; 
}); // false
bool nenhum_zero = std::none_of(valores.begin(), valores.end(), [](int v) { 
    return v == 0; 
}); // true

Algoritmos de Sequência Modificadores

Estes algoritmos alteram os elementos do contêiner.

copy e copy_if

copy transfere elementos entre intervalos. copy_if transfere apenas elementos que satisfazem um predicado.

vector<int> origem = {1, 2, 3, 4, 5};
vector<int> destino;
// Copia todos os elementos para um novo vetor
copy(origem.begin(), origem.end(), back_inserter(destino));

// Copia apenas os elementos ímpares
vector<int> impares;
copy_if(origem.begin(), origem.end(), back_inserter(impares), [](int x) {
    return x % 2 != 0;
});

transform

Aplica uma operação a cada elemento de um intervalo e armazena o resultado em outro.

vector<int> numeros = {2, 3, 4};
vector<int> cubos(numeros.size());

// Calcula o cubo de cada elemento (transformação unária)
transform(numeros.begin(), numeros.end(), cubos.begin(), [](int x) {
    return x * x * x;
});

// Calcula a soma elemento a elemento de dois vetores (transformação binária)
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {10, 20, 30};
vector<int> somas(v1.size());
transform(v1.begin(), v1.end(), v2.begin(), somas.begin(), [](int a, int b) {
    return a + b;
});

replace, replace_if e replace_copy

replace troca todas as ocorrências de um valor por outro. replace_if troca elementos baseado em um predicado. replace_copy realiza a substituição em uma cópia.

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

// Substitui todas as ocorrências de 2 por 200
replace(dados.begin(), dados.end(), 2, 200);

// Substitui valores maiores que 3 por 0
replace_if(dados.begin(), dados.end(), [](int x) {
    return x > 3;
}, 0);

// Cria uma cópia substituindo 3 por 300
vector<int> copia_modificada;
replace_copy(dados.begin(), dados.end(), back_inserter(copia_modificada), 3, 300);

remove, remove_if e o idiom erase-remove

remove não apaga elementos do contêiner; em vez disso, move os elementos a serem mantidos para o início e retorna um iterador para o novo final lógico. O apagamento físico ocorre com erase.

vector<int> numeros = {1, 2, 3, 4, 5, 2, 6};
// "Remove" logicamente todos os 2s
auto novo_final = remove(numeros.begin(), numeros.end(), 2);
// Apaga fisicamente os elementos indesejados
numeros.erase(novo_final, numeros.end());

// Combinação com remove_if para apagar elementos pares
vector<int> lista = {1, 2, 3, 4, 5};
lista.erase(remove_if(lista.begin(), lista.end(), [](int n) {
    return n % 2 == 0;
}), lista.end()); // lista agora contém {1, 3, 5}

unique

Remove duplicatas consecutivas. Normalmente é precedido por uma ordenação e seguido por erase.

std::vector<int> valores = {10, 10, 20, 20, 20, 30, 10};
auto final_unico = std::unique(valores.begin(), valores.end());
valores.erase(final_unico, valores.end()); // valores agora é {10, 20, 30, 10}

Algoritmos de Ordenação e Relacionados

sort, stable_sort e partial_sort

sort ordena os elementos, geralmente em O(n log n). stable_sort mantém a ordem relativa de elementos iguais. partial_sort ordena apenas os primeiros N elementos menores.

vector<int> dados = {9, 4, 7, 2, 8};
sort(dados.begin(), dados.end()); // Ordem crescente
sort(dados.begin(), dados.end(), std::greater<int>()); // Ordem decrescente

// Ordenação parcial: coloca os 3 menores elementos no início, ordenados
partial_sort(dados.begin(), dados.begin() + 3, dados.end());

nth_element

Patriciona o intervalo em torno do N-ésimo elemento, sem ordenar completamente o intervalo.

vector<int> serie = {5, 3, 1, 4, 2, 6};
// Encontra o 3º menor elemento (índice 2)
nth_element(serie.begin(), serie.begin() + 2, serie.end());
// serie[2] agora é 3, com <=3 à esquerda e >=3 à direita.

binary_search, lower_bound e upper_bound

Requerem um intervalo ordenado. binary_search verifica a existência. lower_bound e upper_bound definem intervalos de valores.

vector<int> ordenado = {2, 4, 4, 6, 8}; // Pré-ordenado

bool encontrado = binary_search(ordenado.begin(), ordenado.end(), 4); // true

auto limite_inferior = lower_bound(ordenado.begin(), ordenado.end(), 4); // Aponta para o primeiro 4
auto limite_superior = upper_bound(ordenado.begin(), ordenado.end(), 4); // Aponta para o 6

// Usando para inserir de forma ordenada
vector<int> nova_lista = {1, 3, 5};
auto posicao = lower_bound(nova_lista.begin(), nova_lista.end(), 4);
nova_lista.insert(posicao, 4); // nova_lista se torna {1, 3, 4, 5}

Algoritmos de Conjuntos (em intervalos ordenados)

Realizam operações de teoria dos conjuntos em intervalos previamente ordenados.

vector<int> s1 = {1, 2, 3, 5};
vector<int> s2 = {3, 4, 5, 6};
vector<int> resultado;

// União
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(resultado));

// Interseção
resultado.clear();
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(resultado));

// Diferença (s1 - s2)
resultado.clear();
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(resultado));

Algoritmos Numéricos (de <numeric>)

accumulate

Acumula resultados sobre um intervalo, seja uma soma, produto ou outra operação binária.

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

iota

Preenche um intervalo com valores sucessivos a partir de um valor inicial.

vector<int> indices(5);
iota(indices.begin(), indices.end(), 0); // Preenche com 0, 1, 2, 3, 4

partial_sum e adjacent_difference

partial_sum calcula somas acumuladas. adjacent_difference calcula diferenças entre elementos adjacentes.

vector<int> entrada = {2, 4, 6, 8};
vector<int> soma_parcial(entrada.size());
partial_sum(entrada.begin(), entrada.end(), soma_parcial.begin()); // {2, 6, 12, 20}

vector<int> diferencas(entrada.size());
adjacent_difference(entrada.begin(), entrada.end(), diferencas.begin()); // {2, 2, 2, 2}