Algoritmos e Estruturas de
Dados I
A linguagem C++ permite ao programador
a utilização de um estilo de programação conhecido como “Programação Genérica”.
O tipo de problema que tenta ser resolvido é discutido a seguir. Um certo
comportamento ou uma certa estrutura tem um certo padrão, como definir o padrão
e deixar o compilador e o sistema de tempo de execução cuidar dos casos
especificos?
Um primeiro exemplo:
Um programador pode ter escrito as seguintes
funções:
void troca(int &p1, int &p2){ int aux=p1; p1=p2; p2=aux;}
void troca(double
&p1, double &p2){ double aux=p1; p1=p2; p2=aux;}
Podemos
>>definir<< uma função mais genérica (um “template” de função, um
conjunto de funções, uma família de funções)
template<typename TIPO> void troca(TIPO &p1, TIPO &p2){
TIPO aux(p1); p1=p2; p2=aux;
}
O trecho acima define um
“gabarito”, um “modelo” para funções. O trecho acima apenas informa ao
compilador que ele deve estar alerta para “invocações” que envolvem o nome
“troca”. O trecho acima não define 1 (uma) função, o trecho acima define um
“conjunto” de funções. Podemos agora “invocar” este “template” ou esta “função
genérica” para o caso de ints:
int a=10, b=20;
cout<<"a:"<<a<<"
b:"<<b<<endl;
troca(a,b); //esta é a forma abreviada
para troca<int>(a,b)
cout<<"a:"<<a<<"
b:"<<b<<endl;
A chamada acima corresponde
a instânciar uma função (função troca<int>()) além da chamada; Além deste estilo de
invocação (bastante conveniente) podemos invocar de maneira explícita a
“especialização” para o caso de ints:
int a=10, b=20;
cout<<"a:"<<a<<"
b:"<<b<<endl;
troca<int>(a,b);
cout<<"a:"<<a<<"
b:"<<b<<endl;
Observe a explicitação do
tipo int entre os símbolos menor e maior (troca<int>()). Verifique que este “gabarito” de
função também pode ser invocado para parâmetros do tipo double (ou qualquer
outro tipo que seja copiável). Este exemplo ilustra o uso de uma função
genérica.
-----
O exemplo abaixo é um
programa (simples) que define uma função genérica para ordenação por inserção.
#include <cstdlib>
#include <iostream>
using namespace std;
template<typename T> void ordenaPorInsercao(T a[], int N){
int i,j;
T aux;
for(i=1; i<N; i++){
aux=a[i];
j=i;
while(j>0&&a[j-1]>aux) a[j]=a[--j];
a[j]=aux;
}
}
int main(int argc, char *argv[])
{
int a1[]={50,20,30,10,40};
int ii;
for(ii=0; ii<5; ii++)
cout<<a1[ii]<<" ";
cout<<endl;
ordenaPorInsercao(a1,5);
for(ii=0; ii<5; ii++)
cout<<a1[ii]<<" ";
cout<<endl;
double a2[]={5.5, 2.2, 3.3, 1.1,
4.4};
for(ii=0; ii<5; ii++)
cout<<a2[ii]<<" ";
cout<<endl;
ordenaPorInsercao<double>(a2,5);
for(ii=0; ii<5; ii++)
cout<<a2[ii]<<" ";
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
O “conjunto de funções” ou
“função genérica” é ordenaPorInsercao<T>. No programa acima é feita uma instanciação/invocação
da função ordenaPorInsercao<int> e uma instanciação/invocação da função ordenaPorInsercao<double>.
É interessante observar que
a sentença a[j]=a[j--] apesar de compacta não é muito legível. Muitos
programadores preferem o trecho {a[j]=a[j-1]; j=j-1;} em função da
legibilidade. Mas no caso acima a sentença não funciona como desejado se
usarmos um arranjo de strings! Se trocarmos a sentença pelo trecho obtemos o
efeito desejado.
-----
O programa abaixo define um
tipo C que implementa uma comparação (operator<()) baseada na parte fracionária de um
valor do tipo double. O trecho abaixo é o programa acima definindo uma função
de ordenação para arranjos do tipo C. A ordenação em ordem crescente de {1.3,
2.2, 3.1} resulta em {3.1, 2.2, 1.3} porque a parte inteira é descartada e só é
considerada a parte fracionária.
#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
class C{private: double d;
friend ostream&
operator<<(ostream&, const C&);
static double intPart;
public:
C(){};
C(double p){d=p;}
int operator>(C&
that){return modf(d,&intPart)>modf(that.d,&intPart);}
};
double C::intPart;
ostream& operator<<(ostream& p, const C& c){
return p<<c.d;
}
template<typename T> void ordenaPorInsercao(T a[], int N){
int i,j;
T aux;
for(i=1; i<N; i++){
aux=a[i];
j=i;
while(j>0&&a[j-1]>aux) a[j]=a[--j];
a[j]=aux;
}
}
int main(int argc, char *argv[])
{
int ii;
C a3[]={C(1.5), C(2.2), C(3.3),
C(4.1), C(5.4)};
for(ii=0; ii<5; ii++)
cout<<a3[ii]<<" ";
cout<<endl;
ordenaPorInsercao<C>(a3,5);
for(ii=0; ii<5; ii++)
cout<<a3[ii]<<" ";
cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
Observe que a função global operator<<() necessita acessar um campo privado de C, para
que isso possa ser feito a classe C define operator<<() como sendo uma função “amiga”.
O programa acima faz uso de
um “idioma” condenado por muitos autores: a[j]=a[--j]; Na linguagem C isto “em geral” não
apresenta problemas, mas em C++ isso pode ser um defeito; melhor substituir por
{a[j]=a[j-1]; j--;}.
-----
Podemos ainda definir
classes genéricas ou “famílias de classes”:
template<typename TIPO> class X{ /*...*/ TIPO var; /* … */ };
Com a definição acima X corresponde a um “gabarito” de
classe, as vezes referido como X<TIPO>. O identificador X não é um nome de classe, pois agora
X é um item de uma definição de um conjunto de classes (X é o nome de uma
“classe-genérica”). O trecho acima define um “meta-tipo” de nome
“X<TIPO>”. Usando este meta-tipo podemos “instanciar”(ou definir) uma
classe da seguinte forma:
X<int>
var1;
X<double> var2;
X<bool> var3;
A variável var3 é do tipo classe
genérica X instanciada para o tipo bool (ou var3 é do tipo X<bool>).
Podemos ter instanciações mais “complexas”:
X<X<int>*> var4;
Neste último caso var4 é do
tipo da classe genérica X instanciada para um tipo apontador para objetos do
tipo X<int>.
Uma definição de função
genérica ou de classe genérica pode utilizar mais de um parâmetro:
template <typename
C1, typename C2> class X{/* …*/ C1 var1; C2 var2; /* … */ };
Existem restrições para a
instanciação que não serão discutidas neste material, exemplo de instanciação:
X<int, bool> var3;
Além do estilo de
instanciação apresentado acima, vários outros estilos são permitidos.
Um “template” deve ser
pensando como sendo um “modelo geral” para geração de funções ou para geração
de classes. Vários aspectos sintáticos e semânticos surgem então. Considere por
exemplo o seguinte trecho de programa:
template<typename TIPO> class C{public: static int x; /* …*/};
template<typename TIPO> int
C<TIPO>::x=8;
O trecho acima mostra a
sintaxe para definição e inicialização de um campo estático de uma classe
genérica. A variável x certamente também poderia ser do tipo TIPO:
template<typename TIPO> class C{public: static
TIPO x; /* … */};
template<typename TIPO> TIPO C<TIPO>::x=8;
O identificador do
parâmetro não importa, poderiamos ter escrito:
template<typename TIPO> class C{public: static int x; /* …*/};
template<typename T> int C<T>::x=8;
Quando existe um campo
estático cada uma das classes instanciadas a partir da classe genérica terá seu
próprio campo estático: um campo estático para cada classe distinta. Considere
a definição da classe genérica C<P> acima, nas especializações abaixo
teremos dois campos estáticos:
C<int> v1;
C<double> v2;
C<int>
v3;
Os objetos v1 e v3 são da
mesma classe e compartilham o campo estático x (na verdade C<int>::x), a classe do objeto v2 é distinta
com relação à classe dos objetos v1 e v2. O campo estático da classe
C<double> é C<Double>::x.
-----O que pode ser usado
além de typename?
Além do uso de parâmetros
da categoria “typename” os templates também podem utilizar os tipos da
linguagem C++ e gerar especializações para cada um dos valores destes tipos!
Veja a o exemplo de definição a seguir:
template<int I>
class D{
public:
static int x;
int getI(){return I;}
};
template<int I> int
D<I>::x=11;
No trecho acima foi
definida uma classe genérica que não depende de um <tipo> ela depende de
um <valor> (um valor de um certo tipo). A classe D acima pode ser
especializada para cada valor do tipo int e cada um destes valores terá um
campo estático x distinto dos demais.
------
Na linguagem C++ quase
todas as possibilidades de relacionamento entre classes comuns e classes
instanciadas de classes genéricas podem ser utilizadas. Em particular (i) uma classe comum pode ser base para
definição de uma classe genérica, (ii) uma classe genérica instanciada pode ser
base para uma classe comum e (iii) uma classe genérica instanciada pode ser
base para definição de uma classe genérica.
class Comum1{};
template<typename T> class Generica1: public
Comum1{/* ... */ };
class Comum2: public GenericaInstanciada<int>{
/* ... */ };
template<typename
TIPO> class Generica: public
Generica1<TIPO>{ /* ... */};
template<typename T1, typename
T2> class Generica3: public Generica1<T2>{ /* */};
O trecho acima ilustra
algumas das possibilidades da relação de herança. Nesta disciplina não iremos
investigar toda a sintaxe e semântica de programação genérica em C++. Em
particular não vamos estudar o que alguns chamam de “Metaprogramação” que pode
ser pelo menos apreciada com o pequeno “metaprograma” abaixo, baseado no livro
Metaprogramação com Moldes (C++ Template Metaprogramming):
#include <cstdlib>
#include <iostream>
using namespace std;
template<unsigned long N> struct binario{
static unsigned const valor
=binario<N/10>::valor <<
1 | N%10;
};
template<> struct binario<0>{
// especializacao
static unsigned const valor = 0;
};
int main(int argc, char *argv[]){
cout<<
binario<101010>::valor<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}
No trecho acima observe o
uso de “recursividade” no contexto de “templates”. Parece até um programa da
turma da linguagem Python.
Exercícios:
1.
A
diretiva “define” presente na linguagem C e C++ permite a “geração” de código
fonte de maneira similar ao template que também pode ser visto como um elemento
que permite a “geração”de código fonte. Qual a principal diferença em termos de
geração de código fonte entre “define” e “template”?
2.
A
invocação de um molde/gabarito de função pode explicitar ou não o parâmetro do
“template”. Escreva um exemplo similar à função troca() discutida acima que pode ser
invocada com parâmetros explicitos ou sem explicitar os parâmetros.
3.
A
função abaixo só ordena arranjos de elementos do tipo int. Escreva a função
genérica correspondente:
void ordenaPorSelecao(int a[], int N){
int i,j,aux,indMenor;
for(i=0; i<N-1; i++){
indMenor=i;
for(j=i+1; j<N; j++)
if(a[j]<a[indMenor])
indMenor=j;
aux=a[i]; a[i]=a[indMenor];
a[indMenor]=aux;
}
}
4.
Escreva
um programa que utiliza a função genérica da questão anterior.