UFSM > Ciência da Computação

Primeiro Semestre de 2012
Professora: Juliana Kaizer Vizzotto

Templates em C++

1. Imagine que queremos criar uma biblioteca em C++ para criar e manipular pilhas (`stacks`) de inteiros. Poderíamos fazer isso simplesmente como segue:

   class stack{ 
       public:
           Stack(int size){
               stack = new int[size];
               topo=0;
               ... 
            }
           ...
            
           int push(int in){
                stack[topo++] = i;
               ...
           }
           ...
        private:
             int topo;
             int *stack;  
   };
   

2. E agora se precisarmos de um outra pilha de `double` ao invés de `int`?

3. Ok! Podemos alterar o código acima para `double`!

4. Mas se quisermos um pilha genérica???

5. Templates resolvem esse problema!!

   template<class Type>
   class Stack {
           public: 
                 Stack(int size){
                     stack = new Type[size];
                     topo = 0;
                     ...
                  }
                  ...
                 
                void push(const Type &t){
                   stack[topo++]=t;
                   ...
                }
           private:
                 int topo;
                 Type *stack;
   };
   

6. No código acima usou-se a palavra-chave template, seguida do nome genérico ente ` < > `. Neste caso, ` Type ` . Se quiséssemos usar 2 tipos genéricos, ficaria ` template< class Foo, class Bar> `.

7. Agora, como se cria uma pilha de inteiros e de doubles?

   int main(){
       Stack<int> pilha1(10);
       Stack<double> pilha2(10);
       pilha1.push(2);
       pilha2.push(3.14);
      
       cout << pilha1.top() << "\n";
       pilha2.pop();
       
       return 0;
   }
   

Standard Template Library (STL) em C++

1. A linguagem C++ fornece uma biblioteca de estrutura de dados genérica usando Templates pronta para o usuário/programador. Vamos revisar alguns das estruturas de dados fornecidas na biblioteca.

2. Pilha A pilha é uma das estruturas de dados mais simples: ela representa um container de dados onde se coloca qualquer quantidade de valores e sempre se retira o último valor que foi colocado (o mais recente). A estratégia é chamada LIFO (Last-In,First-Out).

3. Exemplo1: Receba como entrada um número N seguido de N inteiros. Imprima esses inteiros na ordem inversa que eles foram informados na entrada.

#include <stack>
#include <iostream>
using namespace std;
int main(){
   long N, num;
   stack<long> s;
   cin >> N;
   while (N>0){
     cin >>num;
     s.push(num);
     N--;
   }
   while(!s.empty()){
    cout << s.top() << endl;
    s.pop();
   }
}

1. Dicas: Releia o enunciado da questão. Depois de ter certeza que entendeu o enunciado, marque 10 minutos. Durante esse tempo, tente elaborar um algoritmo para resolver a questão (não codifique nada, apenas idealize um algoritmo). Só continue lendo depois de fazê-lo.

2. [Exercício: Parentheses Balance, questão 673 da Uva http://online-judge.uva.es/p/v6/673.html]

Filas

1. Filas são containers de dados que seguem o regime LILO (Las-In, Last-Out), ou seja, o próximo valor removido da fila é aquele que está armazenado a mais tempo.

2. [Exemplo The Dole Queue, questão 133 do UVa http://online-judge.uva.es/p/v1/133.html].

3. Dada uma fila circular com N elementos numerados de 1 a N e dois inteiros K e M, o objetivo é simular o sgeuinte algoritmo. UM juiz inicia no começo da fila e caminha K posições na ordem crescente dos números até chegar ao K-ésimo elemento. Outro juiz inicia no final da fila e caminha M posições na ordem descresnte dos números até chegar ao M-ésimo elemento. O K-ésimo e o M-ésimo elementos devem ser removidos da fila. O procedimento continua até a fila esvaziar.

   #include <cstdio>
   #include <queue>
   #include <iostream>
   using namespace std;
   queue<int> removeX(queue<int> q, int x){
     queue<int> ret;
     while (!q.empty()){
       if (q.front() !=x) ret.push(q.front());
       q.pop();
     }
     return ret;
   }
   int main(){
      int N, k, m, i, d1, d2;
      while(true){
        scanf("%d,%d,%d",&N,&k,&m);
        if (!N&&!k&&!m) return 0;
        queue<int> qk,qm;
        for (i=1;i<=N;i++) qk.push(i);
        for (i=1;i>=N;i--) qm.push(i);
        while (!qk.empty()){
         for (i=0;i<k;i++){
           d1 = qk.front();
           qk.pop();
           if (i !=k-1) qk.push(d1);
         }
         for (i=0; i<m;i++){
            d2 = qm.front();
            qm.pop();
            if (i!=m-1) qm.push(d2);
         }
         if (d1==d2){
           printf("%3d",d1);
           if (!qk.empty()) putchar(',');
         }
        else {
         qk = removeX(qk,d2);
         qm = removeX(qm,d1);
         printf("%3d%3d",d1,d2);
         if (!qk.empty()) putchar(',');
         }
       }
     }
   }
   

4. A função `removeX` serve para remover todas as ocorrências de um valor x de uma fila q, retornando a fila resultante. Isso é útil para remover da fila o K-ésimo ou o M-ésimo elemento da fila.

5. Para esta questão são usadas as variáveis N,k e m lidas da entrada, assim como a variável contadora i, e as variáveis d1 e d2 que indicam respectivamente o k-ésimo e o m-ésimo elemento da fila. O laço principal lê os três inteiros da entrada e termina quando os três foram informados iguais a zero.

6. A solução faz uso de duas filas de inteiros, chamadas qk e qm. Elas são iniciadas respectivamente com os números de 1 a N em ordem crescente e decrescente. Após determinamos o k-ésimo elemento da fila, que é armazenado na variável d1. Depois o m-ésimo elemento da fila é determinado, que é armazenado na variável d2. Tanto o elemento d1 quanto o elemento d2 não são devolvidos de volta para as respectivas filas. Logo a saída é exibida. Se o k-ésimo elemento e o m-ésimo elemento forem iguais esse elemento é apenas exibido sem a necessidade de removê-los (já que ele não foi devolvido para a mesma). Caso eles sejam diferentes, d2 é removido da fila qk e d1 é removido da fila qm. Depois disso os elementos d1 e d2 são impressos.

7. [Exercícios Australian Voting, questão 10142 do UVa http://online-judge.uva.es/p/v101/10142.html]

8. O objetivo é indicar qual(is) o(s) vencedor(es) de uma eleição em que participaram n candidatos e m eleitores. Cada eleitor vota em n candidatos na ordem de sua preferência. Se um candidato obtiver mais do que a metade dos votos dos eleitores, ele é eleito. Caso contrário, os votos dos candidatos empatados em último lugar devem ser ignorados e o voto daquele eleitor específico deve passar para a próxima preferência. O procedimento prossegue até que um candidato tem mais que 50% dos votos ou até que haja um empate entre todos os candidatos ainda não eliminados (caso em que todos eles devem ser impressos como vencedores).

Vector

1. Exemplo:

   #include <iostream>
   #include <vector>
   #include <string>
   //#include <stdio.h>
   using namespace std;
   int main(){
        vector<string> VS;
        string frase;
        int N;
        
        cin >> N;
        getline(cin,frase); //limpa o buffer
        while (N > 0){
        cout << "Digite uma frase: ";
        getline(cin,frase);
        VS.push_back(frase);
        N--;
        }
        
        int i;
        cout << VS.size() << endl;
        for (i=0;i< VS.size();i++){
           cout << VS[i] << endl;
        }
   }