Nestes exercícios iremos desenvolver uma série de Funções que representam algoritmos típicos para manipulação de vetores, assim todas as funções receberão um range que deve ser operado como argumento.
O principal objetivo deste exercício é praticar programação usando estruturas de abstração de alto nível, onde seu código não precisa saber qual o tipo de dados ele está operando. Para fazer isso o nosso código precisa usar funções template associadas com ponteiros. Os templates dão suporte à criação de funções genéricas, enquanto os ponteiros nos ajudam a definir o range onde as operações serão executadas.
O objetivo secundário é adquirir exeperiencia de programação na construção de bibliotecas de operações típicas em vetores, chamaremos essa biblioteca de graal(Generic Array Algorithm Library). Através da experiencia de construir essa bibiliteca, iremos experimentar a importância da abstração de dados e reusabilidade de código no desenvolvimento de aplicações.
Um Iterator é usualmente representado por um objeto(uma instancia de uma Classe do paradígma de Programação Orientado à Objetos) que pode iterar sobre um container(que usualmente, também é um Objeto) sem saber como o container é implementado ou funciona internamente. Na STL, os iteradores são o método mais usado para acessar os elmentos em listas e outros containers.
Por exemplo, se quisermos itear sobre todos os elementos em um std::vector de inteiros para imprimir todos os elementos o código seria desta forma:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vect; // Declara um vetor de inteiros.
for (auto i(0) ; i < 6 ; ++i)
vect.push_back(i); // Insere elementos no vetor
vector<int>::const_iterator it; // Declara um iterator
it = vect.begin(); // Atribui ao iterator o inicio do vetor
while (it != vect.end()) { // Enquanto não chegou no fim
cout << *it << " "; // imprime o valor do elemento "apontado" pelo iterato
++it; // move para o próximo elemento
}
cout << endl;
}Veja que o uso dos Iterators é muito similar aos ponteiros. De fato, informalmente, um Iterator pode ser uma representação de um ponteiro encapsulada em uma representação mais abstrata(e com mais possibilidades).
Quando virmos mais à frente alguns containers da STL, vocé constatará que todas essas classes tem quatro métodos básicos que são projetados para ajudar ao usuário interar sobre os elementos:
- begin() retorna um iterator que aponta para o primeiro elemento de um container
- end() retorna um iterator que aponta para o final de um container. O final é representado por uma posição que está logo após o último elemento.
- cbegin() retorna um iterator (read-only) que aponta para o primeiro elemento de um container
- cend() retorna um iterator (read-only) que aponta para o final de um container. O final é representado por uma posição que está logo após o último elemento.
Um fato importante é que os iterators retornados por cend() e end() apontam sempre para uma posição após o ultimo elemento do container, como mostrado abaixo. Dessa forma, se deseramos definir um range de elementos em qualquer container sempre nos referimos a um intervalo [begin(), end()) -ou seja, sempre definimos um intevalo fechado-aberto!
begin() end()
↓ ↓
Índice | 0| 1| 2| 3| 4| 5| 6| 7| 8| 10| X|
Nos exercícios que seguem iremos treinar o uso e implementações com iteradores implementando funções template que podem receber tanto iterators da STL quanto ponteiros convencionais em suas chamadas, em ambos os casos, definidos sobre uma espaço sequencial de memória (um stati array ou um container da STL). Dessa forma, cada vez que uma das funções é chamada, precisamos informar o range onde a função vai operar.
Por exemplo, se o usuário da função deseja inverter os elementos de um array (usando a função reverse), a função deve receber dois ponteiros: um apontando para a posição inicial do range e outro apontando para a posição logo após o final do range, definindo assim os elementos que devem ser considerados na operação.
De forma similar se o usuário quiser inverter os elementos de um std::vector inteiro, ele poderá usar a mesma função reverse, porém passando dois iterators, correspondentes ao begin() e end() daquele vetor. Em termos de programação, não faz diferença já que estamos usando templates, lembre que essa funcionalidade do c++
permite a geração de código "sob demanda" durante a compilação.
Pelo ponto de vista de quem usa a função reverse, a chamada é reverse(std::being(A), std::end(A)), onde as funções std::begin() e std::end() são definidas na
biblioteca <iteartor> e retornam ponteiros para o início e "fim"(lembre que não é o último elemento, mas sim a posição logo após o último) de um array estático ou os
iterators apontando para as posições respectivas de begin() e end() de um container. É possível, usando esse mesmo formato, reverter apenas 4 elementos de um array fazendo
reverse(std::being(A), std::begin(A)+4), atente que o array precisa ter ao menos 4 elementos para que a chamada funcione.
Assim os exercícios que faremos são os seguintes: