Templates e Questões de Design

Programas são geralmente construídos segundo um design que é

relativamente bem mapeado nos mecanismos oferecidos pela linguagem

escolhida Exemplo: orientação a objetos e classes (Java, C++)

Templates permitem a parametrização de tipos e constantes do código

A capacidade de especialização parcial e instanciação recursiva fornece

um novo poder em termos de design Programação Genérica

Traits

Policy

Metaprogramação

Expression templates

Polimorfismo e Templates

Polimorfismo é a habilidade de se associar comportamentos específicos em uma única notação genérica

Inicialmente, C++ suporta polimorfismo através dos mecanismos de herança e métodos virtuais. Nesse contexto, o ponto chave do design consiste na identificação de um conjunto de habilidades comuns entre tipos de objetos relacionados e declará-los como métodos virtuais

Polimorfismo e Templates

Após criar objetos concretos, o código cliente pode manipulá-los

através de ponteiros e referências à classe base, de forma que as

funções virtuais sejam corretamente despachadasvoid myDraw(GeoObj const& obj){

obj.draw();}double distance(GeoObj const& o1, GeoObj const& o2){

Coord c = o1.centerOfGravity() – o2.centerOfGravity(); return c.abs();}void drawElements(vector<GeoObj*> const& elem){

for (unsigned int i=0; i<elems.size(); ++i}elems[i]->draw();

}

Polimorfismo e Templates

int main()

{

Line l;

Circle c, c1, c2;

myDraw(l);

myDraw(c1);

distance(c1,c2);

distance(l,c);

vector<GeoObj*> myObjs;

myObjs.push_back(&l);

myObjs.push_back(&c);

drawElements(myObjs);

}

Em tempo de compilação, não é possível saber qual versão dos métodos virtuais será usada

Em tempo de execução, a função correta é chamada através do mecanismo de despacho de funções virtuais. Por isso, esse é um polimorfismo dinâmico

Podem ser construídas coleções heterogêneas de objetos, uma vez que são tratados uniformemente como ponteiros ou referências à classe base

Polimorfismo e Templates

Templates também podem ser usadas para implementar polimorfismo Comportamento comum é conseguido implicitamente, garantindo-se

que diferentes “objetos” suportem operações segundo a mesma sintaxe (mesmo nome, mesmo parâmetros). Classes concretas são definidas independentemente

Polimorfismo e Templates

void myDraw(GeoObj const& obj){ obj.draw();}

double distance(GeoObj const& o1, GeoObj const& o2){ Coord c = o1.centerOfGravity() – o2.centerOfGravity(); return c.abs();}

void drawElements(vector<GeoObj*> const& elem){for (unsigned int i=0; i<elems.size();++i) elems[i]->draw();}

template<typename GeoObj>void myDraw(GeoObj const& obj){ obj.draw();}template<typename GeoObj1, typename GeoObj2>double distance(GeoObj1 const& o1, GeoObj2 const& o2){ Coord c = o1.centerOfGravity() – o2.centerOfGravity(); return c.abs();}

template<typename GeoObj>void drawElements(vector<GeoObj*> const& elem){ for (unsigned int i=0; i<elems.size(); ++i) elems[i]->draw();}

Polimorfismo e Templates

Polimorfismo é conseguido quando as classes concretas instanciam as funções parametrizadas

int main(){

Line l;Circle c, c1, c2;myDraw(l);myDraw(c1);

distance(c1,c2); distance(l,c);

vector<Line> myObjs; myObjs.push_back(l); drawElements(myObjs);}

O tipo para qual será instanciada a função polimórfica deve ser conhecido em tempo de compilação: polimorfismo estático

Não podem ser construídas coleções heterogêneas de objetos

Vector<GeoObj*> : erro! Não existe a classe abstrata GeoObj

Polimorfismo Dinâmico X Estático

Polimorfismo implementado via herança Bounded: as interfaces dos tipos participando do comportamento

polimórfico são pre-determinadas pelo projecto das classes bases Dynamic: o binding das interfaces é feito em tempo de execução Coleções heterogêneas são tratadas elegantemente Código executável é potencialmente menor Código é inteiramente compilado

Polimorfismo implementando via templates Unbounded: as interfaces dos tipos participando do comportamento

polimórfico não são pre-determinadas Static: o binding das interfaces é feito em tempo de compilação Código gerado é potenciamente mais rápido Tipos concretos precisam implementar somente a parte usada pelo

template

Programação Genérica

Polimorfismo estático leva ao conceito de programação genérica: “Generic programming is a subdiscipline of computer science that deals

with finding abstract representations of efficient algorithms, data structures, and other software concepts, and their systematic organization... Generic programming focuses on representing families of concepts”

Contribuição mais relevante e mais representativa de programação genérica é a STL C++

STL - Standard Template Library

STL - Descrição Geral parte do padrão C++ (aprovado em 1997/1998)

extende o núcleo de C++ fornecendo um conjuto de componentes

gerais

A STL fornece componentes centrais para tratar: tipos String

diferentes estruturas de dados

classes numéricas

classes para entrada/saída

Algoritmos

Características de C++ que STL usa

Templates Parâmetros que não são tipos Parâmetro default Identificador typename Membros parametrizados

Tratamento de Exceções Namespaces Novos operadores de conversão Definição de main()

int main() { }

int main(int argc, char* argv[]) { }

Namespace std

Todos os identificadores da C++ Standard Library são definidos no namespace std

Portanto existem 3 opções para usar um identificador da STL:1. std::cout << 3.4 << std::endl;2. using std::cout;

using std::endl; cout << 3.4 << endl; 3. using namespace std;

cout << 3.4 << endl;

Header files: sem extensão#include <iostream>#include <string>#include <cstdlib>#include <cstring>

Tratamento de Erros

É heterogêneo: algumas partes checam por erros detalhadamente, gerando

várias exceções, outras jogam exceções somente em erros de execução

Todas as exceções jogadas pela linguagem ou pela biblioteca são derivadas

da classe base exception.

Estão divididas em 3 grupos:

1. Exceções para suporte da linguagem

2. Exceções para a STL

3. Exceções para erros fora do escopo do programa

Estão definidas nos headers <exception>, <stdexception>, <new>, <ios> e

<stdexcept>

Exceções

exception

bad_cast

bad_alloc

bad_typeid

logic_error

ios_base::failure

runtime_error

bad_exception

length_error

out_of_range

invalid_argument

domain_error

range_error

overflow_error

underflow_error

The Standard Template Library - STL

STL fornece soluções para tratar de coleções de dados com algoritmos

eficientes e modernos

Programadores podem se beneficiar de inovações na área de

estruturas de dados e algoritmos sem saber exatamente como eles

funcionam

É um conjunto de classes que atendem a diferentes necessidades,

juntamente com diferentes algoritmos que operam sobre elas

Todos os componentes da STL são parametrizados

O preço que se paga pela sua flexibilidade é que não é auto-explicativa

Componentes da STL

STL baseia-se na cooperação de componentes bem estruturados:

containers, iteradores e algoritmos

Containers são usados para gerenciar coleções de objetos de um certo

tipo. Cada tipo de container tem suas próprias vantagens e

desvantagens e portanto diferentes tipos de containers atendem a

diferentes necessidades em termos de coleções

Iteradores são usados para percorrer os elementos das coleções de

objetos. Essas coleções podem ser containers ou parte deles.

Oferecem uma interface pequena porém comum a todos os tipos de

coleções (similar a ponteiros com + e *). Cada coleção provê seu

próprio iterador que sabe como percorrê-la

Algoritmos são usados para processar os elementos da coleção

Componentes da STL

Conceito fundamental da STL: separar dados de operações

Algoritmo iterador container

container

container iterador

iterador

Containers Podem ser de diferentes tipos:

De maneira geral existem 2 tipos de containers: containers sequenciais: são coleções de elementos nas quais cada

elemento possui uma certa posição: vector, deque e list containers associativos: são coleções nas quais a posição de cada elemento

depende do seu valor segundo algum critério de ordenação: set, multiset, map e multimap

string : similar a vector com elementos do tipo caracter array ordinários

vector:

deque:

set:

map:

list:

Vectors

Coleção que gerencia elementos em um array dinâmico Permite acesso aleatório Inserção de elementos no final do array é rápido, mas no meio ou começo é

lento devido ao processo de realocação dos elementos

#include <iostream>#include <vector>using namespace std;int main(){

vector<int> col;for (int i=1; i<6; i++) {

col.push_back(i);}for (int i=0; i<col.size(); i++) {

cout << col[i] << ´ ´;}cout << endl;

}

Deques

Deque (“double ended queue”) : array dinâmico que pode crescer nas duas direções

Inserir elementos no começo e no fim é rápido Inserir elementos no meio é lento

#include <iostream>#include <deque>using namespace std;int main(){

deque<float> col;for (int i=1; i<6; i++) {

col.push_front(i*1.1);}for (int i=0; i<col.size(); i++) {

cout << col[i] << ´ ´;}cout << endl;

}

Lists

Lista duplamente linkada de elementos. Cada elemento conhece seu sucessor e seu antecessor.

Não permite acesso aleatório Inserção é rápida em qualquer posição

#include <iostream>

#include <list>using namespace std;int main(){

list<char> col;for (char c=´a´; c<=´z´; c+=) {

col.push_back(c);}while (!col.empty()) {

cout << col.front() << ´ ´;coll.pop_front();

}cout << endl;

}

Containers associativos

Mantém seus elementos ordenados automaticamente segundo algum

critério. Esse critério é especificado na forma de uma função de

comparação de valores

Por default os containers comparam elementos ou chaves com o

operador < , no entanto é possível informar sua própria função de

comparação

Tipicamente containers são implementados como árvores binárias.

Cada elemento tem um pai e dois filhos, os filhos da esquerda são

menores que o pai e os da direita maiores que o pai

Serão exemplificados após a discussão sobre iteradores

Containeres

Escolha containeres com cuidado Você necessita inserir elementos em posições arbitrárias? Você necessita manter elementos ordenados dentro do container? Você necessita que sejam compatíveis com C?

Containeres contém cópias dos objetos inseridos Otimize construtores de cópias e operadores de associação de seus

próprios tipos Utilize containeres de ponteiros (lembre-se de destruí-los!)

Use “c.empty()” ao invés de “c.size()==0” Entenda como um container aumenta seu tamanho dinamicamente

vector<int> vi; // são reservadas 10 posições

for (int i=0; i<10; ++i) vi.push_back(i);

vi.push_back(11); // são realocadas mais 10 posições!

vi.reserve(11); // já são criadas 11 posições

Iteradores

É um objeto que pode “caminhar” (iterar) sobre elementos

Esses elementos podem ser todos, ou somente alguns elementos de um

container STL

Um iterador representa uma certa posição dentro do container

As seguintes operações definem o comportamento de um iterador: Operador *: retorna o elemento da posição atual do iterador

Operador ++: avança o iterador para o próximo elemento

Operador == e != : verifica se dois iteradores apontam para a mesma

posição

Operador = : associa a um iterador (a posição do elemento a que ele se

refere)

Todos os containers STL fornecem as funções básicas que permitem o

uso de iteradores sobre seu componentes

Iteradores

cont.begin(): retorna um iterador que representa o começo dos elementos no container. É a posição do primeiro elemento

cont.end(): retorna um iterador que representa o final dos elementos de um container. É a posição atrás do último elemento (past-the-end-iterator)

begin() end()

Iteradores

#include <iostream>#include <list>using namespace std;int main(){

list<char> col;for (char c=´a´; c<=´z´; c+=) {

col.push_back(c);}list<char>::const_iterator pos; // list<char>::iterator posfor (pos = col.begin(); pos != col.end(); ++pos)

cout << *pos << ´ ´;cout << endl;

}

Categorias de Iteradores

Bidirecionais: podem andar para a frente (++) e para trás (--). Podem

ser encontrados em list, set, multiset, map e multimap

De Acesso Aleatório: tem todas as propriedades dos bidirecionais

mais o acesso aleatório. Além disso, pode-se fazer aritmética sobre

eles: +, -, < e >. Aparecem em vector, queue e string

Definem as habilidades do iterador (não são classes!)

Cuidado ao confiar em propriedades especiais dos iteradores ao

escrever código genérico

for (pos = col.begin(); pos != end(); ++pos) { ... } // ok!

for (pos = col.begin(); pos < end(); ++pos) { ... } // nem sempre

Set

Uma coleção onde cada elemento é ordenado de acordo com seu valor Cada elemento só pode ocorrer uma vez na coleção

#include <set>typedef sdt::set<int> IntSet;

IntSet col;col.insert(3); col.insert(1); col.insert(4);col.insert(1); col.insert(2); col.insert(5);

IntSet::const_iterator pos;for (pos = col.begin(); pos != end(); ++pos)

std::cout << *pos << ´ ´;

Set/Multiset

Função de comparação

typedef <set<int>, less<int> > SetAsc; typedef set<int, greater<int> > SetDesc;

Multisets permitem a duplicação de valores

4

3

2

5

1

2

4

3

1

5

Map

Maps podem servir como arrays associativos

typedef map<string,float> StringFloatMap;StringFloatMap col;

col[“PI”] = 3.141516;col[“NULL”] = 0.0;col[“VAT”] = 0.15;

StringFloatMap ::const_iterator pos;for (pos = col.begin(); pos != end(); ++pos) {

cout << “chave: “ << pos->first;cout << “valor: “ << pos->second << endl;

}cout << col[“NULL”];

Map/Multimap

Os elementos de um map são pares to tipo (chave,valor)#include <map>typedef sdt::map<int,string> IntStringMap;

IntStringMap col;col.insert(1,”standard”); // elementos são do tipo pair<int,string>

col.insert(3,”library”); col.insert(2,”template”);

IntStringMap ::const_iterator pos;for (pos = col.begin(); pos != end(); ++pos) // prefix!

std::cout << pos->second << ´ ´; // (*pos).second

// similarmente pos->first retornaria os int

Multimaps permitem entradas repetidas de uma mesma chave

Strings

A classe string da STL permite que cadeias de caracteres possam ser tratadas como tipos normais, que podem ser copiados, atribuídos ou comparados sem preocupações quanto a memória

#include <string>string filename = “teste.txt”;string::size_type idx = filename.find(‘.’);if (idx == string::npos){

filename = filename + “.txt”;idx = filename.size();

}string basename = filenane.substr(0,idx);string extname = filename.substr(idx+1);char* c = basename.c_str();

Algoritmos

A STL fornece vários algoritmos padrão para o processamento dos elementos de coleções

Serviços fundamentais do tipo: busca, ordenação, cópia, reordenação, modificação e processamento numérico

Não são membros das classes de containers São funções globais que que operam sobre iteradores Ao invés de cada algoritmo ser implemetados para cada tipo de

container, são implementados apenas uma vez Podem ser usados sobre containers definidos pelo usuário Esse conceito reduz a quantidade de código e aumenta o poder e a

flexibilidade da biblioteca

Exemploint main() {

vector<int> col; vector<int>::iterator pos;col.push_back(2); col.push_back(5); col.push_back(4);

col.push_back(1); col.push_back(6); col.push_back(3);

pos = min_element(col.begin(), col.end());

cout << “menor valor: “ << *pos << endl;

pos = max_element(col.begin(), col.end()); cout << “maior valor: “ << *pos << endl;

sort((col.begin(), col.end());

pos = find (col.begin(), col.end(),3);

reverse(pos, col.end());

for (pos = col.begin(); pos != col.end(); ++pos) cout << *pos << ‘ ‘;

}

Intervalos (ranges)

Todos os algoritmos processam um ou mais intervalos de elementos

O intervalo não necessariamente engloba todos os elementos do

container

O intervalo é definido através de seu início e fim : [início,fim)

Cabe ao programador garantir que o intervalo seja válido: que o fim seja

alcançável a partir do início sob pena de loops infinitos ou acessos

proibidos a áreas de memória

reverse(col.begin(), col.end());

posIni = find (col.begin(), col.end(),3);

posFim = find (col.begin(), col.end(),6);

for (pos = posIni; pos != posFim; ++pos)

cout << *pos << ‘ ‘;

Intervalos Múltiplos

Alguns algoritmos processam mais que um intervalo Usualmente, define-se o início e o fim do primeiro intervalo e apenas o

início do segundo intervalo

if (equal(col1.begin(), col1.end(), col2.begin()) {...}

list<int> col1; vector<int> col2;for (int i=1; i<10; i+)

col1.push_back(i);

copy(col1.begin(), col1.end(), col2.begin(); // Erro! // col2 está vazia

Algoritmos

Observar o que o algoritmo faz e o que se espera dos containers que manipula

list<int> col1; vector<int> col2;for (int i=1; i<10; i+)

col1.push_back(i);

col2.resize(col1.size());

copy(col1.begin(), col1.end(), col2.begin()); // ok!

deque<int> col3(col1.size());

copy(col1.begin(), col1.end(), col3.begin()); // ok!

Algoritmos

Observar que algoritmos não conhecem a priori os containers sobre os quais serão utilizados

Algoritmos que modificam o intervalo do container podem ter um comportamento diferente do esperado

col.push_back(2); col.push_back(1); col.push_back(2); col.push_back(1);

list<int>::iterator newEnd = remove(col.begin(); col.end(),1);

2 1 2 1

B F

2 2 1 1

B FnewEnd

col.erase(1);

STL

Ler os Capítulos 16 e 17 do C++ 3rd Edition