Saltar para o conteúdo
Topos Uranos
Português

Arranjos

Resumo

Até aqui cada dado do curso viveu em sua própria variável, com seu próprio nome; mas muitos dados do mesmo tipo, como as temperaturas de uma semana, não podem ser percorridos com um laço se cada um tem um nome diferente. Esta aula apresenta a primeira estrutura de dados do curso, a sequência indexada: elementos do mesmo tipo, em posições contíguas da memória, numeradas a partir de zero. Em C++ moderno ela se escreve com std::array, cujo tamanho fica fixo ao compilar. Estudam-se sua declaração, o tipo std::size_t dos índices e os dois percursos, com índice e com o for baseado em intervalo. Estabelece-se a regra que governa toda a unidade: um índice é válido se está entre 0 e o tamanho menos um, e em cada acesso de um laço essa validade se justifica com o invariante. Mostra-se o que ocorre quando ela não se cumpre, que é comportamento indefinido, e compara-se [] com o acesso verificado .at(). E apresentam-se os arranjos de C, para ler código alheio.

Objetivos de aprendizagem

  1. Declarar, inicializar e percorrer um std::array com índices e com o for baseado em intervalo.
  2. Justificar, mediante o invariante do laço, que um índice está dentro dos limites em cada acesso.
  3. Distinguir o acesso com [], que o padrão não verifica, do acesso com .at(), que sempre é verificado, e explicar quando convém cada um.
  4. Ler código com arranjos de C e explicar suas desvantagens em relação a std::array.

A sequência indexada

Muitos dados, um só nome

Para calcular a média das temperaturas de uma semana com o que foi ensinado até aqui, seriam necessárias sete variáveis, monday, tuesday e assim por diante até sunday, e uma soma de sete termos. Com as de um ano seriam 365, e nenhum laço poderia percorrê-las, porque no corpo de um laço o nome de uma variável é sempre o mesmo. O que falta é um nome para o conjunto e um número para cada elemento, de modo que o número possa ser uma variável que o laço faz avançar.

Uma sequência indexada é exatamente isso: um conjunto de nn elementos do mesmo tipo, guardados um atrás do outro em posições contíguas da memória, e designados por sua posição, chamada índice. A matemática conhece o objeto: uma sucessão finita (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1}), na qual aia_i designa o elemento de lugar ii, ou um vetor, como os do curso Álgebra e Geometria I. Em C++ escreve-se a[i], e o índice pode ser qualquer expressão inteira: 2, i, i + 1.

Por que a partir de zero

Em C++, como na maioria das linguagens atuais, o primeiro elemento tem índice 0, e o último, índice n−1n - 1. A razão não é uma convenção caprichosa, mas a maneira como se encontra um elemento: se a sequência começa em certo endereço de memória e cada elemento ocupa ss bytes, o elemento de índice ii está no endereço inicial mais i⋅si \cdot s. O índice é, portanto, um deslocamento: a quantidade de elementos que é preciso saltar a partir do primeiro. O primeiro está a zero saltos de si mesmo.

Daí se segue a definição que governa toda esta unidade: numa sequência de nn elementos, um índice ii é válido se e somente se 0≤i<n0 \leq i < n. A desigualdade da direita é estrita, e é a fonte do erro mais frequente com sequências, o erro de um a mais: escrever i≤ni \leq n onde se devia escrever i<ni < n, ou começar em 1 onde se devia começar em 0. Um índice igual a nn não designa o último elemento, mas a posição que segue a sequência, que não lhe pertence.