1 Introduç˜ao 2 Contêineres - FACOM

Transcrição

Universidade Federal de Mato Grosso do Sul
Facom - Faculdade de Computação
Linguagem de Programação Orientada a Objetos
Prof. Me. Liana Duenha
Standard Template Library (STL)
1
Introdução
A Standard Template Library ou STL é uma biblioteca disponibilizada pelos ambientes
de desenvolvimento C++ que contém um conjunto de classes para representar diversas
estruturas de dados e algoritmos baseado em templates. A STL define os poderosos
componentes reutilizáveis que implementam muitas estruturas de dados comuns e os
algoritmos para processar adequadamente essas estruturas. O uso de STL oferece os
seguintes benefı́cios:
• Reutilização de código. Como é baseado em templates, as classes de STL podem ser adaptadas a tipos distintos sem mudança de funcionalidade (type safe
collections).
• Portabilidade e facilidade de uso.
1.1
Categorias de classes na STL
As classes implementadas pela STL podem ser categorizadas em três grandes grupos:
• Contêineres (containers): classes utilizadas para armazenamento de dados, implementando uma coleção. Os adaptadores de contêineres fornecem funcionalidades especı́ficas sobre contêiners;
• Iteradores (iterators): classes que permitem a varredura de uma coleção seguindo
uma determinada regra;
• Algoritmos (algorithms): classes que implementam métodos para realização de
algoritmos comuns de estruturas de dados sobre as coleções.
2
Contêineres
Correspondem às coleções de elementos de um determinado tipo, na forma de gabaritos de classe. Os contêineres de sequência representam estruturas de dados lineares,
1
como vetores e listas. Os contêineres associativos representam estruturas de dados
não-lineares que, em geral, podem localizar rapidamente elementos armazenados na
estrutura. Esses dois tipos de contêineres são referidos como de contêineres de primeira
classe. Há também os adaptadores de contêineres que implementam versões limitadas
de contêineres sequenciais, como por exemplo, filas, pilhas ou filas de prioridade.
Contêineres de sequência:
• vector: os elementos são organizados na forma de um array que pode crescer
dinamicamente;
• list: os elementos são organizados na forma de uma lista duplamente encadeada, sem limite máximo de elementos;
• deque: os elementos são organizados em sequência, permitindo inserção ou
remoção no inı́cio ou no fim sem necessidade de movimentação de outros elementos. Essa estrutura tenta se aproveitar das vantagens das duas anteriores com
relação à eficiência dos métodos. Deque é abreviação de “double ended queue”ou
fila com dupla terminação. Esta classe oferece acesso indexado eficiente para ler
e modificar seus elementos, de modo muito semelhante a um vector, e também
ofecere métodos eficientes de inserção e remoção nas suas extremidades (front ou
back) de maneira eficiente, assim como uma list.
Contêineres Associativos:
• set: coleção ordenada na qual os próprios elementos são utilizados como chaves
para ordenação do contêiner. Esse contêiner permite duplicatas;
• multiset: idem ao set, porém não permite duplicatas;
• map: mapeamento de “um para um”, não permite duplicatas e possui pesquisa
baseada em chave;
• multimap: idem ao map, porém permite mapeamento de “um para muitos”e
duplicatas.
Adaptadores de Contêineres:
Existem três adaptadores de containeres definidos na STL. São eles:
• 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 porém com prioridades de inserção.
2
Arquivos de cabeçalho de contêiner Standard Libraty: <vector>,<list>,<deque>,
<stack>, <queue>, <map> (para map e multimap), <set> (para set e multiset).
2.1
Métodos comuns
Alguns dos principais métodos comuns aos templates de contêiner são:
• construtor padrão: implementa a inicialização-padrão do contêiner (é comum
que existam diferentes construtores para o mesmo contêiner);
• construtor de cópia: inicializa o contêiner como uma cópia de um contêiner
existente do mesmo tipo;
• destrutor: função destrutora para liberação da memória utilizada pelo contêiner;
• empty: retorna true se não houver nenhum elemento no contêiner; caso contrário,
retorna false
• size: retorna o número de elementos no contêiner;
• swap: permuta os elementos de um contêiner;
• operators =, <, <=, >, >=, ==, ! =: implementa a funcionalidade esperada
para cada operador;
Funções encontradas apenas em contêineres de primeira classe (de sequência ou
associativos:
• max size: retorna o número máximo de elemento de um contêiner;
• begin: retorna um iterator ou um const iterator que referencia o primeiro
elemento do contêiner;
• end: retorna um iterador ou um const iterator que referencia a próxima
posição depois do fim do contêiner;
• rbegin: retorna um reverse iterator ou const reverse iterator que referencia o último elemento do contêiner;
• rend: retorna um reverse iterator ou const reverse iterator que referencia a próxima posição depois do último elemento do contêiner invertido;
• clear: remove todos os elementos do contêiner;
• erase: remove um elemento do contêiner.
Métodos de adição e remoção em deque e vector:
3
• push back: adiciona elemento ao fim do contêiner
• push front: adiciona elemento ao inı́cio do contêiner
• back: obter uma referência para elemento no fim do contêiner
• front: obter uma referência para elemento no inı́cio do contêiner
• pop back: remove um elemento do fim do contêiner
• pop front: remove um elemento do inı́cio do contêiner
Para operações de acesso a elementos em vector, map e deque: utiliza-se o
operador [ ] como em um array comum.
Após a explicação e exemplificação dos iteradores, exibiremos exemplos sobre
adaptadores de contêineres.
3
Iteradores
Os iteradores são utilizados para apontar para os elementos de contêineres de primeira
classe. Os iteradores são implementados apropriadamente para cada tipo de contêiner.
O operador de desreferenciação (*) desreferencia um iterador a fim de que o elemento
para o qual ele aponta possa ser utilizado. A operação ++ em um iterador move-o
para o próximo elemento do contêiner. Há suporte a diversas categorias de iteradores:
• iterator: é usado para percorrer os elementos do contêiner do inı́cio para o fim
do contêiner e não pode ser usado para a gravação de dados no contêiner;
• const iterator: idem ao iterator, porém permite acesso para gravação de dados
no contêiner;
• reverse iterator: permite percurso apenas para leitura dos elementos na ordem inversa (do fim para o inı́cio);
• const reverse iterator: permite percurso para leitura/gravação dos elementos do contêiner na ordem inversa (do fim para o inı́cio);
• random access: iterador bidimensional com capacidade de acesso direto a qualquer elemento do contêiner;
4
4
Algoritmos
Correspondem de funções que implementam algoritmos de estruturas de dados (definidos
na biblioteca algorithm). As funções são divididas em 3 categorias:
• sequência: implementam operações de busca e alteração da sequência de elementos do container
• classificação: implementam classificação dos elementos do contêiner
• numéricos: implementam funções numéricas comuns sobre os elementos do container.
4.1
Alguns algoritmos de sequência:
• copy: copia os elementos entre dois iteradores para um outro contêiner;
• fill: atribui um determinado valor a todos os elementos entre dois iteradores;
• remove: remove todos os elementos de um determinado valor entre dois iteradores;
• replace: recebe dois valore old value e new value, e substitui os elementos
iguais a old value por new value entre dois os iteradores.
• reverse: inverte a ordem dos elementos entre dois iteradores;
• rotate: recebe como parâmetros três iteradores (start, end e middle). Rotaciona
os elementos entre dois iteradores start e end de tal maneira que o iterador middle
fique posicionado onde antes estava o iterador start.
• equal: Recebe como parâmetros três iteradores (start1, end1, start2). Retorna
true se os elementos entre os iteradores start1 e end1 são iguais aos da faixa de
mesmo tamanho iniciando em start2.
• find: Retorna um iterador para a primeira ocorrência do elemento com um
determinado valor passado como parâmetro entre dois iteradores.
• search: Recebe como parâmetros quatro iteradores (start1, end1, start2, end2).
Realiza a busca do subconjunto dos elementos entre os iteradores start2 e end2
dentro do conjunto dos elementos entre start1 e end1.
Os algoritmos operam sobre os contêineres utilizando somente os iteradores dos
containers. Exemplo:
5
using namespace std;
#include <vector>
#include <algorithm>
#include <iostream>
int main ()
{
int elements[] = {3, 8, 4, 7, 2, 1};
vector<int> v;
for (int i = 0; i < 6; i++)
{
v.push_back(elements[i]);
}
//rotaç~
ao
vector<int>::iterator inicio = v.begin();
vector<int>::iterator fim = v.end();
vector<int>::iterator meio = inicio + 3;
rotate(inicio, meio, fim);
cout << "Elementos rotacionados: " << endl;
for (vector<int>::const_iterator it = v.begin(); it < v.end(); it++)
{
cout << *it << " ";
}
//reversing
inicio = v.begin();
fim = v.end();
reverse(inicio, fim);
cout << endl << "Elementos invertidos: " << endl;
{
cout << *it << " ";
}
// replacing
inicio = v.begin();
fim = v.end();
replace(inicio, fim, 4, -1);
cout << endl << "Substituindo 4 por -1: " << endl;
6
{
cout << *it << " ";
}
}
4.2
Alguns algoritmos de classificação:
• sort: Classifica em ordem crescente os elementos entre dois iteradores passados
como parâmetros, sem garantia de ordem entre os elementos de mesmo valor;
• stable sort: semelhante a sort porém mantém a ordem original dos elementos
que são iguais;
Exemplo:
#include <vector>
#include <iostream>
int main(int argc, char* argv[])
{
int elemento;
vector <int> v;
//mostrando o tamanho do conteiner
cout << "O container tem tamanho " << v.size() << endl;
//inserindo no final do conteiner
for (int i = 0; i < 10; i++)
{
cout << "Digite o próximo elemento: ";
cin >> elemento;
v.push_back(elemento);
}
//percorrendo de trás para a frente
cout << "Percurso do container na ordem inversa: " << endl;
for (vector<int>::reverse_iterator rev = v.rbegin(); rev < v.rend(); rev++)
{
cout << *rev << " ";
}
7
cout << endl;
//mostrando a capacidade
cout << "A capacidade atual do vector é " << v.capacity() << endl;
//criando iteradores na direç~
ao 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 = v.begin(); fwd < v.end(); fwd++)
{
cout << *fwd << " ";
}
return 0;
}
4.3
Alguns algoritmos numéricos:
• accumulate: Recebe como parâmetros dois iteradores e um valor val. Acumula
e retorna o valor de val com todos os valores entre os dois iteradores.
• count: Conta e retorna quantos valores entre os dois iteradores são iguais a
determinado valor.
Exemplo:
#include
#include
#include
#include
<vector>
<algorithm>
<numeric>
<iostream>
int main ()
{
int elementos[] = {3, 8, 4, 7, 2, 1};
vector<int> v;
for (int i = 0; i < 6; i++)
{
v.push_back(elementos[i]);
8
}
// acumula e retorna o valor do inicio ao fim do vetor
vector<int>::iterator inicio = v.begin();
vector<int>::iterator fim = v.end();
int valor = accumulate(inicio, fim, 0);
cout << "Valor acumulado dos elementos: " << endl;
cout << valor;
// conta a quantidade de 7s no vetor
inicio = v.begin();
fim = v.end();
int contagem = count(inicio, fim, 7);
cout << endl << "Contagem de 7’s: " << endl;
cout << contagem;
return 0;
}
5
5.1
Exmplos de uso de Contêineres Sequênciais e Associativos
Classe vector
#include <vector>
#include <iostream>
#include <numeric>
template <typename T>
void printVector(vector<T> v)
{
for (typename std::vector<T>::const_iterator it = v.begin();
it < v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
9
int main ()
{
int elements[] = {3, 8, 4, 7, 2, 1};
vector<int> vInt;
// validando a insercao no conteiner vector
for (int i = 0; i < 6; i++)
{
vInt.push_back(elements[i]);
}
// uso de iterators
cout << "\nElementos do vetor: " << endl;
printVector(vInt);
// uso de reverse_iterators
cout << "\nElementos do vetor utilizando reverse_iterators: " << endl;
for (vector<int>::const_reverse_iterator it = vInt.rbegin();
it < vInt.rend(); it++)
{
cout << *it << " ";
}
// useo de reverse (invers~
ao dos elementos)
reverse(vInt.begin(),vInt.end());
cout << endl << "\nElementos do vetor após invers~
ao: " << endl;
printVector(vInt);
// uso de rotate (método de rotaç~
ao)
rotate(vInt.begin(),vInt.begin()+2,vInt.end());
cout << "\nElementos rotacionados usando inı́cio+2 elemento de
controle da rotaç~
ao: " << endl;
printVector(vInt);
// uso de replace (método de substituiç~
ao)
replace(vInt.begin(),vInt.end(), 4, -1);
cout << "\nSubstituindo 4 por -1 em todo o vetor: " << endl;
printVector (vInt);
10
// lendo 5 elementos da entrada padr~
ao e armazenando no final do vetor
int elemento;
for (int i = 0; i < 5; i++)
{
cout << "Digite o próximo elemento: ";
cin >> elemento;
vInt.push_back(elemento);
}
printVector(vInt);
//mostrando a capacidade
cout << endl << "A capacidade atual do vector é " <<
vInt.capacity() << endl;
//ordenando os elementos do vetor
sort(vInt.begin(), vInt.end());
printVector(vInt);
// acumulador
int valorAC = accumulate (vInt.begin(),vInt.end(),0);
cout << "\nSoma de todos os elementos do vetor: " << valorAC;
return 0;
}
5.2
Classe list
#include <list>
#include <iostream>
#include <numeric>
void printList(list<T> v)
{
11
for (typename std::list<T>::const_iterator it = v.begin();
it != v.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
// comparison, not case sensitive.
bool compare_nocase (std::string first, std::string second)
{
unsigned int i=0;
while ( (i<first.length()) && (i<second.length()) )
{
if (tolower(first[i])<tolower(second[i])) return true;
else if (tolower(first[i])>tolower(second[i])) return false;
++i;
}
if (first.length()<second.length()) return true;
else return false;
return false;
}
int main ()
{
int elements[] = {3, 8, 4, 7, 2, 1};
list<int> intList;
// validando a insercao no conteiner list
for (int i = 0; i < 6; i++)
{
intList.push_back(elements[i]);
}
intList.push_front(10);
// uso de iterators
cout << "\nElementos da lista: " << endl;
printList(intList);
12
ao dos elementos)
reverse(intList.begin(),intList.end());
cout << endl << "\nElementos do vetor após invers~
ao: " << endl;
printList(intList);
ao)
replace(intList.begin(),intList.end(), 4, -1);
cout << "\nSubstituindo 4 por -1 em todo o vetor: " << endl;
printList (intList);
intList.sort();
printList(intList);
// acumulador
int valorAC = accumulate (intList.begin(),intList.end(),0);
cout << "\nSoma de todos os elementos do vetor: " << valorAC;
// EXEMPLO SOBRE STRINGS
list<string> strList;
list<string>::const_iterator it;
strList.push_back ("Meu");
strList.push_back ("primeiro");
strList.push_back ("teste");
strList.push_back ("com");
strList.push_back ("STD lists.");
strList.push_front ("Este é ");
strList.push_front ("Olá pessoal! ");
std::cout << "\nElementos da lista:";
for (it=strList.begin(); it!=strList.end(); ++it)
13
std::cout << ’ ’ << *it;
std::cout << ’\n’;
return 0;
}
5.3
Classe deque
#include
#include
#include
#include
<deque>
<algorithm>
<iostream>
<numeric>
void printDeque(deque<T> v)
{
for (typename std::deque<T>::const_iterator it = v.begin();
{
cout << *it << " ";
}
cout << endl;
}
int main ()
{
int elements[] = {3.0, 8.2, 4.0, 7.1, -0.2, -23};
deque<double> doubleDeque;
// validando a insercao no conteiner deque
for (int i = 0; i < 6; i++)
{
doubleDeque.push_front(elements[i]);
}
14
doubleDeque.push_back(-0.45);
// uso de iterators
cout << "\nElementos do deque: " << endl;
printDeque(doubleDeque);
// uso de reverse_iterators
cout << "\nElementos do deque utilizando reverse_iterators: " << endl;
for (deque<double>::const_reverse_iterator it = doubleDeque.rbegin();
it < doubleDeque.rend(); it++)
{
cout << *it << " ";
}
ao dos elementos)
reverse(doubleDeque.begin(),doubleDeque.end());
cout << endl << "\nElementos do deque após invers~
ao: " << endl;
ao)
replace(doubleDeque.begin(),doubleDeque.end(), -0.45, -0.5);
cout << "\nSubstituindo -0.45 por -0.5 em todo o deque: " << endl;
printDeque (doubleDeque);
sort(doubleDeque.begin(),doubleDeque.end());
cout << "\nElementos ordenados: " << endl;
// acumulador
double valorAC = accumulate (doubleDeque.begin(),doubleDeque.end(),0);
cout << "\nSoma de todos os elementos do deque: " << valorAC;
15
return 0;
}
5.4
Classe set e multiset
#include <set>
#include <iostream>
using std::cout;
typedef std::multiset<int> Ims;
void printSet(set<T> v)
{
for (typename std::set<T>::const_iterator it = v.begin();
{
cout << *it << " ";
}
cout << endl;
}
void printMultiset(multiset<T> v)
{
for (typename std::multiset<T>::const_iterator it = v.begin();
{
cout << *it << " ";
}
cout << endl;
}
int main ()
{
16
const int SIZE = 10;
int elements[] = {3, 8, 3, 4, 4, 7, 8, 2, 2, 1};
// declaraç~
ao de dois multisets de inteiros e um set de inteiros
multiset<int> intMultiset1, intMultiset2;
set<int> intSet;
// validando a insercao nos conteineres set e multiset
for (int i = 0; i < SIZE; i++)
{
intSet.insert(elements[i]);
intMultiset1.insert(elements[i]);
}
// outra forma de inserç~
ao
intMultiset2.insert(elements,elements+SIZE);
// Impress~
ao dos resultados
cout << "\nElementos em intSet:";
printSet (intSet);
cout << "\nElementos em intMultiset1:";
printMultiset (intMultiset1);
// ratificando a diferenca de set e multiset com
// relaç~
ao às chaves duplicadas
cout << "\nHá " << intSet.count (3) << " elementos iguais a 3 no set";
cout << "\nHá " << intMultiset1.count (3)
<< " elementos iguais a 3 no multiset";
// Usando iteradores para realizar busca de um elemento
Ims::const_iterator result;
// ou Ims::const_iterator
result = intMultiset1.find(3);
if (result != intMultiset1.end() )
cout << "\nEncontrou valor 3 em Multiset";
result = intMultiset1.find(20);
17
if (result != intMultiset1.end() )
cout << "\nEncontrou valor 20 em Multiset";
// Impress~
ao
cout << "\nElementos em intSet:";
printSet (intSet);
return 0;
}
5.5
Classe map e multimap
#include <map>
#include <iostream>
using std::cout;
typedef std::multimap<int,double> MMapType;
typedef std::map<int,double> MapType;
int main ()
{
// declaraç~
ao de UM multimap de pares (int, double)
MMapType pairs;
pairs.insert(MMapType::value_type(3,4.5) );
18
cout << "\nMULTIMAP:\n";
for (MMapType::const_iterator iter = pairs.begin();
iter != pairs.end(); iter++)
cout << iter->first << "\t" << iter->second << "\n";
// MAP n~
ao aceita duplicatas
MapType map;
map.insert(MMapType::value_type(3,4.5) );
cout << "\nMAP:\n";
for (MapType::const_iterator iter = map.begin();
iter != map.end(); iter++)
cout << iter->first << "\t" << iter->second << "\n";
return 0;
}
6
Exemplos de uso de Adaptadores de Containeres
6.1
stack
Um adaptador stack utiliza, por padrão, um container deque para sua implementação.
Seus métodos são:
• push: empilha
• pop: desempilha
• empty: verifica se está vazia
19
• top: obtém valor do topo da pilha
Exemplo:
#include
#include
#include
#include
#include
<vector>
<stack>
<algorithm>
<numeric>
<iostream>
{
int elementos[] = {3, 8, 4, 7, 2, 1};
stack <int, vector<int> > pilha; //monta pilha sobre vetor
cout << "Empilhando: ";
for (int i = 0; i < 6; i++)
{
cout << elementos[i] << " ";
pilha.push(elementos[i]);
}
cout << endl;
//desempilhamento
cout << "Desempilhando: ";
while (!pilha.empty())
{
cout << pilha.top() << " ";
pilha.pop();
}
return 0;
}
6.2
queue
Um adaptador queue utiliza, por padrão, um container deque para sua implementação.
Pode também ser implementado com list. Seus métodos são:
• push: enfileira
• pop: desenfileira
20
• empty: verifica se está vazia
• front: obtém primeiro elemento da fila
• back: obtém último elemento da fila
Exemplo:
#include
#include
#include
#include
<vector>
<stack>
<queue>
<iostream>
{
int elementos[] = {3, 8, 4, 7, 2, 1};
queue <int> fila; //monta pilha sobre vetor
cout << "Enfileirando: ";
for (int i = 0; i < 6; i++)
{
fila.push(elementos[i]);
}
//desenfileiramento
cout << "Desenfileirando: ";
while (!fila.empty())
{
cout << fila.front() << " ";
fila.pop();
}
return 0;
}
6.3
priority queue
Um adaptador priority queue utiliza, por padrão, um container vector para sua implementação. Pode também ser implementado com deque. A inserção é feita de acordo
com a prioridade dos elementos inseridos; por padrão a prioridade é definida pelo valor
do elemento, porém pode-se fornecer um outro comparador que estenda o objeto de
função less<T> e redefina o método operator() (x, y) que retorna true se x < y.
21
Os métodos de priority queue são os mesmos de deque.
Exemplo:
#include
#include
#include
#include
#include
<vector>
<stack>
<queue>
<iostream>
<functional>//para permitir a extens~
ao de less
template <class T>
class my_less: public less<T>
{
public:
bool operator()(const T& x, const T& y)
{
if (strcmpi(x, y) < 0) return true;
else return false;
}
};
//redefiniç~
ao do significado da compara
{
char* elementos[] = {"abacaxi" , "uva" , "mamao"};
priority_queue<char*, vector<char*>, my_less<char*> > filap;
cout << "Enfileirando: ";
for (int i = 0; i < 3; i++)
{
filap.push(elementos[i]);
}
//desenfileiramento
cout << endl << "Desenfileirando: ";
while (!filap.empty())
{
cout << filap.top() << " ";
filap.pop();
}
return 0;
}
22

1 Introduç˜ao 2 Contêineres - FACOM

Transcrição

Documentos relacionados

Uma Introdução - Universidade de Coimbra

Livro Fabiano

mandando bem – caldeirão do huck

Operadores

Documentação explicando o funcionamento e o desenvolvimento

Apostila de DEV C++

Estruturas Auto-Referenciadas e Ficheiros

Implementação de um Ponto de Acesso Seguro para Redes 802.11

Bibliotecas para Computação Científica

Módulo 03 Identificadores, Palavras Reservadas, e - BCC Unifal-MG

Projeto - Ravel

Minimum Spanning Tree Algoritmos de Prim e Kruskal Algoritmo de

Alguns Algoritmos Clássicos

Linguagem C

RELATÓRIO ANUAL

Qual gráfico é o correto para você?

Autor: Prof. Dr. André Duarte Bueno