List templates
Vamos considerar a lista ligada (singly linked list)
O objecto da classe
slink
struct slink {
slink* next;
slink() { next=0; }
slink(slink* p) { next=p; } };
next
NULL
slink() { next = 0; }
O objecto da classe
slink
O objecto da classe
slink
next
slink(slink* p) { next = p; }
Agora podemos definir a classe slist_base que pode conter os
objectos de qualquer classe derivada de slink:
class slist_base {
slink* last; // last->next é a cabeça da lista
public:
void insert(slink* a); // incluir na cabeça da lista
void append(slink* a);
// incluir no final da lista
slink* get();
// retornar e remover a cabeça
void clear() { last = 0; }
slist_base() { last = 0; }
// o primeiro construtor
slist_base(slink* a) { last = a->next = a; }
// o segundo construtor
class bad_last {};
// a classe de excepções
friend class slist_base_iter; // a classe iterador
};
O nome slist_base significa que a classe vai ser usada como a base
para (classes de listas ligadas) singly linked list classes.
Vamos considerar a implementação
das funções diferentes pertencentes à classe slist_base. Elas são
insert, append e get.
void slist_base::insert(slink* a)
{
if(last)
a->next = last->next;
else
last = a;
last->next = a;
}
next
last->next é a cabeça da lista
a
void slist_base::insert(slink* a)
{
if(last)
a->next = last->next;
else
else
last
last == a;
a;
last->next
last->next == a;
a;
}
next
a=last
next
a last
last=0
void slist_base::insert(slink* a)
{
if(last)
a->next = last->next;
else
last = a;
last->next = a;
}
next
last0
a
next
last
next
last
next
void slist_base::insert(slink* a)
{
if(last)
a->next = last->next;
else
last = a;
last->next = a;
}
next
last0
a
next
last
next
last
next
void slist_base::insert(slink* a)
O objecto da classe
slink
last->next
slink
a->next
{ if(last)
a->next = last->next;
else
last = a;
last->next = a;
}
a->next = last->next;
O objecto da classe
slink
last->next
last->next = a;
incluir na
cabeça da
lista
void slist_base::append(slink* a)
{
if(last) {
a->next = last->next;
last = last->next = a; }
else
last = a->next = a;
}
next
a
void slist_base::append(slink* a)
{
if(last) {
a->next = last->next;
last = last->next = a; }
else
last = a->next = a;
}
next
a
last
last=0
void slist_base::append(slink* a)
{
if(last) {
a->next = last->next;
last = last->next = a; }
else
last = a->next = a;
}
next
last0
a
last
last->next
last->next é a cabeça da lista
next
last
next
next
last
void slist_base::insert(slink* a)
next
last
Cabeça
next
a
void slist_base::append(slink* a)
Cabeça
Final
next
last
next
void slist_base::append(slink* a)
O objecto da classe
slink
last->next
slink
a->next
{ if(last)
a->next = last->next;
last = last->next = a;
else
last = a->next = a; }
a->next = last->next;
O objecto da classe
slink
last->next
last->next = a;
incluir no
final da
lista
A seguinte figura mostra como as funções insert e append funcionam.
a
insert
a
O primeiro objecto
append
O primeiro objecto
last->next
a->next = a
last=a
a
a
last
incluir na
cabeça
new
last
incluir no
final
new
last
slink* slist_base::get()
{
if (last == 0) throw bad_last();
slink* f = last->next;
if ( f == last)
last = 0;
else
last->next = f->next;
return f;
}
slink* slist_base::get()
{
retornar
last
f
if (last == 0) throw bad_last();
slink* f = last->next;
// remover o
if ( f == last)
last = 0; // ultimo elemento
else
last->next = f->next;
}
return f;
Para usar a classe slist_base podemos derivar da classe slink a
classe nova. Por exemplo, vamos considerar o elemento name que
precisamos de incluir na lista:
class name : public slink
{
....................
};
void f(const char* s)
{
slist_base slb;
slb.insert(new name(s) );
// . . . . .
name* p = (name*)slb.get();// cast explícito
// . . . . .
delete p;
}
Este estilo não é bom. Nós gostaríamos de fornecer a versão
type-safe da classe slist_base:
template<class T> class Islist : private slist_base
{
public:
void insert(T* a)
{ slist_base::insert(a); }
void append(T* a) { slist_base::append(a); }
T* get()
{ return (T*) slist_base::get(); }
};
De notar que slist_base é uma classe base privada da classe Islist.
Nós não queremos permitir ao utilizador mudar a classe slist_base.
Este template pode ser usado da seguinte forma:
void f(const char* s)
{
Islist< name> ilst;
ilst.insert(new name(s) );
// . . . . .
name* p = ilst.get();
// . . . . .
delete p;
}
Neste caso o objecto pode ser incluído na Islist se este objecto for
derivado da slink. Por isso, nós não podemos definir Islist,
por exemplo, de inteiros.
Vamos considerar uma lista que não requer esta restrição.
template<class T> struct Tlink : public slink {
T info;
Tlink(const T& a) : info(a) { }
A classe Tlink<T> tem a cópia do objecto do tipo T e ligação
fornecida através da classe base slink. Agora podemos declarar
a classe Slist.
template<class T> class Slist_iter; // vamos considerar esta linha
// um pouco mais à frente
template<class T> class Slist : private slist_base {
public:
void insert(const T& a) { slist_base::insert(new Tlink<T>(a) ); }
void append(T& a) { slist_base::append(new Tlink<T>(a) ); }
T get();
friend class Slist_iter<T>; // vamos considerar esta linha
// um pouco mais à frente
};
template<class T> T Slist<T>::get()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base::get();
T i = lnk->info;
delete lnk;
return i;
}
O uso da classe Slist é tão fácil como o uso da classe Islist. A diferença
é que é possível definir o objecto da classe Slist sem necessidade de o
derivar da respectiva classe slink. Mas intrusive list, tais como
Islist, têm a vantagem na eficiência em termos de execução e
frequentemente em compacidade. Cada vez que o objecto for passado
na Slist esta lista precisa de reservar o objecto do tipo Tlink e
copiar o tipo. Como resultado duas coisas podem ser feitas.
Primeiro, Tlink é um bom reservador de memória. Segundo,
isto é boa ideia guardar objectos na “primary list” que é intrusive e
usar a lista não intrusive apenas quando é necessário o membership
de algumas listas.
void f(name* p)
{
Islist<name> lst1;
Slist<name*> lst2;
lst1.insert(p); // ligação através do objecto ‘*p’
lst2.insert(p); // o uso do objecto separado para guardar ‘p’
}
Slist é uma classe boa para pequenos objectos, tais como inteiros e
ponteiros. Para grandes objectos é melhor guardar ponteiros para
estes objectos na lista.
Iteração
A classe não fornece qualquer possibilidade para olhar para dentro
da lista. Mas ela declara a classe amiga (friend) slist_base_iter. Por
isso, nós podemos declarar o iterador:
class slist_base_iter {
slink* ce;
// o elemento corrente
slist_base* cs;// a lista corrente
public:
inline slist_base_iter(slist_base& s);
inline slink* operator()();
};
slist_base_iter::slist_base_iter(slist_base& s)
{
cs = &s;
ce = cs->last;
}
slink* slist_base_iter::operator()()
// retornar 0 para indicar o final do iteração
{
slink* ret = ce ? (ce=ce->next) : 0;
if (ce == cs->last) ce =0;
return ret;
}
A seguinte figura explica como o construtor da classe slist_base_iter e
o operador operator()() funcionam .
slist_base_iter::slist_base_iter(slist_base& s)
{
cs = &s;
ce = cs->last;
}
slink* slist_base_iter::operator()()
// retornar 0 para indicar o final do iteração
{
slink* ret = ce ? (ce=ce->next) : 0;
if (ce == cs->last) ce =0;
return ret;
}
CS
next
last
ce
ce
ce
ce
Para um dado iterador todos os iteradores para Slist e Islist podem ser
construídos. Primeiro devemos declarar os iteradores como friends
para as classes deles.
template<class T> class Islist_iter;
template<class T> class Islist : private slist_base {
public:
friend class Islist_iter<T>;
};
template<class T> class Slist_iter;
template<class T> class Slist : private slist_base {
public:
friend class Slist_iter<T>;
};
De notar que os nomes dos iteradores foram introduzidos sem definir
as suas classes template. Isto apresenta a possibilidade de usar
dependências entre templates. Agora vamos definir iteradores.
template<class T> class Islist_iter : private slist_base_iter {
public:
Islist_iter(Islist<T>& s) : slist_base_iter(s) { }
inline T* operator()()
{ return (T*) slist_base_iter::operator()(); }
};
template<class T> class Slist_iter : private slist_base_iter {
public:
Slist_iter(Slist<T>& s) : slist_base_iter(s) { }
inline T* operator()();
};
template<class T> T* Slist_iter<T>::operator()()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base_iter::operator()();
return lnk ? &lnk->info : 0;
}
De notar que mais uma vez nós usamos a derivação duma família de
classes (que são os templates) da classe base única. Neste caso a
herança expressa comunalidade e permite eliminar a replicação do
código.
Os nossos iteradores podem ser usados da seguinte forma:
void main(void)
{ try {
Slist<int> lst1;
lst1.insert(3); lst1.insert(4); lst1.insert(5);
int p = lst1.get();
cout << p << endl;
p = lst1.get();
cout << p << endl;
p = lst1.get();
cout << p << endl;
lst1.insert(30); lst1.insert(40); lst1.insert(50);
Slist_iter<int> iter1(lst1);
const int* ii;
Os resultados:
while( (ii=iter1() ) != 0 )
5
cout << (*ii) << endl;
4
}
3
catch(slist_base::bad_last)
50
{ cerr << "bad last\n"; exit(1); }
40
}
30
Sumário de templates
1. Os templates são uma das capacidades do C++ para a reutilização
de código.
2. Existem dois tipos de template: class template e function template.
É permitido usar templates para as funções globais e para as
funções locais pertencentes a qualquer classe.
3. Template permite passar um ou mais tipos dentro da classe
como parâmetros. O tipo pode ser ou qualquer tipo predefinido na
linguagem ou qualquer tipo novo definido pelo utilizador.
4. O argumento de function template deve definir o tipo com pelo
menos um argumento na função. Isto permite garantir que a própria
versão da função vai ser seleccionada com a ajuda da avaliação dos
tipos dos argumentos desta função.
5. Os parâmetros de template devem ser fornecidos em símbolos
tais como (< >). Alguns parâmetros dentro de (< >) podem ser
também símbolos < >. Para evitar ambiguidade precisamos de
inserir o espaço entre os símbolos respectivos.
SWAP<int,comp<int> >::swap(my_array);
6. Templates permitem construir os programas que foram
compostos de partes relativamente independentes. Uma parte é
orientada na construção do interface e a outra - na realização
de funções diferentes. Finalmente esta possibilidade dá novos meios
para suportar o encapsulamento e os tipos abstractos,
particularmente para separar o interface e a implementação.
7. As regras adoptadas na linguagens C/C++ para converter os
tipos dos argumentos não podem ser usadas para templates.
8. Function template pode ser redefinida nas seguintes ocasiões:
existem outras funções que têm o mesmo nome ou existem outras
functions template que têm o mesmo nome.
9. Podemos usar as expressões constantes como argumentos de
template.
10. Ao declarar os objectos de qualquer classe definidos com a
ajuda de templates podemos dizer que dois objectos são objectos
da mesma classe se eles tiveram o mesmo template ou todos os
argumentos tiverem os mesmos valores.
11. Dois tipos construídos do mesmo template são diferentes
independentemente da possibilidade das conversões automáticas
adoptadas na linguagem C++.
12. Os argumentos de template podem ser só expressões constantes
(i.e. neste caso eles não são tipos).
13. Ao definir os argumentos de template como classes bases e
derivadas nós vamos perder muitas conversões definidas na
linguagem para objectos destas classes.
14. Existe uma relação entre templates e a herança. Templates
permitem mostrar abstracções comuns entre tipos diferentes. A
herança permite apresentar interfaces comuns para classes
diferentes.
15. O uso de templates e herança dá-nos os meios para separar o
interface da implementação.
16. A declaração de template só pode ser global.
17. Cada classe ou função geradas de acordo com o template têm
copias únicas dos seus componentes estáticos.
Agora vamos considerar alguns exemplos
class slist_base
struct slink
private
public
private
template<class T> struct Tlink
template<class T> class Slist
template<class T> class Islist
class slist_base_iter
private
private
template<class T> class Islist_iter
template<class T> class Slist_iter
struct slink {
slink* next;
slink() { next=0; }
slink(slink* p) { next=p; } };
template<class T> struct Tlink : public slink {
T info;
Tlink(const T& a) : info(a) { }
};
class slist_base {
slink* last;
// last->next é a cabeça da lista
public:
void insert(slink* a);
// incluir na cabeça da lista
void append(slink* a);
// incluir no final da lista
slink* get();
// retornar e remover a cabeça
void clear()
{ last = 0; }
slist_base()
{ last = 0; }
// o primeiro construtor
slist_base(slink* a) { last = a->next = a; }
// o segundo construtor
class bad_last {};
// a classe de excepções
friend class slist_base_iter; // a classe iterador
};
template<class T> class Slist : private slist_base {
public:
void insert(const T& a) { slist_base::insert(new Tlink<T>(a) ); }
void append(T& a) { slist_base::append(new Tlink<T>(a) ); }
T get();
friend class Slist_iter<T>;
};
template<class T> class Islist : private slist_base
{
public:
void insert(T* a)
{ slist_base::insert(a); }
void append(T* a) { slist_base::append(a); }
T* get()
{ return (T*) slist_base::get(); }
friend class Islist_iter < T >;
};
void slist_base::insert(slink* a)
{ if(last)
a->next = last->next;
else
last = a;
last->next = a;
}
void slist_base::append(slink* a)
{ if(last)
{
a->next = last->next;
last = last->next = a; }
else
last = a->next = a;
}
slink* slist_base::get()
{ if (last == 0) throw bad_last();
slink* f = last->next;
if ( f == last)
last = 0;
else
last->next = f->next;
return f;
}
template<class T> T Slist<T>::get()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base::get();
T i = lnk->info;
delete lnk;
return i;
}
Forward declarations:
template<class T> class Slist_iter;
template<class T> class Islist_iter;
class slist_base_iter
{
slink* ce;
// o elemento corrente
slist_base* cs;
// a lista corrente
public:
inline slist_base_iter(slist_base& s);
inline slink* operator()();
};
template<class T> class Islist_iter : private slist_base_iter {
public:
Islist_iter(Islist<T>& s) : slist_base_iter(s) { }
inline T* operator()()
{ return (T*) slist_base_iter::operator()(); }
};
template<class T> class Slist_iter : private slist_base_iter {
public:
Slist_iter(Slist<T>& s) : slist_base_iter(s) { }
inline T* operator()();
};
slist_base_iter::slist_base_iter(slist_base& s)
{
cs = &s;
ce = cs->last;
}
slink* slist_base_iter::operator()()
// retornar 0 para indicar o final do iteração
{
slink* ret = ce ? (ce=ce->next) : 0;
if (ce == cs->last) ce =0;
return ret;
}
template<class T> T* Slist_iter<T>::operator()()
{
Tlink<T>* lnk = (Tlink<T>*) slist_base_iter::operator()();
return lnk ? &lnk->info : 0;
}
int main(int argc, char* argv[])
{
slist_base sb;
slink sl;
sb.insert(&sl);
try
{
Slist<int> lst1;
lst1.insert(3); lst1.insert(4); lst1.insert(5);
int p = lst1.get();
cout << p << endl;
p = lst1.get();
cout << p << endl;
p = lst1.get();
cout << p << endl;
lst1.insert(30); lst1.insert(40); lst1.insert(50);
Slist_iter<int> iter1(lst1);
const int* ii;
while( (ii=iter1() ) != 0 )
cout << (*ii) << endl;
}
catch(slist_base::bad_last)
{ cerr << "bad last\n"; exit(1); }
return 0;
}
size
top
c_l
counter
template <class T> class stack
{
unsigned counter;
int size;
T* c_l;
T* top;
public:
T pop();
void push(T&);
stack(unsigned);
virtual ~stack();
int get_size() { return size; }
int get_counter() { return counter; }
};
template <class T> stack<T>::stack(unsigned tamanho)
{
top = c_l = new T[size = tamanho];
counter=0;
}
template <class T> stack<T>::~stack()
{
delete [] c_l; }
template <class T> void stack<T>::push(T &new_s)
{
*top++ = new_s; counter++;
}
template <class T> T stack<T>::pop()
{
if(counter==0) {
cerr<<"stack is empty\n";
return NULL;
}
counter--;
return *--top;
}
int main(int argc, char* argv[])
{
stack<char*> pilha=10;
char *ss1 = "Aveiro",*ss2 ="Ilhavo";
double a = 10.15, b = 5.45;
pilha.push(ss1);
pilha.push(ss2);
cout << pilha.get_size() << endl;
cout << pilha.get_counter() << endl;
cout << pilha.pop() << endl;
cout << pilha.pop() << endl;
stack<double> pilha1(10);
pilha1.push(a);
pilha1.push(b);
cout << pilha1.pop() << endl;
cout << pilha1.pop() << endl;
return 0;
}