C++ para acompanhar os algoritmos

Os exemplos de AED usam C++17 e índices a partir de zero. Funções, ciclos e classes vêm de Programação. Esta página fixa apenas o que os algoritmos seguintes usam: como ler um intervalo sem sair do vetor, quando uma cópia não altera o original e o que um iterador pode deixar de apontar.

Vetores e intervalos

Com std::vector<int> v{4,7,2}, as posições 0, 1 e 2 guardam 4, 7 e 2. v.size() vale 3. Conta os elementos que existem, não a capacidade reservada.

v[i] só é válido com 0<=i<v.size(). v.empty() testa se não há elementos. v.push_back(9) produz [4,7,2,9]. v.pop_back() retira o 9 sem o devolver.

Consultar front() ou back() e retirar com pop_back() exige um vetor não vazio. Reservar espaço com reserve(10) não cria dez elementos. Não autoriza consultar v[9].

Os algoritmos usam o intervalo semiaberto [l,r): inclui l, exclui r, tem r-l posições e é vazio quando l==r. O vetor inteiro é [0,v.size()). Para [4,7,2], [1,3) contém 7 e 2, e [3,3) é vazio. A posição 3 pode marcar o fim do intervalo sem conter um elemento.

std::size_t, o tipo de size(), é um inteiro sem sinal, ou seja, subtrair 1 a zero produz um valor muito grande. Para percorreres ao contrário sem esse erro, começa em i=v.size() e, enquanto i>0, consulta v[i-1] e reduz i. Para representar ausência, as lições usam uma posição de fim, std::optional ou um índice com sinal e valor -1, conforme o contrato.

Referências e cópias

Passar std::vector<int> v por valor cria uma cópia. Alterar essa cópia não altera o vetor do chamador. std::vector<int>& v refere o mesmo vetor e permite alterá-lo. const std::vector<int>& v permite lê-lo sem copiar nem alterar os seus elementos através dessa referência.

Num ciclo for (int x : v), x recebe uma cópia de cada valor. Em for (int& x : v), x refere-se ao elemento. Uma atribuição altera o vetor. auto deduz o tipo a partir da expressão inicial. Não significa que o tipo muda durante a execução.

#include <iostream>
#include <vector>
void alterarCopia(std::vector<int> v) {
    if (!v.empty()) v[0] = 99;
}
void duplicar(std::vector<int>& v) {
    for (int& x : v) x *= 2;
}
int main() {
    std::vector<int> v{4, 7, 2};
    alterarCopia(v);
    std::cout << "apos copia: " << v[0] << '\n';
    duplicar(v);
    for (std::size_t i = v.size(); i > 0; --i)
        std::cout << (i == v.size() ? "" : " ") << v[i - 1];
    std::cout << '\n';
    std::vector<int> vazio;
    duplicar(vazio);
    std::cout << "vazio: " << vazio.size() << '\n';
}

alterarCopia escreve 99 numa cópia. A primeira linha continua a ser apos copia: 4. duplicar altera o vetor do chamador para [8,14,4]. O percurso inverso escreve 4 14 8.

São necessárias as duas referências: a do parâmetro e a de x no ciclo. No vazio, os ciclos fazem zero iterações sem acesso inválido. Os valores duplicados cabem em int neste exemplo. Para dados gerais, verifica os limites antes de multiplicar.

Iteradores e biblioteca padrão

Um iterador identifica uma posição num container. v.begin() identifica o primeiro elemento, se existir. v.end() identifica a posição depois do último e nunca deve ser desreferenciado com *. No vazio, os dois coincidem.

std::find(v.begin(),v.end(),x) procura sequencialmente e devolve end() quando não encontra x. Com [4,7,2], procurar 7 devolve o iterador da posição 1 e it-v.begin()=1. Procurar 9 devolve end(). No vazio, begin()==end() e qualquer procura devolve end().

O intervalo de iteradores também é semiaberto: std::sort(v.begin(),v.end()) ordena todo o vetor. Para usares sort e find, inclui <algorithm>. Para vector, inclui <vector>. O prefixo std:: indica nomes da biblioteca padrão. A sigla STL aparece nos materiais para os seus containers, iteradores e algoritmos.

Num vetor, it-v.begin() dá a posição e it+k avança diretamente k posições, dentro dos limites válidos. Numa lista ligada, o iterador avança pelas ligações, ou seja, não podes usar estas operações como se o armazenamento fosse contíguo. As regras de invalidação indicam quando uma alteração torna um iterador antigo inválido.

Comparadores, apontadores e ausência

Um comparador responde se um elemento deve vir antes do outro. A expressão [](int a, int b) { return a < b; } cria uma função sem nome, ou lambda, que recebe dois inteiros. [] indica que não precisa de valores exteriores; [p] guarda uma cópia de p, como no comparador angular da envolvente convexa. A comparação tem de respeitar uma ordem fraca estrita.

Um apontador No* p guarda o endereço de um nó. nullptr indica que não aponta para nenhum nó, por isso só usa p->campo depois de garantires que p aponta para um nó válido. new No{...} cria um nó dinâmico e delete p liberta-o; a referência a esse nó deixa de ser válida depois da libertação. Uma classe que possui nós tem de decidir quem os liberta e como pode ser copiada.

std::optional<T>, disponível em <optional>, representa um valor do tipo T ou ausência. std::nullopt devolve ausência e if (r) verifica se existe um valor antes de usares *r. É diferente de usar zero como erro, porque zero pode ser uma resposta válida, por exemplo numa soma.

Contas e chamadas recursivas

Em inteiros, 7/2 vale 3, porque a divisão trunca a parte fracionária. Por isso 7/2*8 vale 24 e 7*8/2 vale 28. Uma fórmula matemática pode precisar de outra ordem de operações ou de um tipo mais largo. Em 1LL*a*b, a multiplicação já usa long long; converter o resultado de a*b só depois não impede um overflow que já ocorreu.

Uma função recursiva suspende a chamada atual para resolver um caso menor e retoma-a quando esse resultado chega. Na análise das recorrências, distingue o caso base, a redução do problema e o trabalho local. Não assumes que o compilador elimina a memória de chamadas suspensas.

Para uma revisão mais ampla da linguagem, podes consultar Rodrigo Dias:

Aprende C++ em 40 minutosCarregar vídeo do YouTube

Abrir no YouTube