# C++ para acompanhar os algoritmos

Vetores, referências, iteradores, comparadores e casos vazios usados nos exemplos.

Página: https://resumos.rgo.pt/cadeiras/aed/fundamentos-cpp/

Os exemplos de AED usam C++17 e índices a partir de zero. Funções, ciclos e classes vêm de [Programação](https://resumos.rgo.pt/cadeiras/p/). 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.

**main.cpp**

```cpp
#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](https://resumos.rgo.pt/cadeiras/aed/tipos-abstratos/#mem%C3%B3ria-c%C3%B3pia-e-iteradores) 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](https://resumos.rgo.pt/cadeiras/aed/ordenacao/#estabilidade-e-compara%C3%A7%C3%A3o-v%C3%A1lida).

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](https://resumos.rgo.pt/cadeiras/aed/tipos-abstratos/#mem%C3%B3ria-c%C3%B3pia-e-iteradores).

`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](https://resumos.rgo.pt/cadeiras/aed/complexidade-invariantes/#recorr%C3%AAncias-e-espa%C3%A7o), 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:

[Vídeo: Aprende C++ em 40 minutos](https://www.youtube.com/watch?v=iC0sEBfcm4g)

[Abrir no YouTube](https://www.youtube.com/watch?v=iC0sEBfcm4g)

## Exercícios

As justificações e os programas em C++ são de autoavaliação. Compara o raciocínio com os critérios da solução.

Alterar os elementos que o chamador vê

Uma função recebe `std::vector<int> v` e executa `for (int x : v) x *= 2;`. O chamador tem `[3,5]` e pretende obter `[6,10]`. O que precisa de mudar? Explica os dois níveis de cópia e o caso vazio. Assume que cada valor duplicado cabe em `int`.

Pista

O parâmetro e a variável do ciclo são cópias independentes.

Solução

Usa `std::vector<int>& v` e `for (int& x : v) x *= 2;`, porque a primeira referência evita copiar o vetor e a segunda modifica cada elemento desse vetor. Sem a segunda, só mudam as cópias locais `x`. Sem a primeira, só mudaria o vetor copiado. No vazio, o ciclo faz zero iterações.

Confere a tua resposta:

*   Usei uma referência ao vetor no parâmetro.
*   Usei uma referência ao elemento no ciclo.
*   Obtive \[6,10\] no chamador e tratei o vazio sem acesso inválido.

Erros frequentes

Não uses `const` numa referência que precisa de alterar os valores.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/fundamentos-cpp/#refer%C3%AAncias-e-c%C3%B3pias)

Percorrer ao contrário sem subtrair a zero

Escreve um ciclo que percorra um vetor ao contrário, incluindo o caso vazio, com `std::size_t`. Porque é perigoso começar em `v.size()-1` e testar `i>=0`?

Pista

Num inteiro sem sinal, `i>=0` nunca se torna falso.

Mais uma pista

Mantém `i` uma posição depois do elemento a consultar.

Solução

Usa `for (std::size_t i=v.size(); i>0; --i)` e consulta `v[i-1]`. Em `[7,2]`, `i` vale 2 e 1, dando 2 e 7. No vazio, o teste falha antes de qualquer acesso. Começar em `size()-1` subtrai a zero no vazio, porque o teste `i>=0` nunca é falso num inteiro sem sinal e uma redução posterior de zero dá um valor enorme.

Confere a tua resposta:

*   Comecei em size(), consultando i-1 apenas quando i>0.
*   Mostrei que \[7,2\] é visitado como 2,7.
*   Justifiquei zero acessos no vazio e ausência de subtração sem sinal a zero.

Erros frequentes

Trocar só o teste para `i>0` e consultar `v[i]` omite a posição zero.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/fundamentos-cpp/#vetores-e-intervalos)

Procurar sem desreferenciar o fim

Em `[4,7,2]`, usa `find` para 7 e 9. O que devolve cada procura e quando podes usar `*it`? Inclui o vetor vazio.

Pista

O fim marca ausência, não um elemento.

Solução

Para 7, devolve a posição 1; podes ler `*it`. Para 9 e para o vazio, devolve `end()`; não podes desreferenciar.

Confere a tua resposta:

*   Distingui encontro de ausência com end().
*   Mostrei a posição 1 para 7 em \[4,7,2\] e end() para 9.
*   Tratei o vazio com begin()==end().

Erros frequentes

Ler `*end()` não tem resultado garantido.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/aed/fundamentos-cpp/#iteradores-e-biblioteca-padr%C3%A3o)