C++: Algoritmos STL

Na lição 34 aprendemos sobre contêineres STL — no que armazenar dados.

Mas contêineres por si só não são suficientes — você também precisa processar dados: buscar, ordenar, contar, transformar...

Escrever você mesmo poderia levar dezenas de linhas; com algoritmos STL, uma linha resolve.

1. Visão Geral dos Algoritmos STL

(1) 1.1 O que são Algoritmos STL?

Algoritmos STL são um conjunto de templates de funções genéricas fornecidos pela biblioteca padrão do C++ para manipular dados em contêineres.

Por que usar algoritmos STL?

Escrevendo você mesmo	Algoritmos STL
Precisa escrever loops	Uma linha de código
Propenso a erros	Extensivamente testados
Desempenho pode variar	Altamente otimizados
Código verboso	Código conciso

Analogia do mundo real:

Escrever algoritmos você mesmo = lavar roupas à mão (demorado e trabalhoso)
Algoritmos STL = máquina de lavar (um botão e pronto)

(2) 1.2 Arquivos de Cabeçalho dos Algoritmos

A maioria dos algoritmos STL está no cabeçalho algorithm, e algoritmos numéricos estão em numeric.

▶ Exemplo 2: Aplicação de Algoritmo STL (Dificuldade ⭐)

TEXT 📖 Somente leitura

#include <algorithm> // Most algorithms
#include <numeric> // Numeric algorithms (accumulate, etc.)

Saída:

TEXT 📖 Somente leitura

(program output)

(3) 1.3 Categorias de Algoritmos

Os algoritmos STL são divididos em várias grandes categorias por função:

Categoria	Algoritmos Representativos	Descrição
Não modificantes	`find`, `count`, `for_each`	Não modificam o conteúdo do contêiner
Modificantes	`copy`, `transform`, `replace`	Modificam o conteúdo do contêiner
Ordenação	`sort`, `stable_sort`, `partial_sort`	Relacionados à ordenação
Busca binária	`binary_search`, `lower_bound`	Busca em intervalos ordenados
Mesclagem	`merge`, `inplace_merge`	Mesclam intervalos ordenados
Numéricos	`accumulate`, `inner_product`	Computação numérica
Conjunto	`set_union`, `set_intersection`	Operações de conjunto

2. Algoritmos Não Modificantes

(1) 2.1 find — Encontrando Elementos

Função: Encontrar um elemento especificado em um contêiner, retornando um iterador.

Protótipo:

CPP

InputIt find(InputIt first, InputIt last, const T& value);

Exemplo: Encontrando uma nota (Dificuldade ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Find score 90
 auto it = std::find(scores.begin(), scores.end(), 90);
 
 if (it != scores.end()) {
 // Calculate position (index)
 int index = std::distance(scores.begin(), it);
 std::cout << "Found score 90 at position: " << index << std::endl;
 } else {
 std::cout << "Score 90 not found" << std::endl;
 }
 
 return 0;
}

Resultado:

TEXT 📖 Somente leitura

Found score 90 at position: 3

💡 Dica:

Retorna last (tipicamente end()) quando não encontrado
Complexidade de tempo: O(n)

(2) 2.2 count — Contagem

Função: Contar o número de elementos iguais a um valor especificado.

Exemplo: Contando notas perfeitas (Dificuldade ⭐)

CPP

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

int main() {
 std::vector<int> scores = {100, 85, 100, 92, 78, 100};
 
 // Count perfect scores (100)
 int perfect = std::count(scores.begin(), scores.end(), 100);
 
 std::cout << "Number of perfect scores: " << perfect << std::endl; // Output: 3
 
 return 0;
}

(3) 2.3 for_each — Iteração

Função: Executar uma operação especificada em cada elemento de um contêiner.

Exemplo: Imprimir todas as notas (Dificuldade ⭐)

TEXT 📖 Somente leitura

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Use a lambda expression to print each score
 std::for_each(scores.begin(), scores.end(), (int s) {
 std::cout << s << " ";
 });
 std::cout << std::endl;
 
 return 0;
}

Resultado:

TEXT 📖 Somente leitura

85 92 78 90 88

💡 Dica:

for_each é mais conciso que escrever loops manualmente
Muito poderoso quando combinado com expressões lambda

3. Algoritmos Modificantes

(1) 3.1 copy — Cópia

Função: Copiar elementos de um intervalo para outro.

Exemplo: Cópia de array (Dificuldade ⭐)

CPP

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

int main() {
 std::vector<int> src = {1, 2, 3, 4, 5};
 std::vector<int> dst(5); // Destination container, size 5
 
 // Copy
 std::copy(src.begin(), src.end(), dst.begin());
 
 // Print result
 for (int x : dst) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

(2) 3.2 transform — Transformação

Função: Transformar elementos de um intervalo e copiar para outro.

Exemplo: Notas ponderadas (Dificuldade ⭐⭐)

TEXT 📖 Somente leitura

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 std::vector<int> adjusted(scores.size()); // Adjusted scores
 
 // Regular coursework 70%, exam 30%
 std::transform(scores.begin(), scores.end(), adjusted.begin(),
 (int s) { return s * 0.7 + 90 * 0.3; });
 
 std::cout << "Adjusted scores: ";
 for (int x : adjusted) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Resultado:

TEXT 📖 Somente leitura

Adjusted scores: 86.5 91.9 81.6 90 88.6

(3) 3.3 replace — Substituição

Função: Substituir elementos iguais a um certo valor por outro valor.

Exemplo: Processamento de nota de recuperação (Dificuldade ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Replace failing scores (<60) with 60 (makeup exam passing line)
 std::replace_if(scores.begin(), scores.end(),
 (int s) { return s < 60; },
 60);
 
 std::cout << "Processed scores: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

4. Algoritmos de Ordenação

(1) 4.1 sort — Ordenação

Função: Ordenar um intervalo em um contêiner (crescente por padrão).

Exemplo: Ordenando notas (Dificuldade ⭐)

CPP

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

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Sort ascending
 std::sort(scores.begin(), scores.end());
 
 std::cout << "Ascending: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 // Sort descending
 std::sort(scores.begin(), scores.end(), std::greater<int>());
 
 std::cout << "Descending: ";
 for (int x : scores) {
 std::cout << x << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Resultado:

TEXT 📖 Somente leitura

Ascending: 78 85 88 90 92 
Descending: 92 90 88 85 78

(2) 4.2 Regras de Ordenação Personalizadas

Exemplo: Ordenar estudantes por nota (Dificuldade ⭐⭐)

CPP

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

struct Student {
 std::string name;
 int score;
};

int main() {
 std::vector<Student> students = {
 {"Zhang San", 85},
 {"Li Si", 92},
 {"Wang Wu", 78}
 };
 
 // Sort by score descending
 std::sort(students.begin(), students.end(),
 (const Student& a, const Student& b) {
 return a.score > b.score;
 });
 
 std::cout << "Score ranking:" << std::endl;
 for (const auto& s : students) {
 std::cout << s.name << ": " << s.score << std::endl;
 }
 
 return 0;
}

Resultado:

TEXT 📖 Somente leitura

Score ranking:
Li Si: 92
Zhang San: 85
Wang Wu: 78

5. Algoritmos Numéricos

(1) 5.1 accumulate — Soma

Função: Calcular a soma acumulada dos elementos em um intervalo.

Exemplo: Calcular nota total (Dificuldade ⭐)

CPP

#include <iostream>
#include <vector>
#include <numeric>

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88};
 
 // Calculate total score
 int total = std::accumulate(scores.begin(), scores.end(), 0);
 
 std::cout << "Total score: " << total << std::endl; // Output: 433
 std::cout << "Average: " << total / 5.0 << std::endl; // Output: 86.6
 
 return 0;
}

(2) 5.2 Produto Interno

Exemplo: Produto escalar de vetores (Dificuldade ⭐⭐)

CPP

#include <iostream>
#include <vector>
#include <numeric>

int main() {
 std::vector<int> v1 = {1, 2, 3};
 std::vector<int> v2 = {4, 5, 6};
 
 // Compute dot product: 1*4 + 2*5 + 3*6 = 32
 int dot_product = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
 
 std::cout << "Vector dot product: " << dot_product << std::endl; // Output: 32
 
 return 0;
}

6. Exemplo Abrangente

▶ Exemplo 1: Sistema de Análise de Notas (Dificuldade ⭐⭐⭐)

TEXT 📖 Somente leitura

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

int main() {
 std::vector<int> scores = {85, 92, 78, 90, 88, 76, 95, 83, 89, 91};
 
 // 1. Calculate total number of students
 int count = scores.size();
 std::cout << "Total students: " << count << std::endl;
 
 // 2. Calculate total and average score
 int total = std::accumulate(scores.begin(), scores.end(), 0);
 double average = static_cast<double>(total) / count;
 std::cout << "Total score: " << total << ", Average: " << average << std::endl;
 
 // 3. Find highest and lowest scores
 int max_score = *std::max_element(scores.begin(), scores.end());
 int min_score = *std::min_element(scores.begin(), scores.end());
 std::cout << "Highest: " << max_score << ", Lowest: " << min_score << std::endl;
 
 // 4. Count passing students
 int passed = std::count_if(scores.begin(), scores.end(),
 (int s) { return s >= 60; });
 std::cout << "Students passed: " << passed << std::endl;
 
 // 5. Sort and output top 3
 std::vector<int> top3 = scores;
 std::sort(top3.begin(), top3.end(), std::greater<int>());
 std::cout << "Top 3: ";
 for (int i = 0; i < 3; i++) {
 std::cout << top3[i] << " ";
 }
 std::cout << std::endl;
 
 return 0;
}

Saída:

TEXT 📖 Somente leitura

85 92 78 90 88 76 95 83 89 91

Resultado:

TEXT 📖 Somente leitura

Total students: 10
Total score: 867, Average: 86.7
Highest: 95, Lowest: 76
Students passed: 10
Top 3: 95 92 91

7. Dicas de Uso dos Algoritmos

(1) 7.1 Funções Auxiliares de Iterador

Função	Finalidade
`std::distance(first, last)`	Calcular a distância entre dois iteradores
`std::advance(it, n)`	Avançar um iterador em n passos
`std::next(it)`	Retornar o próximo iterador
`std::prev(it)`	Retornar o iterador anterior

(2) 7.2 Expressões Lambda Avançadas

Expressões lambda são ótimas companheiras dos algoritmos STL:

CPP

// Basic form
[capture](parameters) -> return_type { body }

// Example: Sort by multiple criteria
std::sort(students.begin(), students.end(),
 (const Student& a, const Student& b) {
 if (a.score != b.score)
 return a.score > b.score; // First by score
 return a.name < b.name; // Then by name
 });

❓ Perguntas Frequentes

P: Algoritmos STL são mais rápidos que loops? R: Algoritmos STL são tipicamente mais rápidos porque: - Altamente otimizados - Possuem versões especializadas para diferentes contêineres - Compiladores podem otimizá-los melhor

P: Todos os contêineres podem usar algoritmos STL? R: Teoricamente sim, mas a eficiência varia: - Contêineres sequenciais (vector, deque): alta eficiência - Contêineres associativos (set, map): possuem suas próprias funções membro, que são mais rápidas

P: O que são expressões Lambda? R: Lambdas são funções anônimas introduzidas no C++11 que podem ser definidas inline ondequer que uma função seja necessária.

Sintaxe básica:

TEXT 📖 Somente leitura

[capture](params) -> return_type { body }

Exemplo:

CPP

auto add = (int a, int b) { return a + b; };
std::cout << add(3, 5) << std::endl; // Output: 8

P: E se um algoritmo reportar um erro? R: Erros comuns: 1. Usar busca binária em um contêiner não ordenado → ordene primeiro 2. Contêiner de destino muito pequeno → use back_inserter 3. Incompatibilidade de tipo de iterador → verifique o tipo do contêiner

▶ Exemplo 3: sort (Dificuldade ⭐)

CPP

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

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};

    std::sort(v.begin(), v.end());

    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

▶ Experimente

Saída:

TEXT 📖 Somente leitura

1 2 3 4 5

💡 Dica: std::sort ordena em ordem crescente por padrão, recebendo um intervalo de iteradores [begin, end).

📖 Resumo

Algoritmos STL: templates de funções genéricas para manipular dados de contêineres
Algoritmos não modificantes: find, count, for_each
Algoritmos modificantes: copy, transform, replace
Algoritmos de ordenação: sort + funções de comparação personalizadas
Algoritmos numéricos: accumulate (soma)
Lambda: funções anônimas, usadas em combinação com algoritmos

Recomendações de estudo:

Use mais algoritmos STL, escreva menos loops manuais
Familiarize-se com algoritmos comuns; consulte a documentação para os menos comuns
Combine com expressões Lambda para código mais conciso

📝 Exercícios

Básico (Dificuldade ⭐): Crie um vector<int> com 10 números aleatórios, ordene com sort e exiba, depois inverta com reverse e exiba.
Intermediário (Dificuldade ⭐⭐): Use find para buscar uma string especificada em vectorstring, e use count para contar quantas vezes um valor aparece.
Desafio (Dificuldade ⭐⭐⭐): Use remove_if e uma lambda para implementar "remover todos os números pares de um vector". Entenda o idioma erase-remove.

Algoritmos STL operam em intervalos de iteradores, desacoplados dos contêineres
Algoritmos comuns: sort/find/count/copy/reverse
Categorias de algoritmos: somente leitura (find/count), escrita (copy/fill), ordenação (sort)
Expressões lambda como parâmetros de algoritmo são mais concisas
Algoritmos + lambda são mais concisos e seguros que loops escritos manualmente

Próxima lição: Prática: POO Abrangente (#36) — Refatorando o sistema de gerenciamento de estudantes usando pensamento orientado a objetos

Equipe Técnica Web-Tutorial

Uma plataforma de tutoriais mantida por diversos desenvolvedores. Cada tutorial é escrito e revisado por profissionais da área correspondente. Trabalhamos para manter nosso conteúdo preciso e confiável — se encontrar algum problema, avise-nos.

Sobre Nós