MAC 413/5715 - Tópicos de Programação Orientada a Objetos

Aula 21 - 30/10/2002

Programação Genérica

• Em inglês: Generic Programming ou, mais informalmente, generics
• O objetivo de programação genérica é generalizar componentes de software de forma a facilitar a sua re-utilização.
• Programação genérica busca construir [famílias de] componentes que ao mesmo tempo:
• sejam genéricas o suficiente para serem altamente re-utilizadas e que
• sejam eficientes em todas as situações em que são utilizadas.
• O exemplo mais famosos são as templates de C++ (espécie de "formas")
• As templates são uma extensão de C++ com uma série de coisas que são processadas em tempo de compilação gerando código específico para os tipos utilizados
• Como conseqüência, a compilação se torna muito mais pesada mas o desempenho de tempo de execução pode melhorar muito.

Exemplo usando templates de C++

• Uma Pilha Genérica

template <class T>
class PilhaGenerica {
 private:
   T P[100];
   int topo;
 public:
   PilhaGenerica () : topo (-1) { };
   int push ( T elem) { P[++topo] = elem; }
   T pop () { top--; return P[topo+1]; }
   ...
 }
 
• utilização:

typedef PilhaGenerica<float> PilhaReal;
typedef PilhaGenerica<MeuObj> PilhaObjs;

PilhaReal minhaQueridaPilha;
minhaQueridaPilha.push(3.2);
 

• poderia generalizar também o tamanho:

template <class T, int tamanho>

PilhaGenerica<MeuObj, 256> pilhao;
pilhao.push (new MeuObj ("Oba!"));
 

• Melhoria:
• int push ( T elem) utiliza o construtor copiador de T, i.e., quando passamos elem como um argumento, se elem é um objeto, o compilador insere uma chamada ao construtor copiador (copy constructor)
• isso pode ser lento demais e pode não ser o que queremos.
• Alternativa: passar uma referência:

int push (const T& elem)
 

• Poderíamos fazer algo semelhante usando objetos mas seria muito mais lento pois a flexibilidade seria "resolvida" em tempo de execução

• Outro Exemplo: Uma função de cópia

void* memcpy(void* region1, const void* region2, size_t n)
{
  const char* first = (const char*)region2;
  const char* last = ((const char*)region2) + n;
  char* result = (char*)region1;
  while (first != last)
    *result++ = *first++;
  return result;
}

• já é um pouco genérica pois devolve um ponteiro de tipo indefinido
• mas pode ser generalizada para copiar qualquer tipo de coisa usando um template:

template <typename InputIterator, typename OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
  while (first != last)
    *result++ = *first++;
  return result;
}

• esta template poderia ser utilizada da seguinte forma:

#include <list>
#include <vector>
#include <iostream>

int main()
{
  const int N = 3;
  std::vector<int> region1(N);
  std::list<int> region2;

  region2.push_back(1);
  region2.push_back(0);
  region2.push_back(3);
  
  std::copy(region2.begin(), region2.end(), region1.begin());

  for (int i = 0; i < N; ++i)
    std::cout << region1[i] << " ";
  std::cout << std::endl;
}

C++ Standard Template Library (STL)

• Elementos principais:
1. Contêiners
• vetor, deque (double ended queue), lista ligada
• mapa, conjunto, multi-mapa, multi-conjunto
• implementados através de classes-template
• contém funções-padrão como insert(), erase(), begin(), end(), size(), capacity(), etc.
• contêiners específicos podem ter outras funções específicas
2. Iteradores
• são usados [por algoritmos] para percorrer os elementos dos contêiners
• é uma espécie de "ponteiro genérico" para elementos de um contêiner
• podemos incrementar [ou decrementar] um iterador para percorrer os elementos de um contêiner
• iteradores de vetores e deques permitem aritmética de ponteiros
3. Algoritmos
• representam comportamento ou funcionalidade que é aplicada a contêiners para processar o seu conteúdo
• ordenação, cópia, busca, união de contêiners, etc.
• implementados através de funções-template
• não são funções da classe do contêiner, são funções independentes (não muito OO)
• algoritmos podem ser utilizados não só com contêiners mas com qualquer tipo de dado compatível
• Algoritmos do STL:
• #include <algorithm>
• funções min(T a, T b, Compare com), max(Ta, Tb, Compare comp), swap(Ta, Tb)
• for_each (início, fim, operação)
• transform (ini_origem, fim_origem, ini_destino, operação)
• sort (ini, fim) // baseado historicamente no quicksort
• partial_sort (ini, fim_container, fim_regiao_ordenada) // baseado historicamente no heapsort (sempre nlogn)
• stable_sort (ini, fim) //baseado historicamente no mergesort (preserva a ordem de elementos iguais)
• partition (ini, fim, condicao) // move para o inicio os elementos que satisfazem a condicao
• remove (...) // remove elementos com um certo valor
• remove_if (...)// remove elementos que satisfazem um criterio
• unique (...) // remove elementos adjacentes iguais
• unique_copy // copia uma parte de um contêiner para outro eliminando duplicacoes
• merge // junta dois contêiners
• fill // preenche o container com um certo valor
• generate_n // preenche n posicoes de um container com o resultado dado por uma funcao
• replace_if // sustitui valores que satisfazem um criterio por outro valor
• random_shuffle // embaralham todos elementos
• binary_search ()
• equal_range () // verifica se um pedaço de um container é igual a um pedaço de outro
• find
•  (não muito importante) Para que um objeto qualquer possa ser armazenado em um contâiner STL, ele precisa ter
1. um construtor de cópia (gerado automaticamente pelo compilador)
2. operação de atribuição =
3. operador de igualdade ==
4. operador menor <

• Além dos 3 elementos principais, outros 3 tipos importantes de elementos são:
1. Adaptadores
• criam um envólucro em torno de outro componente adicionando funcionalidade
• podem ou não mudar a interface do componente original
• relacionado aos padrões Decorator e Adaptor
• Exemplo: contadores e medidores de desempenho desenvolvidos por David R. Musser
• Exemplo que altera interface: inverte ordem dos parâmetros, fixa um parâmetro
• Adaptadores pré-definidos: pilha (envólucro de vetor), fila, fila de prioridades, etc.
2. Objetos-Função ou  Functor
• São objetos que encapsulam uma função.
• Exemplo:
  
  class X {
    public:
      valor-devolvido operator() (argumentos) const ;
      ...
  };
  
  
  class PrintInt  {
     public:
       void operator() (int elem) const {
         cout << elem << ' ';
       }
  };
  
  int main () {
    vector<int> col;
  
    for (int i = 1; i <= 100; ++i)
      col.push_back (i)
  
    for_each (col.begin(), col.end(), PrintInt());
  
    cout << endl;
  }
  
  
  // definição de for_each:
  namespace std {
    template <class Iterator, class Operation>
    Operation for_each (Iterator act, Iterator end, Operation op)
    {
      while (act != end) {
         op (*act);
         ++act;
      }
      return op; // como op é um functor, ela pode ter sido modificada, i.e., 
                 // carregar algum estado relevante ou resultado final (e.g, media e desvio padrao)
     }
  }
• Vantagens em relação a funções normais:
1. assim como temos ponteiros e ponteiros espertos, os "objetos-função" são "funções espertas"
2. As funções podem ter estado associado a elas; diferentes instâncias do mesmo objeto-função podem ter estados diferentes simultaneamente.
3. Possuem um tipo (permite tipagem forte); podemos ter hierarquias de tipos de functors.
4. podem melhorar o desempenho pois muita coisa é definida em tempo de compilação
• conjuntos recebem a "ordem" como parâmetro (ou usam < se nada é definido):
  set<int, less<int>> conjunto;
  set<Pessoa, idade<Pessoa>> salaDeAula;
3. Alocadores
• objetos que definem como a memória de um contâiner será alocada (e desalocada)
• normalmente, um alocador padrão é usado mas programadores podem definir e usar novos
• diferentes contâiners podem usar alocadores diferentes simultaneamente
• é relativamente novo, deve começar a ser mais usado no futuro.

Referências

• Página Generic Programming Techniques .
• Página Generic Programming de David R. Musser

 
• Data Structures with STL. William Murray and Chris Pappas. Prentice-Hall, 2001.
• The C++ Standard Library. Nicolai Josuttis. Addison-Wesley, 1999.