Linguagem de
Programação II
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
STL
Standard Template Library
Introdução
É uma biblioteca disponibilizada pelos ambientes de
desenvolvimento C++ contendo um conjunto de classes de
coleções (estruturas de dados) e de algoritmos de
coleções, organizados na forma de gabaritos (templates).
O uso de STL pretende oferecer os seguintes benefícios:
reutilização de código – como é baseado em gabaritos (templates), as
classes de STL podem ser adaptadas a tipos distintos sem mudança de
funcionalidade (type safe collections).
portabilidade e facilidade de uso
Introdução
Foi desenvolvida nos laboratorios da HP e liberada em
Agosto de 1994
Fornece ao programador estruturas de dados comuns e úteis
como vetores, listas, deques, sets e maps e um conjunto de
algoritmos para manipula-los como pesquisa e inserção
Não seria implementada sem o conceito de templates
Templates permitem que a STL opere com os tipos de dados prédefinidos de C++ e tambem com os tipos definidos pelo programados
Objetiva a reutilização de código
O termo genérico significa criar código que seja independente do tipo de
dado
Componentes básicos
As classes implementadas pela STL podem ser
categorizadas em três grandes grupos:
Containers – classes utilizadas para armazenamento de dados,
implementando uma coleção. Exemplos: vetores, listas, filas projetados
para armazenar tipos predefinidos (int, float, etc), objetos e tipos criados
pelo programador
Iteradores (iterators) – classes que permitem a varredura pelos
elemento de uma coleção seguindo uma determinada regra. Atuam da
mesma forma que um ponteiro perconrrendo arrays. São a ligação
entre algoritmos e containers fornecendo aos algoritmos as
operações para acesso aos containers.
Normlamente são utilizados para se morevem sequencialmente de
um elemento a outro em um container
Algoritmos – classes que implementam métodos para realização de
algoritmos comuns de estruturas de dados sobre as coleções como
pesquisa, inserção e classificação
Containers
Correspondem às coleções de elementos de um
determinado tipo, na forma de gabaritos (templates) de
classe. Os conteiners definidos pela STL são:
vector: elementos organizados na forma de um array que pode crescer
dinamicamente.
Acesso aleatório rápido por meio de um índice numérico.
Lento para inserção e retirada no meio.
Rápido para inserção e retirada no fim
List: elementos organizados na forma de uma lista duplamente
encadeada.
Acesso aleatório lento
Rápido para inserção e retirada em qualquer posição
Acesso rápido aos extremos
Containers
deque: elementos organizados em sequência, permitindo inserção ou
remoção no inícis valores do tipo ou no fim sem necessidade de
movimentação de outros elementos.
Acesso rápido por meio de um índice numérico
Lento para inserção e retirada no meio
Rápido para inserção e retirada nos extremos
map: cada elemento é um par <chave, elemento> sendo que a chave é
usada para ordenação da coleção.
Não permite chaves duplicadas
set: coleção ordenada na qual os próprios elementos são utilizados
como chaves para ordenação da coleção.
Armazena apenas valores do tipo chave, não permitindo chaves
duplicadas
Containers
multimap: Associa uma chave a um valor permitindo chaves duplicadas
multiset: Armazena apenas um valor do tipo chave, permitindo chaves
duplicadas
Métodos comuns a containers
empty: determina se a coleção está vazia
size: determina o número de elementos na coleção
begin: retorna um iterador para a frente, apontando para o
início da coleção
end: retorna um iterador para a frente, apontando para o
próximo elemento após o fim da coleção
rbegin: retorna um iterador para trás, apontando para o fim
da coleção
rend: retorna um iterador para trás, apontando para o
elemento anterior ao início da coleção.
clear: apaga todos os elementos de uma coleção.
erase: apaga um elemento da coleção.
Métodos de adição e remoção em deque
e vector
push_back: adiciona elemento ao fim da coleção
push_front: adiciona elemento ao início da coleção
back: obter uma referência para elemento no fim da coleção
front: obter uma referência para elemento no início da
coleção
pop_back: remove um elemento do fim da coleção
push_back: remove um elemento do início da coleção
Operações de acesso a elementos em vector, map e
deque: utiliza-se o operador [ ] como em um array comum.
Iteradores
Correspondem a objetos que podem ser utilizados para
acessar os elementos de um container. Três categorias de
iteradores são suportadas:
iterator: permite percurso dos elementos do início para o fim da
coleção
reverse_iterator: permite percurso dos elementos na ordem inversa
(do fim para o início) da coleção.
random_access: acesso aleatório. Definido para vector.
Os iteradores podem ser incrementados com o operador ++
para apontarem para o próximo elemento e de-referenciados
pelo operador * obtendo o valor do elemento que apontam
Algoritmos
Correspondem a gabaritos de funções que implementam
algoritmos de estruturas de dados (definidos na biblioteca
algorithm). As funções são divididas em 3 categorias:
sequência: implementam operações de busca e alteração da
sequência de elementos do container
classificação: implementam classificação dos elementos do container
numéricos: implementam funções numéricas comuns sobre os
elementos do container.
Algoritmos de sequencia
copy(start, end, dest): copia os elementos entre os
iteradores start e end para dest.
fill(start, end, val): atribui val a todos os elementos entre os
iteradores start e end
remove(start, end, val): remove todos os elementos de
valor val entre os iteradores start e end.
replace(start, end, old_value, new_value): substitui os
elementos iguais a old_value por new_value entre os
iteradores start e end.
reverse(start, end): inverte a ordem dos elementos entre os
iteradores start e end
rotate(start, middle, end): rotaciona os elementos entre os
iteradores start e end de tal maneira que o iterador middle
fique posicionado onde antes estava o iterador start.
Algoritmos de sequencia
equal (start1, end1, start2): retorna true se os elementos
entre os iteradores start1 e end1 são iguais aos da faixa de
mesmo tamanho iniciado em start2.
find(start, end, val): retorna um iterador para a primeira
ocorrência do elemento val entre os iteradores start e end.
search(start1, end1, start2, end2): procura o subconjunto
dos elementos entre os iteradores start2 e end2 dentro do
conjunto dos elementos entre start1 e end1.
Os algoritmos operam sobre os containers utilizando somente
os iteradores dos containers.
Algoritmo
Iterador
Containers
#include <iostream>
# include <vector>
using namespace std;
int main() {
unsigned int k;
vector<int> pares; // poderia ser usado vector <int> pares(10) para definir
// tamanho, mas não é obrigatório
pares.push_back(10);
pares.push_back(2);
pares.push_back(8);
pares[3] = 7;
for (k = 0; k < pares.size(); k++)
cout << pares[k];
return 0;
}
Exemplo de como criar uma estrutura de dados do tipo vector
#include <iostream>
# include <list>
using namespace std;
int main() {
list<float> notas; // lista do tipo float
list<float>::iterator iterfloat; // iterador para a lista
notas.push_back(6.5);
notas.push_back(7.5);
notas.push_back(8.5);
notas.push_back(9.5);
Iterator deve ser do
mesmo tipo da lista
for (iterfloat = notas.begin(); iterfloat != notas.end(); iterfloat++ )
cout << *iterfloat << “ “;
return 0;
}
Exemplo de uma lista
Algoritmos de classificação
Alguns algoritmos de classificação:
sort(start, end): classifica em ordem crescente os elementos
entre os iteradores start e end, utilizando o algoritmo introsort,
sem garantia de ordem entre os elementos de mesmo valor
stable_sort(start, end): semelhante a sort porém mantém a
ordem original dos elementos que são iguais.
sort_heap(start, end): transforma o heap entre os iteradores
start e end em um heap classificado (para criar um heap a partir
de um container sequencial pode-se utilizar make_heap(start,
end).
#include <iostream>
# include <vector>
using namespace std;
int main() {
unsigned int k;
vector<int> pares; // poderia ser usado vector <int> pares(10) para definir
// tamanho, mas não é obrigatório
pares.push_back(10);
pares.push_back(2);
pares.push_back(8);
pares[3] = 7;
Iterator que aponta
para o inicio do
container
Iterator que aponta
para o fim do
container
sort(pares.begin(), pares.end());
for (k = 0; k < pares.size(); k++)
cout << pares[k];
return 0;
}
Exemplo de como classificar um vector usando o algoritmo sort()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
int elemento;
vector <int> teste;
//mostrando o tamanho do container
cout << "O container tem tamanho " <<
teste.size() << endl;
//inserindo no final do container
for (int i = 0; i < 10; i++) {
cout << "Digite o próximo elemento: ";
cin >> elemento;
teste.push_back(elemento);
}
//mostrando a capacidade
cout << "A capacidade atual do vector é "
<< teste.capacity() << endl;
//criando iteradores na direção original
vector<int>::iterator inicio = teste.begin();
vector<int>::iterator fim = teste.end();
//ordenando os elementos
sort(inicio, fim);
cout << "Elementos ordenados: " << endl;
for (vector<int>::const_iterator fwd =
teste.begin(); fwd < teste.end(); fwd++)
cout << *fwd << " ";
return 0;
}
//percorrendo de trás para a frente
Exemplo mais complexo com vector
for (vector<int>::reverse_iterator rev =
teste.rbegin(); rev < teste.rend(); rev++)
cout << *rev << " ";
Algoritmos numéricos
accumulate(start, end, val): acumula e retorna o valor dos
tipo val com todos os valores entre os iteradores start e end.
count(start, end, val): conta quantos valores entre os
iteradores start e end são iguais a val.
#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>
void accumulate_count_test(){
int elementos[] = {3, 8, 4, 7, 2, 1};
vector<int> teste;
for (int i = 0; i < 6; i++){
teste.push_back(elementos[i]);
}
using namespace std;
int main(int argc, char* argv[]) {
accumulate_count_test();
//accumulate the elements
vector<int>::iterator inicio = teste.begin();
vector<int>::iterator fim = teste.end();
return 0;
}
int valor = accumulate(inicio, fim, 0);
cout << "Valor acumulado dos elementos”;
cout << valor;
//counts the number of 7's
inicio = teste.begin();
fim = teste.end();
int contagem = count(inicio, fim, 7);
cout << endl << "Contagem de 7's: ";
cout << contagem;
Exemplo com acumulador e count
}
Adaptadores de containers
A idéia dos adaptadores de containers é prover
funcionalidade específica sem no entanto implementar a
estrutura onde os dados são armazenados. A estrutura é
fornecida por um dos containers definidos na STL e o seu
comportamento é adaptado por um adaptador de container.
São definidos 3 adaptadores na STL:
stack: fornece funcionalidade de pilha (estrutura LIFO, last in first out).
queue: fornece funcionalidade de fila FIFO (first in first out).
priority_queue: fornece a funcionalidade de uma fila FIFO porém com
prioridades de inserção.
Stack
Um adaptador stack utiliza, por padrão, um container deque
para sua implementação.
Métodos:
push: empilha
pop: desempilha
empty: verifica se está vazia
top: obtém valor do topo da pilha
#include <vector>
#include <algorithm>
#include <stack>
#include <iostream>
void stack_test(){
int elementos[] = {3, 8, 4, 7, 2, 1};
using namespace std;
//monta pilha sobre vetor
stack <int, vector<int> > pilha;
int main(int argc, char* argv[]) {
cout << "Empilhando: ";
for (int i = 0; i < 6; i++){
cout << elementos[i] << " ";
pilha.push(elementos[i]);
}
stack_test();
return 0;
}
//desempilhamento
cout << "Desempilhando: ";
while (!pilha.empty()){
cout << pilha.top() << " ";
pilha.pop();
}
Exemplo de stack
}
Queue
Um adaptador queue utiliza, por padrão, um container deque
para sua implementação. Pode também ser implementado
com list.
Métodos:
push: enfileira
pop: desenfileira
empty: verifica se está vazia
Front: obtém primeiro elemento da fila
back: obtém último elemento da fila
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <iostream>
void queue_test() {
int elementos[] = {3, 8, 4, 7, 2, 1};
//monta pilha sobre vetor
queue <int> fila;
using namespace std;
cout << "Enfileirando: ";
for (int i = 0; i < 6; i++) {
int main(int argc, char* argv[]) {
queue_test();
cout << elementos[i] << " ";
fila.push(elementos[i]);
return 0;
}
}
//desenfileiramento
cout << "Desenfileirando: ";
while (!fila.empty()) {
cout << fila.front() << " ";
fila.pop();
}
Exemplo com queue
}