Algoritmos de Consulta e Leitura

Esta categoria engloba funções que examinam os elementos de um container sem alterar seu estado interno. Elas são fundamentais para validações e buscas.

Busca e Contagem

Para localizar elementos específicos, utilizamos std::find para valores exatos ou std::find_if quando uma condição lógica precisa ser satisfeita. A função std::find_end é útil para identificar a última ocorrência de uma subsequência.

std::vector<int> dados = {10, 20, 30, 40, 50};

// Buscar o valor 30
auto it = std::find(dados.begin(), dados.end(), 30);
if (it != dados.end()) {
    std::cout << "Valor encontrado: " << *it << std::endl;
}

// Buscar primeiro valor múltiplo de 20
auto it2 = std::find_if(dados.begin(), dados.end(), [](int n) {
    return n % 20 == 0;
});

Para quantificar ocorrências, std::count verifica igualdade direta, enquanto std::count_if aplica um predicado personalizado.

Comparação e Verificação

A função std::equal valida se dois intervalos possuem conteúdos idênticos. Já std::mismatch retorna um par de iteradores apontando para a primeira divergência entre dois ranges.

Para validações booleanas em massa, existem std::all_of (todos satisfazem), std::any_of (algum satisfaz) e std::none_of (nenhum satisfaz).

std::vector<int> valores = {2, 4, 6, 8};
bool todosPares = std::all_of(valores.begin(), valores.end(), [](int n) {
    return n % 2 == 0;
});

Algoritmos de Modificação de Sequência

Estas funções alteram o conteúdo dos containers ou movem elementos entre eles.

Cópia e Transformação

std::copy transfere elementos para outro destino. Se houver uma condição de filtro, std::copy_if deve ser usado. O std::back_inserter é frequentemente utilizado para expandir containers dinamicamente durante a cópia.

Para aplicar operações matemáticas ou lógicas durante a transferência, std::transform é a escolha ideal, suportando operações unárias ou binárias (entre dois ranges).

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

// Elevar ao quadrado
std::transform(origem.begin(), origem.end(), destino.begin(), [](int n) {
    return n * n;
});

Substituição e Remoção

Substituições podem ser feitas in-place com std::replace ou std::replace_if. A variante std::replace_copy gera um novo container com as alterações.

Um ponto crucial é o comportamento do std::remove. Ele não diminui o tamanho do container; apenas move os elementos válidos para o início e retorna um iterador para o novo fim lógico. Para efetivar a remoção de memória, deve-se chaining com erase.

std::vector<int> lista = {1, 9, 2, 9, 3};
// Move os 9s para o final
auto novo_fim = std::remove(lista.begin(), lista.end(), 9);
// Reduz o tamanho real do vector
lista.erase(novo_fim, lista.end());

Outras utilidades incluem std::unique (remove duplicatas adjacentes), std::reverse (inverte ordem), std::rotate (rotaciona elementos) e std::shuffle (embaralha aleatoriamente).

Ordenação e Estruturas de Dados

Algoritmos de Sort

O std::sort é geralmente implementado via Introsort, oferecendo performance média O(n log n) sem garantir estabilidade. Quando a ordem relativa de elementos equivalentes precisa ser mantida, std::stable_sort é necessário. Para otimizar casos onde apenas os menores elementos interessam, std::partial_sort ordena apenas uma parte do range.

std::nth_element reorganiza o container de forma que o elemento na posição n esteja na posição correta como se estivesse ordenado, com todos à esquerda sendo menores e à direita maiores.

Busca Binária e Merge

Em containers já ordenados, std::binary_search verifica existência rapidamente. std::lower_bound e std::upper_bound retornam iteradores para posições específicas relativas ao valor buscado.

Para unir dois ranges ordenados mantendo a ordem, utiliza-se std::merge.

Operações de Heap

A STL permite tratar um range como um heap (pilha de prioridade). std::make_heap organiza os elementos, std::push_heap insere um novo eleemnto mantendo a propriedade, e std::pop_heap move o maior elemento para o final. std::sort_heap ordena o range baseado na estrutura de heap.

Utilitários Numéricos e de Conjunto

Localizados principalmente em <numeric>, estes algoritmos lidam com acumulação e geração.

• std::accumulate: Soma ou reduz elementos de um range.
• std::inner_product: Calcula o produto interno de dois ranges.
• std::iota: Preenche um range com valores sequencialmente crescentes.
• std::partial_sum: Gera um range com as somas parciais acumuladas.

Para operações de teoria dos conjuntos em ranges ordenados, existem std::set_union, std::set_intersection, std::set_difference e std::set_symmetric_difference.

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

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

Práticas e Considerações Técnicas

A escolha entre std::sort e std::stable_sort depende da necessidade de preservar a ordem original de elementos iguais. A estabilidade tem um custo de memória adicional.

O padrão "erase-remove" é obrigatório para remover elementos de containers sequenciais como std::vector, pois os algoritmos de remoção da STL operam apenas em iteradores e não conhecem o tamanho do container.

Algoritmos de busca binária e operações de conjunto exigem que os dados de entrada estejam previamente ordenados, caso contrário o comportamento é indefinido ou incorreto.