Container Deque Cpp

Prévia do material em texto

Container <deque> – C++
Aleffer Rocha, UTFPR-PG.
aleffer@alunos.utfpr.edu.br
Novembro de 2014, Ponta Grossa – PR.
Roteiro de apresentação
 Introdução ao deque;
 Criando um deque;
 Inserção no início do deque;
 Inserção no fim do deque;
 Remoção no início do deque;
 Remoção no fim do deque;
 Métodos Construtores <deque>;
 Métodos Acessores <deque>;
 Métodos Modificadores <deque>;
 Exercício;
 Referências.
Introdução ao deque
 A classe-template deque representa uma estrutura de dados do tipo
double-ended queue (fila com duas extremidades);
 A exemplo do vetor, o deque também suporta o operador “[ ]”;
 As operações de inserção e eliminação podem ser feitas em ambos os
lados extremos e os seus elementos não são armazenados em posições
contíguas da memória.
Criando um deque
 Existem 4 formas de se criar um deque, ou seja, são 4 construtores:
#include <deque>
#include <iostream>
using namespace std;
int main (void){
deque <int> p_deque; /* Deque vazio. */
deque <int> s_deque(8); /* Deque com N elementos (neste caso, 8). */
deque <int> t_deque(8, -1); /* Deque com N elementos inicializado com valor X (neste
caso 8 elementos estes inicializados com -1) */
deque <int> q_deque(ini, fim); /* Cria o deque vazio e copia os valores indexados do
iterator passado em início ao iterator passado como fim. */
return 0;
}
Inserção no início do deque
 Vamos utilizar o deque “p_deque” criado no slide anterior para fazermos a inserção no
início do deque:
#include <deque>
#include <iostream>
using namespace std;
int main (void){
...
p_deque.push_front(7); /* Inserindo o valor 7 inicio do deque. */
p_deque.push_front(9); /* Inserindo o valor 9 no inicio do deque. */
p_deque.push_front(2); /* Inserindo o valor 2 do deque. */
return 0;
}
Inserção no fim do deque
 Vamos utilizar o deque “p_deque” para fazermos a inserção no fim do deque:
#include <deque>
#include <iostream>
using namespace std;
int main (void){
...
p_deque.push_back(3); /* Inserindo o valor 3 no fim do deque. */
p_deque.push_back(5); /* Inserindo o valor 5 no fim do deque. */
p_deque.push_back(1); /* Inserindo o valor 1 no fim do deque. */
return 0;
}
Remoção no início do deque
 Vamos utilizar o deque “p_deque” para fazermos a remoção no início do deque:
#include <deque>
#include <iostream>
using namespace std;
int main (void){
...
p_deque.pop_front(); /* Removendo o primeiro elemento do deque. */
return 0;
}
Remoção no fim do deque
 Vamos utilizar o deque “p_deque” para fazermos a remoção no fim do deque:
#include <deque>
#include <iostream>
using namespace std;
int main (void){
...
p_deque.pop_back(); /* Removendo o último elemento do deque. */
return 0;
}
Métodos Construtores <deque>
MÉTODO DESCRIÇÃO TEMPO DE EXECUÇÃO
deque <T> d; Cria um deque vazio. O(1)
deque <T> d(n); Cria um deque com “n” elementos. O(n)
deque <T> d(n, value); Cria um deque com “n” elementos,
inicializados com um valor dado no
parâmetro “value”.
O(n)
deque <T> d(begin, end); Cria um deque e copia os valores dados
através dos iterators passados pelos
parâmetros “begin” e “end”;
O(n)
Métodos Acessores <deque>
MÉTODO DESCRIÇÃO TEMPO DE EXECUÇÃO
d[i] Retorna ou seta o i-ésimo elemento com
verificação dos limitantes.
O(1)
d.at(i) Retorna o elemento i do deque verificando se i
está dentro dos limites do deque.
O(1)
d.size() Retorna um inteiro correspondente ao tamanho do
deque.
O(1)
d.empty() Retorna 1 se o deque estiver vazio ou 0 caso o
deque não esteja vazio.
O(1)
d.begin() Retorna o iterator indexado no início do deque. O(1)
d.end() Retorna o iterator indexado no fim do deque. O(1)
d.front() Retorna o primeiro elemento do deque. O(1)
d.back() Retorna o último elemento do deque. O(1)
Métodos Modificadores <deque>
MÉTODO DESCRIÇÃO TEMPO DE EXECUÇÃO
d.push_front(value) Adiciona um valor no início do deque. O(1) (amortizado)
d.push_back(value) Adiciona um valor no fim do deque. O(1) (amortizado)
d.assign(begin, end) Limpa o container e copia os elementos do
iterator passado em begin até o iterator
passado em end.
O(n)
d.insert(iterator, value) Adiciona um valor na posição do iterator
passado.
O(n)
d.pop_front() Remove o primeiro elemento do deque. O(1)
d.pop_back() Remove o último elemento do deque. O(1)
d.erase(iterator) Remove o elemento onde está na posição do
iterator passado.
O(n)
d.erase(begin, end) Remove os elementos do iterator passado em
begin até o iterator passado em end.
O(n)
Exercício
 Faça um programa usando container deque qual leia uma quantidade N
de números (sendo N diferente de 0) e apresente na tela: Os números
digitados, a soma de todos os números digitados, a quantidade de
números digitados e a média aritmética da soma de todos os números,
conforme o exemplo abaixo:
ENTRADA SAÍDA
5
5
2
12
0
5 5 2 12 
24
4
6
Referências
 STANDART C++ CONTAINERS, acesso em novembro de 2014,
disponível em: http://cs.northwestern.edu/~riesbeck/programming/c++/stl-
summary.html#list
 Guia da consulta rápida C++ STL – Joel Saade, acesso em novembro de
2014.