Aula 12

Biblioteca padrão do C++



O que é?
Composição
Alguns componentes:
Contentores
 Iteradores
 Algoritmos
 Functores

1
2002/2003
Programação Orientada para
Objectos
C++ Padrão




Normalização de 1989 a 1997
Publicação em 1998
Nova versão em 2004?
Norma de 750 páginas, publicada pelo ISO
(Organização Internacional de Normalização)

2
“Information Technology – Programming Languages –
C++” (ISO/IEC 14882-1998)
2002/2003
Programação Orientada para
Objectos
Biblioteca padrão do C++

Parte da norma é uma biblioteca:






3
E/S
Cadeias de caracteres
Contentores
Algoritmos
Cálculo numérico
Internacionalização
2002/2003
Programação Orientada para
Objectos
STL (Standard Template Library)


Cerne da biblioteca padrão
Fornece ferramentas para manipular
colecções de dados



4
Separação clara entre dados e operações
Componentes genéricos
Novo nível de abstracção
2002/2003
Programação Orientada para
Objectos
Componentes da STL

Contentores (dados)


Iteradores (“cola” entre contentores e algoritmos)




Usados para processar os itens dos contentores
Functores


5
Percorrem contentores
Contentores vistos como sequências
Interface comum, independente do tipo de contentor
Algoritmos (operações comuns sobre sequências)


Gestão de colecções de itens de um dado tipo
Necessidades especiais
Suplementos, restrições ou configurações para algoritmos e
operações
2002/2003
Programação Orientada para
Objectos
Contentores

Sequenciais



Associativos



6
Posição de itens não depende do seu valor! (ordem
extrínseca)
Exemplos: std::vector, std::deque e std::list
Posição de itens depende do seu valor e ordem exacta
depende de relação de ordem (ordem intrínseca)
Relação de ordem por omissão: operador <
Exemplos: std::set, std::multiset, std::map e
std::multimap
2002/2003
Programação Orientada para
Objectos
vector





Implementação típica: matrizes dinâmicas
Acesso aleatório (directo e eficiente usando indexação)
Adição e remoção eficientes de itens na traseira
#include <vector>
Operações comuns






7
Construir: vector<int>()
Indexar: operator[]()
Saber se está vazio: empty()
Saber dimensão: size()
Acrescentar atrás: push_back()
Remover último item: pop_back()
2002/2003
Programação Orientada para
Objectos
deque (Double-Ended QUEue)





Implementação típica: matrizes dinâmicas
Acesso aleatório
Adição e remoção eficientes de itens na traseira e na frente
#include <deque>
Operações comuns:






8
Construir: deque<double>()
Indexar: operator[]()
Saber se está vazia: empty()
Saber comprimento: size()
Acrescentar à frente/atrás: push_front() e push_back()
Remover primeiro/último item: pop_front() e pop_back()
2002/2003
Programação Orientada para
Objectos
list (lista)





Implementação típica: cadeias duplamente ligadas
Acesso sequencial
Inserção e remoção eficiente de itens em qualquer posição
#include <list>
Algumas operações:






9
Construir: list<float>()
Saber se está vazia: empty()
Saber comprimento: size()
Saber primeiro item: front()
Saber último item: back()
…
2002/2003
Programação Orientada para
Objectos
set (conjunto) e multiset (colecção)







Ordem intrínseca (posição dos itens depende do seu valor)
Implementação típica: árvores binárias
Conjuntos: sem repetições de itens
Colecções: com repetições
Não se podem modificar os itens
#include <set> ou #include <multiset>
Operações comuns:






10
Contruir: set<int>() ou multiset<int>()
Saber se está vazio: empty()
Saber cardinalidade: size()
Inserir item: insert()
Remover item: erase()
Saber número de itens com valor: count()
2002/2003
Programação Orientada para
Objectos
map (mapa) e multimap (multimapa)






Itens são pares (chave, valor) – e.g., pair<int, string>
Ordem intrínseca (posição dos pares depende da sua chave)
Mapas: sem repetição de chaves
Multimapas: com repetição
#include <map> ou #include <multimap>
Operações comuns:







11
Construir: map<int, string>() ou multimap<int, string>()
Saber se está vazio: empty()
Saber número de pares: size()
Indexar usando chave: operator[]()
Inserir par: insert()
Remover pares: erase()
Saber número de pares com chave: count()
2002/2003
Programação Orientada para
Objectos
Contentores especiais

Implementação típica: contentores anteriores
Sem iteradores

stack (pilhas)



queue (filas)


Contentor que gere os seus elementos de acordo com a política FIFO
priority_queue (filas prioritárias)


12
Contentor que gere os seus elementos de acordo com a política LIFO
Frente da fila é item mais prioritário
Por omissão, prioridade comparada usando operador <
2002/2003
Programação Orientada para
Objectos
Que contentor usar?





13
Use vector (contentor mais simples)
Insere ou remove itens à frente e atrás? Use deque
Insere ou remove itens a meio? Use list
Procura com frequência itens pelo seu valor? Use
set ou multiset
Deseja separar itens em chave e valor? Use map ou
multimap
2002/2003
Programação Orientada para
Objectos
Iteradores




Permitem definir sequências
Permitem percorrer contentores
Referenciam itens
Operadores fundamentais:




14
Saber conteúdo ou item referenciado: *
Avançar: ++
Comparar: == e !=
Atribuir: =
2002/2003
Programação Orientada para
Objectos
Iteradores

Operações de obtenção de iteradores (apenas contentores
não-especiais):




begin()
end()
Há sempre dois tipos de iteradores:


15
begin()
end()
…
contentor::iterator
contentor::const_iterator
2002/2003
Programação Orientada para
Objectos
Tipos de iteradores

Bidireccionais



Avançam e recuam (++ e --)
Contentores: list, set, multiset, map e multimap
De acesso aleatório




São também bidireccionais
Permitem acesso aleatório aos itens da sequência
Permitem aritmética mais completa de iteradores: saltos, distâncias, ...
Contentores: vector e deque
vector<int>::const_iterator i = v.begin();
i += 2;
cout << i[3] << endl;
cout << *i << endl;
16
2002/2003
Programação Orientada para
Objectos
Iteradores especiais

De inserção




Iteradores associados a um canal


Inserem ou extraem itens de canais automaticamente
Iteradores reversos

17
Na traseira de um contentor
Na frente de um contentor
Em local dado
Avançar recua, recuar avança
2002/2003
Programação Orientada para
Objectos
Iteradores especiais (exemplo)
list<int> l;
for(int i = 0; i != 10; ++I)
l.push_back(i);
vector<int> v;
copy(l.begin(), l.end(), back_inserter(v));
set<int> c;
copy(l.begin(), l.end(), inserter(c, c.begin()));
copy(l.begin(), l.end(), ostream_iterator<int>(cout, “ “));
cout << endl;
copy(l.rbegin(), l.rend(), ostream_iterator<int>(cout, “\n“));
18
2002/2003
Programação Orientada para
Objectos
Algoritmos






#include <algorithm>
#include <numeric>
Rotinas genéricas sobre sequências
Sequências definidas por iteradores
Relação com contentores através de iteradores: não são
operações membro!
Sufixos dos nomes dos algoritmos:


19
_if – têm predicado como argumento, usando-o para identificar itens
_copy – copiam para um destino ao actuar, não alterando o original
2002/2003
Programação Orientada para
Objectos
Tipos de algoritmos







20
Não modificadores
Modificadores
De remoção
De mutação
De ordenação
Para sequências de itens intrinsecamente
ordenadas
Numéricos
2002/2003
Programação Orientada para
Objectos
sort() e reverse()
int main()
{
vector<int> v;
v.push_back(13);
v.push_back(7);
v.push_back(10);
sort(v.begin(), v.end());
copy(v.begin(), v.end(), ostream_iterator<int>(cout, “\n“));
reverse(v.begin(), v.end());
copy(v.begin(), v.end(), ostream_iterator<int>(cout, “\n“));
}
21
2002/2003
Programação Orientada para
Objectos
replace() e unique_copy()
int main()
{
list<int> l;
l.push_back(7);
l.push_back(7);
l.push_back(9);
l.push_back(10);
replace(l.begin(), l.end(), 7, 44);
copy(l.begin(), l.end(), ostream_iterator<int>(cout, “\n“));
unique_copy(l.begin(), l.end(), ostream_iterator<int>(cout, “\n“));
}
22
2002/2003
Programação Orientada para
Objectos
Classes functoras




Classes cujas instâncias se comportam como rotinas
Instâncias (functores) podem ser usadas como rotinas
Têm de ter como operação membro operator()
Definição:
class X {
public:
tipo_de_devolução operator() (parâmetros) const;
…
};
…
X fo;
…
fo(argumentos); // ou fo.operator()(argumentos);
// ou
tipo_de_devolução resultado = fo(argumentos);
23
2002/2003
Programação Orientada para
Objectos
Functores

Tipos



Vantagens face a ponteiros para rotinas


24
Predicados
Aritméticos
Podem ter atributos: “rotinas” com estado!
Maior possibilidade de utilizar código em-linha
2002/2003
Programação Orientada para
Objectos
Functores pré-definidos








25
negate<T>()
plus<T>()
minus<T>()
multiplies<T>()
divides<T>()
modulus<T>()
equal_to<T>()
not_equal_to<T>()







2002/2003
less<T>()
greater<T>()
less_equal<T>()
greater_equal<T>()
logical_not<T>()
logical_and<T>()
logical_or<T>()
Programação Orientada para
Objectos
Adaptadores de functores


Combinam functores com functores, functores
com valores e functores com rotinas
Adaptadores de functores pré-definidos:




26
bind1st()
bind2nd()
not1()
not2()
2002/2003
Programação Orientada para
Objectos
Functores: Aumentando a STL
template <typename T>
class Mostra : public unary_function<T, void> {
public:
Mostra(ostream& out);
void operator()(T const& t) const;
private:
ostream& out;
};
template <typename T>
Mostra<T>::Mostra(ostream& out)
: out(out) {}
template <typename T>
void Mostra<T>::operator()(T const& t) const {
out << t << endl;
}
27
2002/2003
Programação Orientada para
Objectos
Como usar o novo functor
int main()
{
vector<int> v;
v.push_back(2);
v.push_back(5);
v.push_back(9);
// Algoritmo for_each
for_each(v.begin(), v.end(), Mostra<int>(cout));
}
28
2002/2003
Programação Orientada para
Objectos