BLOG C++

Concepts

O comitê de padronização do C++ox decidiu excluir concepts da proposta de evolução corrente da linguagem. Dessa forma uma importante ferramenta foi deixada de lado.

Na proposta discutida, concepts seria uma forma de garantir que determinado parâmetro de uma template implementa métodos específicos (obedecendo a um padrão) ou possui determinados tipos. Enfim, uma forma de garantir que uma template só irá ser instanciada se o tipo passado possuir certas características. Suponha que uma template necessite de um parâmetro tipo que possua o método mm. Atualmente, como não é possível especificar um concept, o compilador irá dar um erro de compilação durante a instanciação da template reclamando da falta do método mm. O problema é que uma template repassa seus parâmetros e instancia outra que instancia outra e assim por diante, de modo que a mensagem de erro costuma não ser muito clara, e possivelmente em uma template bem distante da original…

Um outro problema relacionado é quando queremos redefinir uma operação para um grupo de classes que não são da mesma hierarquia mas possuem métodos semelhantes – na STL, os containers, por exemplo, possuem sempre os métodos begin() e end() retornando iteradores. Se quisermos redefinir “operator <<” para imprimir um container teremos de fazer um operador para cada um dos tipos: vector, map, list etc. Uma forma mais simples de se fazer isso seria especificando um concept exigindo que os iteradores estejam presentes em uma template mais genérica.

Exemplo

#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <class A, class B>
ostream& operator << ( ostream& o, const pair<A,B>& n ) {
  return o << "(" << n.first << ", " << n.second << ")";
}

template <class T>
ostream& operator << ( ostream& o, const vector<T>& v ) {
  o << "[ ";
  for( typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

template <class K, class T>
ostream& operator << ( ostream& o, const map<K,T>& m ) {
  o << "[ ";
  for( typename map<K,T>::const_iterator i = m.begin(); i != m.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

int main(int argc, char *argv[])
{
  vector<int> v;
  map<int, string> m;

  v.push_back( 0 );
  v.push_back( 1 );
  v.push_back( 2 );

  m[0] = "zero";
  m[1] = "um";
  m[2] = "dois";

  cout << v << endl << m << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Na linha 8 criamos uma template para imprimir o tipo pair<A,B> redefinindo o operador “<<”. Nas linhas 13 e 21 fizemos o mesmo para imprimir vector<T> e map<K,T>. O código acima produz a seguinte saída:

[ 0 1 2 ]
[ (0, zero) (1, um) (2, dois) ]
Pressione qualquer tecla para continuar. . .

Simulando concepts

Podemos simular o uso de um concept. Para tanto, basta entendermos como funciona o compilador na hora de instanciar uma template. Em um primeiro momento, o compilador procura casar os parâmetros passados para a template com as templates candidatas. Há regras para desambiguidade se mais de uma casar, e o compilador só dará uma mensagem de erro se não for possível escolher uma.

Se uma template casa, mas dentro de seu código ela usa algo (um método ou um tipo) que não está definido para o tipo usado na instanciação será gerado um erro de compilação dizendo “mm não definido para tipo T”. Por outro lado, se um cabeçalho de uma template exigir algo do parâmetro que ele não tenha não será gerado um erro: apenas essa template não casará. O nome desse comportamento do compilador é “Substitution Failure Is Not An Error” ou simplesmente SFINAE (grato, Felipe Magno de Almeida).

Portanto, podemos exigir no cabeçalho de uma template que um determinado método (ou tipo) esteja presente para que a template case. As técnicas para fazer isso são um pouco confusas, mas vamos lá. No exemplo anterior gostaríamos de definir uma única template para o operador “<<”  que sirva para qualquer classe que tenha suporte a iteradores. Aqui o pulo do gato: templates de classes e estruturas permitem o uso de parâmetros default (templates de funções não!). Basta portanto criarmos um parâmetro default (que não será nunca usado) e que dependa da existência de um tipo ou método (nesse caso devemos tomar o endereço do método). Por exemplo, podemos criar uma template que só será instanciada se o tipo passado possuir o tipo interno “const_iterator” (todos os containers têm esse tipo interno):

template <class V, class Ok = typename V::const_iterator>
struct CheckItr {};

CheckItr< vector<int> > teste1;
CheckItr< int > teste2;

No código acima, a template CheckItr recebe um parâmetro V e um parâmetro Ok cujo default é V::const_iterator. Se quisermos fazer a verificação, esse parâmetro deve ser sempre preenchido automaticamente, ou seja, não devemos fornecer um tipo para ele. Dessa forma, a linha 4 do exemplo acima irá compilar normalmente instanciando “CheckItr< vector<int>, vector<int>::const_iterator >” ao passo que a linha 5 irá dar um erro de compilação pois int não possui o tipo const_iterator definido internamente – int nem é classe!

Agora a solução do exemplo: o operador “<<” é redefinido o tempo todo para “ostream&” e algum outro tipo. Se criarmos uma template genérica como abaixo teremos um grande problema de ambiguidade:

template <class T>
ostream& operator << ( ostream& o, const T& v );

Mas nós podemos exigir que o parâmetro T da template acima seja capaz de instanciar CheckItr – note que se ele não for capaz de instanciar o compilador irá apenas instanciar ou procurar outro operador “<<”. Dessa forma resolveríamos o problema de ter apenas uma template para todos os tipos que implementam iteradores. Mas como fazer isso? Se fosse uma função, seria simples, pois novamente poderíamos colocar um parâmetro default (parâmetro da função , não da template… template para funções não permitem parâmetros default). Veja:

template <class T>
void imprime( const T& v, CheckItr<T>* p = NULL ) {
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
}

Se a função imprime for chamada passando-se um vector, map, list ou qualquer outro objeto cuja classe defina const_iterator não haverá problema, ela será instanciada (novamente não se deve passar o parâmetro default). Se o tipo passado não possuir const_iterator, o compilador irá tentar casar com outra função imprime – se não conseguir, aí sim será gerado um erro de compilação. Infelizmente, não podemos definir parâmetros default para o operador “<<”, de modo que teremos de adotar uma outra estratégia para contornar essa limitação. A solução sugerida é colocar a verificação no parâmetro ostream&. Para tanto, definimos em CheckItr um tipo interno “ostream“, e o usamos no cabeçalho do operador “<<”. Segue:

template <class V, class Ok = typename V::const_iterator >
struct CheckItr {
  typedef ::ostream ostream;
};

template <class T>
ostream& operator << ( typename CheckItr<T>::ostream& o, const T& v ) {
  o << "[ ";
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

Assim essa template somente será instanciada se o parâmetro T puder instanciar CheckItr. Se isso ocorrer, o tipo CheckItr<T>::ostream existe, e a template casou. Ou seja, somente se T possui const_iterator definido que essa template para o operador “<<” será utilizada.

Segue o exemplo completo:

#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <class V, class Ok = typename V::const_iterator >
struct CheckItr {
  typedef ::ostream ostream;
};

template <class A, class B>
ostream& operator << ( ostream& o, const pair<A,B>& n ) {
  return o << "(" << n.first << ", " << n.second << ")";
}

template <class T>
ostream& operator << ( typename CheckItr<T>::ostream& o, const T& v ) {
  o << "[ ";
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

int main(int argc, char *argv[])
{
  vector<int> v;
  map<int, string> m;

  v.push_back( 0 );
  v.push_back( 1 );
  v.push_back( 2 );

  m[0] = "zero";
  m[1] = "um";
  m[2] = "dois";

  cout << v << endl << m << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Dessa forma a template acima atenderá todos os containers da STL e também qualquer classe que tenha definido o tipo const_iterator. Espera-se que se uma classe define const_iterator ela defina também begin() e end() - não fizemos isso no exemplo, mas isso pode ser verificado em CheckItr<T>.  Para verificar se um tipo possui um método a maneira mais simples é obter o endereço desse método usando o operador “&”. O retorno desse operador é uma constante, de modo que pode ser usado como parâmetro de uma template.

template <class V, typename V::const_iterator (V::*begin)() const = &V::begin,
                   typename V::const_iterator (V::*end)() const = &V::end >
struct CheckItr {
  typedef ::ostream ostream;
};

A verificação acima já checa se existe o tipo const_iterator por causa do valor de retorno de begin() e end(). Note que tomamos o cuidado de especificar uma variável ponteiro para membro constante de V, pois begin() é um método sobrecarregado e nesses casos o C++ exige informação de contexto.

“You shall not pass!”

Esse é o verdadeiro Fibonacci em C++…

Lógico que no post anterior sobre o desempenho do Java o objetivo não era calcular Fibonacci, mas mostrar que em chamadas recursivas o otimizador do Java leva a melhor. Uma implementação de Fibonacci em C++ usando este algoritmo recursivo,  sem passar para outros algoritmos mais óbvios como manter os dois últimos valores ou somar em um vetor, deve usar uma característica funcional da linguagem C++: a metaprogramação.

Este é o primeiro  post sobre metaprogramação que faço, mas é o exemplo clássico, muito simples e que causa um impacto enorme…

#include <iostream>;

using namespace std;

template<int n>
struct Fib {
  enum X { value = Fib<n-1>::value + Fib<n-2>::value };
};
template <>
struct Fib<1> {
  enum X { value = 1 };
};

template <>
struct Fib<0> {
  enum X { value = 0 };
};

int main(int argc, char *argv[]) {
  cout << Fib<45>::value << endl;
  return 0;
}

Tempo de execução: 0.01 segundo!

Às vezes 0.00 segundo (o sistema não conseguiu medir…). E o tempo de compilação foi normal, 0.58 segundos. Bom, esse programa não é genérico o suficiente para calcular para n, apenas para uma constante conhecida a tempo de compilação. Mas é um recurso do C++, e a gente programa em C++ para usar todos os recursos que a linguagem oferece.  É rápido por que é calculado em tempo de compilação. Não torna a compilação mais lenta pois o compilador instancia Fib<x> apenas uma vez e reaproveita o valor nas vezes seguintes.

Mas também é possível fazer um Fibonacci recursivo para qualquer n mesmo que ele não seja conhecido durante a compilação.

using namespace std;

template <int n>
struct FIB {
  enum X { value = FIB<n-1>::value + FIB<n-2>::value };

  static int generico( int k ) {
    return k > n ? FIB<n>::generico( k-1 ) + FIB<n>::generico( k-2 ) : especifico( k );
  }

  static int especifico( int k ) {
    return k == n ? value : FIB<n-1>::especifico( k );
  }
};

template <>
struct FIB<0> {
  enum X { value = 0 };

  static int especifico( int k ) { return 0; }
};

template <>
struct FIB<1> {
  enum X { value = 1 };

  static int especifico( int k ) {return k == 1 ? value : FIB<0>::especifico( k ); }
};

inline int fib( const int n ) {
  return FIB<15>::generico( n );
}

int main(int argc, char *argv[])
{
  cout << fib( 45 ) << endl;
  return 0;
}

No exemplo acima o tempo de execução foi de 0.03 segundo. O pulo do gato é o 15 na função fib. Ele instancia a série para os 15 primeiros elementos. Detalhe que esse número é configurável durante a compilação somente. Mas de qualquer forma o programa funciona usando o mesmo algoritmo original – só que muito mais rápido.

Foi uma mistura de metaprogramação com programação. Uma possibilidade do C++, que a gente usa de acordo com o problema em questão…

“Nunca diga nunca!”