Templates
Traduzido de: http://www.cs.washington.edu/people/acm/tutorials
Prepared for Bart Niswonger’s CSE 326 (Data Structures) class, Su ’01
– Albert Wong (awong@cs)
Razões de uso de templates
O que são templates? Vale a pena usa-los?
• Programação Genérica Limitada (polimorfismo)
Algumas funções tem o mesmo significado semântico para alguns (ou
talvez todos) tipos de dados. A função print() deve exibir uma
representação de qualquer coisa passada a ela. Não deveria haver
necessidade de reescrever esta função para cada possível tipo de dado.
• Código menos repetitivo
Código que difere apenas no tipo de dado que manipula não deve ser
reescrito para cada tipo de dados que se pretende manipular. É mais fácil
de ler e manter se um mesmo trecho de código for usado para todos os
tipos de dados.
2
Exemplo:
uma função swap
Problema: Pode ser interessante trocar os valores de duas variáveis. O
comportamento desta função é semelhante para qualquer tipo de dado.
Funções template permitem esta troca, na maioria das vezes sem qualquer
mudança na sintaxe.
Método estúpido – escrever uma função sobrecarregada para cada tipo
Swap 4
void swap(int &a, int &b) {
int c = a;
a = b;
b = c;
}
Swap 4 T
void swap(T &a, T &b) {
T c = a;
a = b;
b = c;
}
Método template – escrever uma função template
template <typename T>
void swap(T &a, T &b) {
T c = a;
a = b;
b = c;
}
Esta função pode ser usada com
qualquer tipo de dado que suporte
atribuição e pode ser passada por
referência não constante.
3
Sintaxe de Template:
A linha <…> estabelece que tudo da
declaração ou definição que se
segue pertence ao template (no caso
a definição da função swap)
template <typename T>
void swap(T &a, T &b) {
T c = a;
a = b;
b = c;
}
As “variáveis placeholder” tem um valor para
cada declaração de template. Elas serão
substituídas por qualquer tipo que seja
especificado para o template
swap dissecado
Lista de “variáveis placeholder”. Na
maioria das vezes elas serão
especificadas pelas palavras chave
typename ou class. Estas palavras
chave são eqüivalentes
Comportamento de Template:
Como muitas coisas em C++ os
templates comportam-se como parte
da linguagem. Mas não são. Existem
duas maneira de empregar templates,
por especialização implícita ou
explícita. A especialização explícita
funciona sempre. A implícita algumas
vezes mas é muito mais “limpa”
4
Sintaxe de Template :
Usando um template
Para usar um template há necessidade de sua
especialização. Templates não são funções genéricas.
Eles fazem polimorfismo estático. Eles se
metamorfoseiam no tipo correto em tempo de préprocessamento
Uso
template <typename T>
void swap(T &a, T &b) {
T c = a;
a = b;
b = c;
}
Sintaxe
Na especialização explícita de um template escreve-se seu nome com os argumentos para as variáveis
placeholder entre parênteses angulosos. Isto sempre funciona.
Exemplo:
double d1 = 4.5, d2 = 6.7;
swap<double>(d1, d2);
Templates podem detectar os valores de seus placeholders se toda a informação sobre o que o
placeholder representa possa ser inferida do contexto(argumentos e, para funções membro, a instância
associada). Isto é chamado de especialização implícita. No caso acima o compilador detecta que T é
um double mesmo sem o <double> explícito uma vez que os argumentos são double. Esta
simplificação funciona.
Exemplo:
swap(d1, d2);
5
Como funciona
Libraries
Pré-processador
Resolve #define, #include,
comments, templates
Compilador
Traduz o código para linguagem
de máquina. Produz um “object
file.” Este código não é
executável
Linker
Código fonte
(text)
.c .h
.c .h
Pré-processador
Código C/C++
(text)
Código objeto
(bin)
Executável Nativo
(bin)
Compiler
Linker
executável
Recebe os object files e resolve
as referências para as funções e
variáveis em arquivos distintos
Compiladores possuem no mínimo 2 partes e C++ tem 3 partes. Quando se
constrói um executável a partir de um fonte C++, o pré-processador remove
tudo listado sob “Preprocessor.” O resultado é código puro C++ (sem
commentários, templates, #includes, etc). Este código é então compilado e
ligado.
6
Como funciona:
Compilador, Linker
Compilação
• Compilar significa transformar uma linguagem em outra linguagem. Em C++
transforma-se fonte C++, em código de máquina
• Cada arquivo fonte C++ usualmente é compilado em um object file que contém o
código e todas as funções definidas. Caso seja invocada uma função de uma
biblioteca ou outro arquivo, o código objeto (no object file) afirma “esta função
existe em algum lugar e quero usá-la”
• Os erros de sintaxe usualmente são mensagens do compilador (não do linker nem
do pré-processador).
Edição de ligações
• Depois da compilação, todos os arquivos objeto precisam ser ligados para criar um
executável final. Todos os “stubs” “quero esta função” nos arquivos objeto tem de ser
resolvidos em um bloco de código de máquina e o executável resultante tem de ser
formatado de maneira inteligível pelo sistema operacional.
• Se for escrito o protótipo de uma função, sem sua definição, o código compilará mas
não ligará. Os erros de link usualmente são mais difíceis de rastrear, pois linker não
pode sempre fornecer os números das linhas (o linker vê apenas os arquivos objeto e
não tem acesso ao código fonte.
7
Como funciona:
Pré-processador
O que é o pré-processador?
O pré-processador trata com as diretivas que iniciam com # (tais como #include,
#define). O pré-processamento trata de tudo que ocorre antes do compilador começar a
transformação para código de máquina.
Em relação aos templates as coisas relevantes que o pré-processador faz são:
• Substitui todos os #include pelos arquivos que eles referenciam.
• Remove todos os comentários.
• Substitui todas as macros #defines por seus valores
• Gera o código dos templates
Templates não existem!
• Templates são construções do pré-processador. Quando um template é usado
(especializado, implicitamente or explicitamente), ele se torna instanciado.
• Para criar a instância o pré-processador cria versão do template na qual cada
placeholder é substituído por sua especialização. Neste ponto a versão específica do
template passa a existir e pode ser compilada. Ela não existe de outra maneira!
• Um template apenas faz uma busca e substituição para cada tipo especializado para o
template.
8
Como funciona:
Conseqüências
Problema:
Templates são resolvidos na etapa de pré-processamento, não existindo
para o compilador até serem instanciados. Procura-se ser transparente e
eficiente. Como esperado, C++ falha e às vezes as coisas se tornam
inconsistentes.
Efeitos:
• O código do template não é compilado até ser usado (e instanciado). O
compilador não detecta erros de sintaxe até o template ser usado.
• A especialização (momento de uso do template) instancia todos os
templates relevantes que o precedem. Se um template aparece depois
da especialização, ele não é instanciado nem compilado.
Conclusão:
Para que tudo funcione, todas as definições dos templates relevantes
devem aparecer antes de, pelo menos, uma especialização . Caso
contrário, partes do template não serão instanciadas e compiladas.
9
Class Templates:
Definição de Classe
Sintaxe:
A sintaxe para as templated classes acompanha a sintaxe das templated
functions. As regras para que as templated classes possam inferir sua
especialização são mais evoluídas.
Recordação:
Estes dois templates são equivalentes?
template <typename T>
void swap(T &a, T &b) {
T c = a;
a = b;
b = c;
}
template <class C>
void swap(C &a, C &b) {
C c = a;
a = b;
b = c;
}
Resposta:
Sim, são equivalentes. Escrevendo class templates pode-se chegar a uma
situação na qual duas definições sejam escritas para a mesma coisa. Se isto
ocorrer o programa não será montado (build). O nome do placeholder não
interessa, e “typename” e “class” podem ser usados de maneira
intercambiável.
10
Class Templates:
Exemplo
Exemplo: Um array templated, dinâmico, 2 dimensional (Matrix)*
A única coisa que muda na
definição da classe é a linha:
template <typename T>
No bloco de
definição o
placeholder (T)
pode ser usado
como um tipo de
dados. Quando o
template é
especializado, ele
assume o valor da
especialização.
#ifndef MATRIX_H
#define MATRIX_H
template <typename T>
class Matrix {
public:
Matrix(int rows, int cols);
Matrix(const Matrix &other);
virtual ~Matrix();
Matrix& operator=(const Matrix &rhs);
T* operator[](int i);
int getRows() const;
int getCols() const;
protected:
void copy(const Matrix &other);
private:
Matrix();
int m_rows;
int m_cols;
T *m_linArray;
Arquivo: Matrix.h
};
#endif /* MATRIX_H */
11
Class Templates:
Continuação do exemplo
#include "Matrix.h"
template <typename T>
Matrix<T>::Matrix()
{}
template <typename T>
Matrix<T>::Matrix(int rows, int cols) {
m_rows = rows;
m_cols = cols;
m_linArray = new T[m_rows *
m_cols];
}
template <typename T>
Matrix<T>::Matrix(const Matrix &other) {
copy(other);
}
template <typename T>
Matrix<T>::~Matrix() {
delete[] m_linArray;
}
template <typename T>
T* Matrix<T>::operator[](int i) {
return m_linArray + (i*m_cols);
}
template <typename T>
void
Matrix<T>::copy(const Matrix &other) {
m_rows = other.m_rows;
m_cols = other.m_cols;
int size = m_rows * m_cols;
m_linArray = new T[size];
for( int i=0; i < size; i++ ) {
m_linArray[i] =
other.m_linArray[i];
}
}
template <typename T>
int Matrix<T>::getRows() const {
return m_rows;
}
template <typename T>
template <typename T>
int Matrix<T>::getCols() const {
Matrix<T>&
Matrix<T>::operator=(const Matrix &other) { return m_cols;
}
if( this != &other ) {
delete[] m_linArray;
copy(other);
}
return *this;
}
Arquivo: Matrix.cpp
12
Class Templates:
O nome de uma templated class, por si só,
não significa nada (Matrix não tem nenhum
significado). O significado só é adquirido
pela especialização (explícita ou implícita).
Quando for referenciada uma instância
(uma especialização específica) de uma
templated class, o nome da classe deve ser
especializado explícitamente.
Observe que a
região de
especialização
não inclui o tipo
de retorno.
Portanto, o tipo
de retorno
necessita de
especialização
explícita.
Funções Membro Dissecadas
O template foi especializado
implicitamente pelo seu contexto. Está
dentro da região de especialização do
escopo da classe. Assim não precisa
dos argumentos do template. Para
uma definição de classe a região de
especialização é o bloco da classe .
template <typename T>
Matrix<T>&
Matrix<T>::operator=(const Matrix &other) {
if( this != &other ) {
this->~Matrix();
copy(other);
}
return *this;
}
specialization region of
Matrix<T>::
Lembrar que
embora construtores
e destrutores
tenham o mesmo
nome do template
de classe eles são
funções e não
necessitam
especialização.
13
Class Templates:
Sintaxe
•As templated classes precisam ser especializadas explicitamente.
Para criar uma 2 dimensional Matrix de doubles do último exemplo,
a sintaxe seria:
Matrix<double> m(3,3);
•Esta especialização durante a declaração cria um novo tipo –
Matrix<double>. É um tipo próprio, separado de qualquer outra
especialização de Matrix (diferente de Matrix<int>, ou
Matrix<Foo>, etc.) Neste ponto a instância se comporta como
qualquer outro tipo instanciado – pelo menos para efeito de
compilação.
14
Segurança:
Consciência do perigo
Problema
Templates não existem até serem usados. Necessitam ser instanciados, Se
a instanciação não ocorrer de maneira explicita, ela ocorre no primeiro uso
de todas as definições do template. Considere-se o exemplo
Parece bem mas não ligará.
O que não funciona e por que?
O link error ocorre com m1.getRows()
• Nada de um template é instanciado até
que seja usado ou instanciado
explicitamente.
• Matrix<int>::getRows() const não é
criada até que seja usada na linha
contendo m1.getRows().
• A definição da função está em Matrix.cpp
e nunca foi usada lá.
Portanto a definição nunca é criada e
compilada para código objeto.
/* main.cpp */
#include <iostream>
using namespace std;
#include “Matrix.h”
int main(void) {
Matrix<int> m1(3,4);
cout << m1.getRows() << endl;
}
O arquivo Matrix.cpp só contém código de
template. Como nunca é usado, nunca gera
código objeto e não pode ser compilado.
15
Segurança:
3 convenções
Existem três convenções para evitar o problema de ligações
• Escreva todo o código inline nos arquivos .h.
• Faça o dito anteriormente mas escreva um arquivo de implementação com a sua
implementação e #include o arquivo de implementação em seu arquivo header.
• Escreva o template como uma classe normal (usando arquivos header e de
implementação). A seguir crie um novo Este é o arquivo a ser compilado e não a
implementação do template arquivo fonte e #include o arquivo de implementação do
template nele.
Os dois primeiros métodos sofrem do problema de, sempre que a implementação de
uma função seja mudada, todo o código que a usa deve ser recompilado (e não
apenas re-ligado). Isto é lento em montagens grandes. O processo de construção irá
instanciar o template muito maior número de vezes do que o necessário (com perda de
tempo e espaço).
O terceiro método fica livre destes problemas também evitando outras barreiras uma
vez que força a instanciação de tudo em um só ponto.
16
Segurança :
/* main.cpp */
#include <iostream>
using namespace std;
#include <Matrix.h>
int main(void) {
Matrix<int> m1(3,4);
cout << m1.getRows() << endl;
}
Exemplo:
Para conseguir ligar de maneira
apropriada o código anterior é
necessário instanciar uma versão int
do template de Matrix. O arquivo
fica com o aspecto indicado
Um exemplo
Procedimento adequado
• Escreva o template, de maneira
separada entre um header e um
arquivo de implementação
• Crie um arquivo de instanciação para
o template que inclua o arquivo de
implementação.
• Compile o arquivo de instanciação e
não o arquivo de implementação do
template
• O arquivo de instanciação gera o
código objeto para o template.
/* MatrixInst.cc */
#include “Matrix.cpp”
template Matrix<int>;
Observe que o
arquivo de
implementação
(não o header) é
incluído.
Esta linha força a instanciação do template da classe
Matrix, bem como de todas as suas funções membro,
para a especialização int. Outras especializações
17
exigem suas próprias linhas.
Detecção de falhas
(fique ligado para descobrir antes que seja tarde demais)
/*Foo.h */
#ifndef FOO_H
#define FOO_H
template <typename T>
class Foo {
Foo() {
b = “Hello Mom!”;
}
};
#endif /* FOO_H */
Este código compilará?
• Infelizmente sim. Apesar de b não ser
declarado, vai “compilar” porque
ninguém instancia o template, e o
compilador nunca vê o código do
template.
• Esta é razão pela qual não forçar
explicitamente a instanciação dos
class templates é perigoso. Não se
percebe o erro até tentar usar o
código.
Por esta razão algumas pessoas julgam melhor escrever uma primeira versão
da classe sem usar templates, e criar templates a partir dai.
18
STL
Standard Template Library, ou STL, é uma
biclioteca C++ de classes de containers,
algoritmos e iteradores
Fornece muitos algoritmos básicos e estruturas de
dados
STL é uma biblioteca genérica com componentes
are altamente parametrizados: quase todos os
componentes da STL são templates. Não se deve
usar a STL enquanto não se conheça o
funcionamento dos templates em C++
19
Exemplo de uso de STL
/* **********************************
* Stack.hpp
* ********************************/
#ifndef STACK_HPP
#define STACK_HPP
// is stack empty?
bool empty() const {
return c.empty();
}
// push element into the stack
void push (const T& elem) {
c.push_back(elem);
}
#include <deque>
#include <exception>
template <class T>
class Stack {
protected:
std::deque<T> c;
// pop element out of the stack and
// return its value
T pop () {
if (c.empty()) {
throw ReadEmptyStack();
}
T elem(c.back());
c.pop_back();
return elem;
}
//container for the elements
public:
/* exception class for pop() and top() with empty
stack /*
class ReadEmptyStack : public std::exception
{
public:
virtual const char* what() const throw() {
return "read empty stack";
}
};
{
// number of elements
typename std::deque<T>::size_type size() const
}
return c.size();
};
// return value of next element
T& top () {
if (c.empty()) {
throw ReadEmptyStack();
}
return c.back();
}
#endif /* STACK_HPP
20