Docs executáveis de C++: Algoritmos

Q: Como verifico se um valor existe em um vector em C++?

Use std::find: auto it = find(v.begin(), v.end(), target);. Se it == v.end() o valor não está presente; caso contrário it aponta para a primeira correspondência. Para testar uma condição em vez de um valor exato, use std::any_of com um predicado.

Laços que você não precisa escrever

Na página anterior você viu que todo contêiner entrega iteradores - cursores leves com begin() e end(). Essa abstração é a razão de existir dos algoritmos padrão. Em vez de escrever um laço for cru toda vez que quer buscar, contar ou transformar dados, você chama uma função nomeada de <algorithm> e entrega a ela um intervalo.

Um intervalo é só dois iteradores: onde começar e um além de onde parar. Como todo algoritmo fala essa mesma linguagem de iteradores, o mesmo find funciona em um vector, uma string ou um array simples.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // 16 está no intervalo [begin, end)?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

O padrão a internalizar: um algoritmo de busca devolve o iterador end() para dizer "nada encontrado". Sempre compare com end() antes de desreferenciar o resultado - desreferenciar end() é comportamento indefinido.

Contar e testar com predicados

Muitos algoritmos recebem um predicado - uma função (geralmente uma lambda) que devolve bool para cada elemento. count_if conta as correspondências; all_of, any_of e none_of respondem perguntas de sim/não sobre todo o intervalo.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 aprovados
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count (sem _if) é o primo mais simples que conta um valor exato em vez de uma condição. Recorra às versões com predicado assim que seu teste for "qualquer coisa que satisfaça uma regra" em vez de "este valor específico".

Transformar e reduzir um intervalo

Dois cavalos de batalha cobrem a maior parte do processamento de dados: std::transform mapeia cada elemento por meio de uma função, e std::accumulate (do <numeric>, não do <algorithm>) dobra um intervalo até um único valor.

transform escreve seus resultados por meio de um iterador de saída. Um erro comum e perigoso é apontar a saída para um vector vazio - o algoritmo presume que já há espaço e escreve além do fim. Ou dimensione o destino primeiro, ou use um back_inserter para que cada resultado seja inserido com push_back.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // vazio - ainda sem espaço

    // back_inserter faz `squares` crescer à medida que os resultados chegam
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate parte de um valor inicial e combina os elementos da esquerda para a direita. O tipo do valor inicial importa: passe 0 (um int) e a soma é calculada em int, o que pode estourar ou truncar.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // Comece com 0.0 (double) para que o total acumulado continue double.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

Se você tivesse escrito accumulate(prices.begin(), prices.end(), 0) com uma semente int, cada adição aconteceria em int e os centavos sumiriam. O tipo da semente determina silenciosamente o tipo do resultado.

O idiom erase-remove

Aqui está a pegadinha que surpreende todo mundo. std::remove não remove nada do contêiner. Os algoritmos só têm iteradores, então não conseguem mudar o tamanho de um contêiner - eles nem sabem que existe um. O que remove faz de fato é mover todos os elementos mantidos para o início, deixando a cauda em um estado não especificado, e devolver um iterador para o novo fim lógico.

// remove sozinho deixa o tamanho inalterado - este é o bug:
remove(v.begin(), v.end(), 0);  // devolve um iterador que você ignorou
// v ainda tem seu tamanho original; a cauda é lixo

Para realmente apagar os elementos você combina remove com o erase do contêiner, e é por isso que se chama idiom erase-remove:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove empurra os não-zeros para frente, devolve o novo fim
    // 2. erase corta tudo dali até o fim real
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

Use remove_if para um predicado em vez de um valor exato. No C++20 você pode pular toda a dança com as funções livres std::erase / std::erase_if, que fazem os dois passos por você: erase(v, 0);.

Iteradores sobrevivem à sua validade por sua conta e risco

Como os algoritmos devolvem iteradores, esses iteradores estão sujeitos às mesmas regras de invalidação que você viu na página anterior. Guardar um iterador e depois modificar o contêiner - um push_back que dispara uma realocação, ou um erase - pode deixar o iterador guardado pendurado, e usá-lo é comportamento indefinido.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // pode realocar o armazenamento de v
cout << *it;       // BUG: `it` pode agora apontar para memória liberada

O hábito seguro: use o iterador que um algoritmo devolve imediatamente, antes de qualquer operação que possa redimensionar ou realocar o contêiner. Se você precisa modificar o contêiner com base em um resultado, capture um índice (it - v.begin()) em vez disso, já que os índices sobrevivem à realocação.

Próximo: Ordenação

Você já viu como buscar, contar, transformar e reduzir - mas um algoritmo é importante o suficiente para merecer a própria página. std::sort reordena um intervalo no lugar, e assim que os dados estão ordenados toda uma família de algoritmos mais rápidos e exclusivos para dados ordenados (binary_search, lower_bound, equal_range) se abre. A seguir vamos nos aprofundar na ordenação: como fornecer um comparador personalizado, a diferença entre sort e stable_sort, e as regras que sua função de comparação precisa obedecer para evitar comportamento indefinido.

Perguntas frequentes

O que é o cabeçalho <algorithm> em C++?

<algorithm> é o cabeçalho da biblioteca padrão que contém funções genéricas como std::find, std::sort, std::count_if e std::transform. Elas operam sobre intervalos descritos por um par de iteradores (normalmente begin() e end()), então o mesmo algoritmo funciona em um vector, array, string ou qualquer contêiner que exponha iteradores.

Como verifico se um valor existe em um vector em C++?

Use std::find: auto it = find(v.begin(), v.end(), target);. Se it == v.end() o valor não está presente; caso contrário it aponta para a primeira correspondência. Para testar uma condição em vez de um valor exato, use std::any_of com um predicado.

Por que std::remove não remove de fato os elementos do meu contêiner?

Os algoritmos só enxergam iteradores, não o contêiner, então std::remove não consegue encolhê-lo - ele empurra os elementos mantidos para o início e devolve um iterador para o novo fim lógico. Você precisa segui-lo com v.erase(...) (o idiom erase-remove) para descartar fisicamente os restos.

Conceitos relacionados