Templates e STL

maior(3, 8) compara inteiros; maior(2.5, 1.5) compara reais. Um parâmetro de tipo permite escrever o mesmo corpo para ambos. A biblioteca padrão usa esta ideia para combinar contentores que guardam valores, iteradores que delimitam intervalos e algoritmos que trabalham nesses intervalos.

Funções template

template <typename T> introduz um parâmetro de tipo. typename e class são equivalentes nesta declaração simples. Na chamada maior(3, 8), o compilador deduz T = int; em maior(2.5, 1.5), deduz double.

O exemplo combina uma função e uma classe template; a pilha guarda os dados num vector, onde push_back acrescenta no fim, back consulta o último, pop_back remove-o e empty testa o vazio. A retirada verifica o vazio antes de usar back.

Programa completo para compilar localmente:

#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

template <typename T>
T maior(T a, T b) { return a < b ? b : a; }

template <typename T>
class Pilha {
public:
    void inserir(const T& valor) { dados_.push_back(valor); }
    T retirar() {
        if (dados_.empty()) throw std::out_of_range("Pilha vazia");
        T valor = dados_.back();
        dados_.pop_back();
        return valor;
    }
    bool vazia() const { return dados_.empty(); }
private:
    std::vector<T> dados_;
};

int main() {
    std::cout << maior(3, 8) << " " << maior(2.5, 1.5) << "\n";
    Pilha<std::string> palavras;
    palavras.inserir("primeira");
    palavras.inserir("segunda");
    std::cout << palavras.retirar() << " " << palavras.retirar() << "\n";
    std::cout << std::boolalpha << palavras.vazia() << "\n";
}

Saída:

8 2.5
segunda primeira
true

O corpo de maior exige que a < b seja válido. maior(3, 2.5) não deduz um único T, porque os argumentos têm tipos diferentes; escreve maior<double>(3, 2.5) para escolher double.

Um template não elimina requisitos dos tipos. maior(objeto1, objeto2) só funciona se esse tipo oferecer a comparação necessária. As definições dos templates têm de estar disponíveis quando o compilador as instancia, por isso ficam habitualmente no cabeçalho, ao contrário de funções não template cuja implementação pode ficar num .cpp separado.

Classes template

Pilha<std::string> e Pilha<int> são tipos distintos. Cada instância conserva a mesma disciplina, último a entrar, primeiro a sair, mas guarda valores de outro tipo. A retirada do exemplo copia o último valor antes de o remover e lança uma exceção se a pilha está vazia. Exige, portanto, um tipo copiável. Um tipo só com movimento precisaria de outra retirada, que devolvesse por movimento em vez de copiar.

Depois das inserções, a pilha contém primeira, segunda; a primeira retirada devolve segunda e deixa primeira, a seguinte devolve primeira e deixa o vetor vazio. Uma terceira retirada lançaria uma exceção, em vez de consultar um elemento inexistente.

vector: o array que cresce

std::vector<T> tem armazenamento contíguo, tamanho variável e acesso por índice. size() conta os elementos existentes; capacity() conta a capacidade em elementos. reserve(n) só aumenta a reserva quando n excede a capacidade atual; nunca a diminui nem cria elementos. resize(n) muda o tamanho, construindo ou destruindo elementos.

v[i] exige i < v.size() e não verifica o limite. v.at(i) verifica e lança std::out_of_range. front, back e pop_back exigem um vetor não vazio.

Reservar capacidade para dez elementos não permite escrever v[9] se o tamanho ainda é zero. Depois de reserve(3), o tamanho continua 0 e a capacidade passa a pelo menos 3. Depois de resize(3), existem os índices 0, 1 e 2.

push_back tem custo amortizado constante: algumas inserções são mais caras porque realocam e transferem os elementos. Inserir ou remover no meio desloca elementos e custa linear no número deslocado. A gestão automática de memória não elimina os custos das operações.

Escolher um contentor

Nesta tabela, n é o número de elementos. Os custos usuais de procura por chave pressupõem comparações ou dispersão de custo constante.

Uma lista não oferece acesso por índice. Encontrar o nó pode custar linear, mesmo que a remoção desse nó seja constante. stack e queue são adaptadores que expõem as operações de pilha e fila sobre um contentor subjacente. Escolhe pela sequência de operações de que precisas, não só por uma complexidade isolada.

map e set: chaves e conjuntos

#include <iostream>
#include <map>
#include <sstream>
#include <string>

int main() {
    std::istringstream entrada("azul verde azul vermelho verde azul");
    std::map<std::string, int> frequencias;
    std::string palavra;
    while (entrada >> palavra) ++frequencias[palavra];
    for (const auto& par : frequencias)
        std::cout << par.first << ": " << par.second << "\n";
    std::cout << std::boolalpha << (frequencias.find("branco") == frequencias.end())
              << " " << frequencias.size() << "\n";
}

Saída:

azul: 3
verde: 2
vermelho: 1
true 3

frequencias[palavra] insere a chave a zero se ela ainda não existe; serve para contar, mas surpreende numa simples consulta, por isso usa find quando queres consultar sem inserir. Cada elemento de um map é um pair<const Key, Valor>: par.first é a chave e par.second é a contagem.

map percorre as chaves pela ordem do comparador. set guarda apenas as chaves, sem o segundo valor, e ignora inserções repetidas de uma chave equivalente. unordered_map não oferece ordem de percurso fixa.

Iteradores

Um iterador identifica uma posição num contentor. begin() identifica o primeiro elemento e end() a posição depois do último. No vazio, são iguais. Um intervalo [first, last) pode representar o vazio sem caso especial; percorre enquanto it != last, lê *it e avança com ++it. Nunca desreferencies end().

// Excerto: v é um vector<int> já existente.
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

Iteradores têm capacidades diferentes. vector fornece acesso aleatório e permite it + 3. list fornece avanço e recuo, mas não soma de um deslocamento. std::sort exige acesso aleatório; numa list, usa a sua operação sort().

Invalidação de iteradores

Um iterador ou referência pode deixar de ser válido quando a coleção muda. Num vector, uma realocação invalida todos os iteradores, apontadores e referências aos elementos. Se uma inserção não realoca, os acessos anteriores à posição conservam-se, mas os da posição em diante, incluindo o antigo end, são invalidados. erase invalida os acessos na posição removida e posteriores.

Não guardes um iterador e continues a usá-lo depois de uma operação que o pode invalidar. Para remover durante um percurso de vector, a forma habitual é it = v.erase(it) quando removes, e ++it quando conservas. erase devolve um novo iterador válido para o elemento seguinte, ou end().

Em list e nos contentores associativos ordenados, remover um elemento invalida os acessos a esse elemento, e inserir normalmente não invalida os anteriores. As regras de deque e dos contentores de dispersão diferem; não generalizes a regra do vetor.

Algoritmos: sort e find

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

int main() {
    std::vector<int> valores = {5, 2, 3, 2, 1, 4, 5};
    std::sort(valores.begin(), valores.end());
    valores.erase(std::unique(valores.begin(), valores.end()), valores.end());
    valores.erase(std::remove_if(valores.begin(), valores.end(),
        [](int x) { return x % 2 == 0; }), valores.end());
    for (int x : valores) std::cout << x << " ";
    std::cout << "\n" << std::accumulate(valores.begin(), valores.end(), 0) << "\n";
}

Saída:

1 3 5
9

Depois de ordenar, unique compacta valores iguais adjacentes e devolve o novo fim lógico sem mudar o tamanho. No exemplo, o tamanho continua 7 até ao erase. O resultado lógico termina no iterador devolvido. As posições depois dele continuam desreferenciáveis, com estado válido mas não especificado, por isso o programa não conta com esses valores.

O primeiro erase apaga esse resto e reduz o tamanho para 5. O segundo remove os pares filtrados por remove_if.

find percorre até encontrar um valor ou chegar ao fim. count_if conta os que satisfazem um predicado. accumulate, de <numeric>, começa no valor inicial recebido; esse valor também influencia o tipo do acumulador. Para somar double, usa 0.0 quando queres acumulação real.

Uma lambda, como [](int x) { return x % 2 == 0; }, cria uma operação sem lhe dar um nome separado. Lê [] como a lista de capturas: vazia aqui, [limite] copia uma variável e [&limite] referencia-a. Uma captura por referência não prolonga a vida do objeto capturado. No programa de filtragem acima, a lambda decide que elementos são pares; remove_if desloca os restantes para o início.

Comparadores e pesquisa ordenada

Um comparador de ordenação deve representar “vem antes”, com uma relação estrita consistente. Para qualquer x, comp(x, x) tem de ser falso. Por isso a <= b não serve como comparador de sort: dá verdadeiro para valores iguais e quebra a exigência. Para desempatar objetos, compara primeiro o critério principal e depois o secundário:

// Excerto: ordena por nota e desempata por identificador.
struct Registo { int nota; int id; };
bool antes(const Registo& a, const Registo& b) {
    if (a.nota != b.nota) return a.nota < b.nota;
    return a.id < b.id;
}

Com {10:2, 10:1, 9:3}, a ordem é 9:3, 10:1, 10:2. Verificar apenas comp(x, x) == false não prova transitividade; prova só o caso mais simples. Um comparador que ordena por média e desempata por nome usa a mesma estrutura: primeiro o valor, depois a chave estável.

Para pesquisar, lower_bound encontra a primeira posição que não vem antes do valor procurado. O intervalo tem de estar particionado por esse critério, normalmente ordenado pelo mesmo comparador. Num vetor {1, 3, 5, 7}, procurar 5 devolve a posição 2; procurar 4 devolve a mesma posição, que contém 5. Encontrar uma posição de inserção não prova que o valor existe: confirma it != v.end() antes de ler *it e compara o valor encontrado com o procurado.

sort não garante a ordem anterior entre elementos equivalentes; stable_sort conserva-a. Procurar por pesquisa binária num vetor arbitrário não satisfaz a condição de partição.

Agregar por chave e ordenar pelo resultado

Um map<string, list<int>> liga cada estudante às suas notas e percorre os nomes pela ordem das chaves. Se o relatório pede ordem decrescente de média, esse percurso não chega. Calculamos um resumo por estudante e ordenamos os resumos pelo critério pedido, conservando o mapa original.

Cada lista contém entre 1 e 1000 notas inteiras de 0 a 20. O resultado usa a média de cada estudante e, no fim, a média das médias, dando o mesmo peso a cada estudante. Para o mapa vazio, escrevemos Sem estudantes. Estes contratos evitam dividir pelo tamanho de uma lista vazia ou pelo número zero de estudantes.

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <string>
#include <vector>

struct Media {
    std::string nome;
    double valor;
};

// Cada lista tem 1 a 1000 notas inteiras de 0 a 20.
void imprimir_medias(const std::map<std::string, std::list<int>>& notas) {
    std::vector<Media> resumo;
    double soma_medias = 0;
    for (const auto& estudante : notas) {
        double soma = 0;
        for (int nota : estudante.second) soma += nota;
        double media = soma / estudante.second.size();
        resumo.push_back({estudante.first, media});
        soma_medias += media;
    }
    std::sort(resumo.begin(), resumo.end(), [](const Media& a, const Media& b) {
        if (a.valor != b.valor) return a.valor > b.valor;
        return a.nome < b.nome;
    });
    std::cout << std::fixed << std::setprecision(2);
    for (const auto& estudante : resumo)
        std::cout << estudante.nome << " " << estudante.valor << "\n";
    if (resumo.empty()) std::cout << "Sem estudantes\n";
    else std::cout << "Global " << soma_medias / resumo.size() << "\n";
}

int main() {
    imprimir_medias({{"Ana", {10, 20}}, {"Bruno", {12}}, {"Carla", {13, 17}}});
}

Saída:

Ana 15.00
Carla 15.00
Bruno 12.00
Global 14.00

Ana tem (10 + 20) / 2 = 15, Bruno tem 12 / 1 = 12 e Carla tem (13 + 17) / 2 = 15. A soma começa em double, por isso a divisão não perde a parte fracionária. O vetor guarda os três pares nome/média, incluindo os dois com média 15. Um map<double, string> usaria a média como chave única e perderia um dos estudantes empatados.

O comparador põe a maior média primeiro e desempata por nome crescente. Comparar com > mantém a relação estrita; usar >= daria verdadeiro para um objeto comparado consigo próprio. O desempate por nome é uma escolha explícita deste exemplo, não uma consequência de sort nem uma regra atribuída à prova antiga.

No fim, (15 + 12 + 15) / 3 = 14. Juntar todas as notas daria 72 / 5 = 14,4: nesse cálculo, os estudantes com duas notas pesariam o dobro do que tem uma. O denominador e o peso de cada grupo vêm do contrato, não do contentor escolhido.

fixed com setprecision(2) formata a impressão com duas casas decimais; não arredonda as médias guardadas antes de ordenar ou calcular o total. Se duas médias diferentes aparecerem iguais no ecrã, a ordem continua a usar os valores calculados. Para m estudantes e g notas no total, a agregação percorre as g notas e a ordenação faz O(m log m) comparações; o vetor adicional guarda m resumos.