1. Algoritmos de Consulta (Não Modificadores)

---

Esses algoritmos examinam os elementos sem alterá-los.

1.1 find e find_if

• find(inicio, fim, valor): retorna um iterador para o primeiro elemento igual ao valor fornecido, ou fim se não encontrado.
• find_if(inicio, fim, predicado): retorna o primeiro elemento que satisfaz o predicado.
• find_end(inicio, fim, sub_inicio, sub_fim): localiza a última ocorrência de uma subsequência.

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

// Procurar valor 5
auto it = std::find(numeros.begin(), numeros.end(), 5);
if (it != numeros.end()) {
    std::cout << "Encontrado: " << *it << '\n'; // 5
}

// Primeiro elemento maior que 6
auto it2 = std::find_if(numeros.begin(), numeros.end(),
                        [](int x){ return x > 6; });
std::cout << "Primeiro >6: " << *it2 << '\n'; // 7

// Última ocorrência de {3,5}
std::vector<int> sub = {3, 5};
auto it3 = std::find_end(numeros.begin(), numeros.end(),
                         sub.begin(), sub.end());
if (it3 != numeros.end()) {
    std::cout << "Subsequência começa no índice: "
              << (it3 - numeros.begin()) << '\n'; // 1
}

1.2 count e count_if

• count(inicio, fim, valor): conta quantas vezes o valor aparece.
• count_if(inicio, fim, predicado): conta elementos que satisfazem o predicado.

std::vector<int> dados = {1, 2, 3, 2, 4, 2};
int c = std::count(dados.begin(), dados.end(), 2);      // 3
int pares = std::count_if(dados.begin(), dados.end(),
                          [](int x){ return x % 2 == 0; }); // 4

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 &x){ x *= 2; });
// valores agora: {2, 4, 6, 8, 10}

1.4 equal e mismatch

• equal(inicio1, fim1, inicio2): verifica se dois intervalos são iguais elemento a eleemnto.
• mismatch(inicio1, fim1, inicio2): retorna um par de iteradores apontando para o primeiro par de elementos diferentes.

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

bool iguais = std::equal(a.begin(), a.end(), b.begin());  // false

auto dif = std::mismatch(a.begin(), a.end(), c.begin());
if (dif.first != a.end()) {
    std::cout << "Diferenca: " << *dif.first
              << " vs " << *dif.second << '\n';
}

1.5 all_of, any_of, none_of

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

2. Algoritmos Modificadores

---

Alteram o conteúdo do contêiner.

2.1 copy e copy_if

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

std::copy(origem.begin(), origem.end(), destino.begin()); // destino: [1,2,3,4,5]

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

2.2 transform

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

std::transform(nums.begin(), nums.end(), quadrados.begin(),
               [](int x){ return x * x; }); // quadrados: [1,4,9]

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> soma(3);
std::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, replace_copy

std::vector<int> valores = {1, 2, 3, 2, 5};

std::replace(valores.begin(), valores.end(), 2, 20); // [1,20,3,20,5]

std::replace_if(valores.begin(), valores.end(),
                [](int x){ return x > 10; }, 0); // [1,0,3,0,5]

std::vector<int> resultado;
std::replace_copy(valores.begin(), valores.end(),
                  std::back_inserter(resultado), 3, 300);
// resultado: [1,0,300,0,5], valores original inalterado

2.4 remove, remove_if e erase

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

auto novo_fim = std::remove(dados.begin(), dados.end(), 2);
dados.erase(novo_fim, dados.end()); // [1,3,4]

dados = {1, 2, 3, 4, 5};
dados.erase(std::remove_if(dados.begin(), dados.end(),
                           [](int x){ return x % 2 == 0; }),
            dados.end()); // [1,3,5]

2.5 unique

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

2.6 reverce

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

2.7 rotate

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

2.8 shuffle

#include <random>
std::vector<int> v = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(v.begin(), v.end(), gen);

3. Ordenação e Algoritmos Relacionados

---

3.1 sort, stable_sort e partial_sort

std::vector<int> v = {5, 3, 1, 4, 2};
std::sort(v.begin(), v.end()); // crescente: [1,2,3,4,5]
std::sort(v.begin(), v.end(), std::greater<int>()); // decrescente

std::vector<std::pair<int,int>> p = {{1,2},{2,1},{1,1},{2,2}};
std::stable_sort(p.begin(), p.end(),
                 [](const auto &a, const auto &b){ return a.first < b.first; });

std::vector<int> v2 = {5, 3, 1, 4, 2, 6};
std::partial_sort(v2.begin(), v2.begin() + 3, v2.end());
// os 3 menores (1,2,3) ficam ordenados no início

3.2 nth_element

std::vector<int> v = {5, 3, 1, 4, 2, 6};
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] == 3, elementos à esquerda <=3, à direita >=3

3.3 binary_search, lower_bound, upper_bound

Reequerem contêiner ordenado.

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

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

auto lb = std::lower_bound(ord.begin(), ord.end(), 3);
std::cout << "Índice lower_bound: " << (lb - ord.begin()) << '\n'; // 1

auto ub = std::upper_bound(ord.begin(), ord.end(), 3);
std::cout << "Índice upper_bound: " << (ub - ord.begin()) << '\n'; // 3

3.4 merge

std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> result(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), result.begin());
// result: [1,2,3,4,5,6]

4. Algoritmos de Heap

---

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

h.push_back(6);
std::push_heap(h.begin(), h.end()); // [6,4,5,2,1,3]

std::pop_heap(h.begin(), h.end()); // move maior para o fim
int topo = h.back(); // 6
h.pop_back();

std::sort_heap(h.begin(), h.end()); // ordena crescentemente: [1,2,3,4,5]

5. Algoritmos de Mínimo/Máximo

---

5.1 min e max

int x = 5, y = 3;
int menor = std::min(x, y); // 3
int maior = 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

std::vector<int> v = {3, 1, 4, 2, 5};
auto it_min = std::min_element(v.begin(), v.end()); // aponta para 1
auto it_max = std::max_element(v.begin(), v.end()); // aponta para 5

5.3 minmax_element (C++11)

auto par = std::minmax_element(v.begin(), v.end());
// par.first aponta para 1, par.second aponta para 5

6. Algoritmos Numéricos (<numeric>)

---

6.1 accumulate

#include <numeric>
std::vector<int> v = {1, 2, 3, 4, 5};
int soma = std::accumulate(v.begin(), v.end(), 0); // 15
int prod = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>()); // 120

6.2 inner_product

std::vector<int> p = {1, 2, 3};
std::vector<int> q = {4, 5, 6};
int dot = std::inner_product(p.begin(), p.end(), q.begin(), 0); // 32

6.3 iota

std::vector<int> r(5);
std::iota(r.begin(), r.end(), 10); // [10,11,12,13,14]

6.4 partial_sum

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

6.5 adjacent_difference

std::vector<int> dif_src = {1, 2, 3, 4, 5};
std::vector<int> dif_dst(dif_src.size());
std::adjacent_difference(dif_src.begin(), dif_src.end(), dif_dst.begin());
// [1,1,1,1,1]

7. Outros Algoritmos

---

7.1 generate

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

7.2 generate_n

std::vector<int> gn(5);
int m = 10;
std::generate_n(gn.begin(), 3, [&m]{ return m++; });
// [10,11,12,0,0] (valores não inicializados permanecem)

7.3 includes

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

7.4 Operações de Conjunto

std::vector<int> s1 = {1, 2, 3, 4, 5};
std::vector<int> s2 = {3, 4, 5, 6, 7};
std::vector<int> res;

std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
               std::back_inserter(res)); // [1,2,3,4,5,6,7]

res.clear();
std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                      std::back_inserter(res)); // [3,4,5]

res.clear();
std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                    std::back_inserter(res)); // [1,2]

res.clear();
std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
                              std::back_inserter(res)); // [1,2,6,7]

8. Perguntas Frequentes

---

1. Diferença entre sort e stable_sort?
   sort usa introsort (instável), complexidade média O(n log n). stable_sort usa mergesort, estável, com a mesma complexidade porém maior uso de memória.
2. Por que remove precisa de erase?
   remove apenas reposiciona os elementos a serem mantidos para o início, retornando um iterador para o novo fim lógico. O tamanho físico do contêiner não é alterado; erase remove a faixa do fim lógico até o fim real.
3. Quais algoritmos exigem contêiner ordenado?
   Algoritmos de busca binária (binary_search, lower_bound, upper_bound), operações de conjunto (set_union, etc.), merge e includes dependem de ordenação para funcionar eficientemente.