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!”

Manipulação de tipos em C++

Há uma certa dificuldade para os programadores iniciantes na área de templates que se aventuram a manipular tipos. A primeira delas é quanto ao uso da palavra reservada typename. Essa palavra deve ser utilizada para informar ao compilador que o nome que vem em seguida é um tipo, e não um membro de uma estrutura ou uma variável. No código abaixo podemos ver isso. Esse é um exemplo onde criamos uma função que recebe um vetor e calcula a soma dos elementos desse vetor.

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

using namespace std;

template <class V>
V soma( const vector<V>& v ) {
  V aux = 0;

  for( typename vector<V>::const_iterator i = v.begin(); i != v.end(); ++i )
    aux += *i;

  return aux;
}

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

  v.push_back( 1.1 );
  v.push_back( 2.1 );
  v.push_back( 3.1 );

  cout << soma( v ) << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Sem a palavra typename na linha 11 temos as seguintes mensagens de erro:

main.cpp: In function `V soma(const std::vector<V, std::allocator<_CharT> >&)':
main.cpp:11: error: expected `;' before "i"
main.cpp:11: error: `i' undeclared (first use this function)
main.cpp:11: error: (Each undeclared identifier is reported only once for each function it appears in.)
main.cpp: In function `V soma(const std::vector<V, std::allocator<_CharT> >&) [with V = double]':
main.cpp:25:   instantiated from here
main.cpp:11: error: dependent-name ` std::vector<V,std::allocator<_CharT> >::const_iterator' is parsed as a non-type, but instantiation yields a type
main.cpp:11: note: say `typename  std::vector<V,std::allocator<_CharT> >::const_iterator' if a type is meant

Ocorre que o compilador assume que const_iterator é um nome de um membro (variável ou método) da classe vector<V>, e não um nome de tipo (nesse caso específico, um tipo definido através de um typedef). De uma forma geral, toda expressão envolvendo um parâmetro da template (no exemplo, o V) onde ocorre acesso à um campo de uma estrutura (uso do “::”) será encarado pelo compilador não como um tipo mas sim como um membro dessa estrutura. Se quisermos que o compilador veja ali um tipo devemos preceder a declaração com a palavra reservada typename. Pelo menos o compilador nos dá uma boa dica do problema na mensagem de erro nº 8:  ”note: say `typename  std::vector<V,std::allocator<_CharT> >::const_iterator’ if a type is meant“.

Note que no fonte, na linha 9 temos a declaração da variável aux sem a necessidade do typename, pois nesse caso o compilador assume que V é um tipo.

Lidando com tipos internos

Porém há situações onde alguns tipos são informados como typedefs internos à uma estrutura (classe). É o caso de todos os containers da stl, que possuem o tipo value_type definido como o tipo do objeto que o container armazena. Essa informação é útil para a construção de rotinas mais genéricas, onde não se sabe o tipo do container. A função soma do exemplo acima lida apenas com vectors.  Mas ela pode ser redefinida para lidar com qualquer classe container (ou compatível) da seguinte forma: ao invés de receber o parâmetro const vector<V>& v ela passa a receber const V& v. O problema é que nesse caso não sabemos o tipo do elemento armazenado no container. É para isso que serve o tipo value_type. E aí, dessa vez precisaremos usar typename antes de V::value_type.

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

using namespace std;

template <class V>
typename V::value_type soma( const V& v ) {
  typename V::value_type aux = 0;

  for( typename V::const_iterator i = v.begin(); i != v.end(); ++i )
    aux += *i;

  return aux;
}

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

  v.push_back( 1.1 );
  v.push_back( 2.1 );
  v.push_back( 3.1 );

  cout << soma( v ) << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Na linha 8 temos o tipo de retorno da função: V::value_type, devidamente precedido por typename para informar ao compilador que se trata de um tipo (de modo análogo na linha 9 temos a declaração da variável aux).

“Hasta la vista, baby!”

Adiando a definição de uma template interna a uma classe template

Às vezes devido às dependências do código precisamos adiar a definição de uma template até um determinado ponto do programa fonte – por exemplo se no código dessa template for necessário uma declaração feita mais a frente. Outro motivo seria simplesmente manter a declaração da classe pequena, deixando a definição em outra parte do código – sem contar que qualquer declaração dentro de uma classe será automaticamente considerada inline sempre que possível.

A sintaxe para isto é estranha. Veja os trechos de código a seguir.

Declaração:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

A classe Estado é uma template com um construtor e um método template (cobertura), e a classe Municipio é uma template interna à classe Estado, e possui um método comum (praias) e um outro método template (hotel). O método hotel depende de três parâmetros template: T, U e V.

Não há mistério na definição fora da classe do construtor Estado. A coisa começa a ficar estranha para o método cobertura, pois este precisa de dois parâmetros.

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T, class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

A saída para esta compilação é:

38 main.cpp: prototype for `void Estado<T>::cobertura(W)' does not match any in class `Estado<T>'
38 main.cpp: template<class T> template<class W> void Estado::cobertura(W)
38 main.cpp: template definition of non-template `void Estado<T>::cobertura(W)'
[Build Error] [main.o] Error 1

A linha 2  já nos indica qual a solução: template <class T> template<class W>

A sintaxe para a declaração de templates aninhadas é essa. Com qualquer nível de aninhamento. Assim, o código final para a declaração das templates externamente à classe é mostrado a seguir.

Código final:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T> template <class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

template <class T> template <class U>
Estado<T>::Municipio<U>::Municipio( string nome ): nome(nome) {
  // Um código qualquer aqui
}

template <class T> template <class U>
int Estado<T>::Municipio<U>::praias() {
  // Um código qualquer aqui
  return 0;
}

template <class T> template <class U> template <class V>
inline void Estado<T>::Municipio<U>::hotel( V v ) {
  // Um código qualquer aqui
}

int main(int argc, char *argv[])
{
  Estado<int> rio("Rio de Janeiro");
  Estado<int>::Municipio<double> buzios("Búzios");

  rio.cobertura( 4 );
  buzios.hotel( 5 );
  cout << buzios.praias() << endl;

  return EXIT_SUCCESS;
}

Dessa forma, além de podermos contornar as possíveis dependências do código também podemos manter a declaração de uma classe template enxuta – sem comprometer o desempenho, pois nada impede que usemos a opção inline (linha 55).

“All the world’s a stage…”

Não funciona…

#include <cstdlib>
#include <iostream>

using namespace std;

class MyClass {
  template <class T>
  virtual void foo(T& t) {}
};

int main(int argc, char *argv[])
{
  system("PAUSE");
  return EXIT_SUCCESS;
}

Saída:

invalid use of `virtual' in template declaration of 'virtual void MyClass::foo(T&)'

Detalhes:

Métodos implementados por templates não podem ser virtuais. Que chato, mas a pergunta é: porque alguém iria querer que um método template fosse virtual?

“ô loco, meu…”

Para aqueles que, como eu, ficam loucos quando vêem uma mensgaem de erro de template com nomes de 500 caracteres, existe um pequeno programa chamado STLFilt que filtra essas mensagens e as torna um pouco mais palatáveis… algo do tipo:

    rtmap.cpp: In function `int main()':
    rtmap.cpp:19: invalid conversion from `int' to `
       std::_Rb_tree_node<std::pair<const int, double> >*'
    rtmap.cpp:19:   initializing argument 1 of `std::_Rb_tree_iterator<_Val, _Ref,
       _Ptr>::_Rb_tree_iterator(std::_Rb_tree_node<_Val>*) [with _Val =
       std::pair<const int, double>, _Ref = std::pair<const int, double>&, _Ptr =
       std::pair<const int, double>*]'
    rtmap.cpp:20: invalid conversion from `int' to `
       std::_Rb_tree_node<std::pair<const int, double> >*'
    rtmap.cpp:20:   initializing argument 1 of `std::_Rb_tree_iterator<_Val, _Ref,
       _Ptr>::_Rb_tree_iterator(std::_Rb_tree_node<_Val>*) [with _Val =
       std::pair<const int, double>, _Ref = std::pair<const int, double>&, _Ptr =
       std::pair<const int, double>*]'
    E:/GCC3/include/c++/3.2/bits/stl_tree.h: In member function `void
       std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::insert_unique(_II,

       _II) [with _InputIterator = int, _Key = int, _Val = std::pair<const int,
       double>, _KeyOfValue = std::_Select1st<std::pair<const int, double> >,
       _Compare = std::less<int>, _Alloc = std::allocator<std::pair<const int,
       double> >]':
    E:/GCC3/include/c++/3.2/bits/stl_map.h:272:   instantiated from `void std::map<_
    Key, _Tp, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _Input
    Iterator = int, _Key = int, _Tp = double, _Compare = std::less<int>, _Alloc = st
    d::allocator<std::pair<const int, double> >]'
    rtmap.cpp:21:   instantiated from here
    E:/GCC3/include/c++/3.2/bits/stl_tree.h:1161: invalid type argument of `unary *
       '

Se torna um pouco mais legível:

      *** {BD Software Proxy c++ for gcc v3.01} STL Message Decryption is ON! ***
    rtmap.cpp: In function `int main()':
    rtmap.cpp:19: invalid conversion from `int' to `iter'
    rtmap.cpp:19:   initializing argument 1 of `iter(iter)'
    rtmap.cpp:20: invalid conversion from `int' to `iter'
    rtmap.cpp:20:   initializing argument 1 of `iter(iter)'
    stl_tree.h: In member function `void map<int,double>::insert_unique(_II, _II)':
        [STL Decryptor: Suppressed 1 more STL standard header message]
    rtmap.cpp:21:   instantiated from here
    stl_tree.h:1161: invalid type argument of `unary *'

    STL Decryptor reminder:
        Use the /hdr:L option to see all suppressed standard lib headers