BLOG C++

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

Evitando conflitos de nomes

namespace é uma palavra reservada do C++ que implementa um mecanismo capaz de expressar agrupamento lógico. Em outras palavras, se um conjunto de declarações estão logicamente associadas de acordo com algum critério, elas podem ser colocadas juntas no mesmo namespace para expressar este fato. Um namespace também pode ser chamado de um contexto. O uso de namespaces, além de proporcionar agrupamento lógico,  serve para evitar o conflito de nomes: dois identificadores podem ter o mesmo nome se estiverem em namespaces diferentes. Como é um mecanismo que define escopo, o nome de um identificador fora de seu namespace deve ter o nome do namespace na frente, seguido do operador de escopo “::”.  Namespaces também afetam o mecanismo de mangling que o C++ usa.

A sintaxe para namespace é bem intuitiva, semelhante à de uma classe. No entanto, um namespace define apenas escopo, e não um tipo em si. Funções declaradas dentro de um namespace não são métodos, são apenas funções.

Exemplo:

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem() {
    std::cout << "Uma mensagem qualquer!" << std::endl;
  }
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

No exemplo acima, declaramos um namespace Teste e dentro deste, a função escreveMensagem(). Note na linha 6 o uso de identificadores declarados em outro namespace: std::cout e std::endl. cout e endl são variáveis declaradas dentro do namespace std. O uso de um identificador com o seu namespace é chamado de nome qualificado ou completo.

Usando Namespaces

Em um determinado ponto pode se tornar tedioso ter de repetir o nome do namespace sempre que se quer utilizar um determinado identificador de um outro namespace. Para estas situações existem duas abordagens previstas no C++.

1) using namespace std;

Essa construção, chamada de global using-directive, é mais geral pois importa todos os identificadores do namespace std, e por isso deve ser utilizada com bastante parcimônia: tem como consequência justamente anular o mecanismo de separação de escopos proposto pelo namespace.

Há autores inclusive que defendem que seu uso deve ser limitado apenas a código herdado, ou seja, sistemas e bibliotecas antigos, escritos antes da introdução desse mecanismo em C++. Não sou tão radical, para pequenos programas acho essa sintaxe bastante conveniente. Deve ser porque programo em C++ desde 1989, quando não havia namespaces (nem templates, nem exceções, nem herança múltipla… é, pode me chamar de velho! ). Para sistemas grandes porém, é melhor realmente não utilizar essa opção. Em seu livro “The C++ Programming Language” Bjarne Stroustrup recomenda o seguinte (tradução livre): “Diretivas globais de using são uma ferramenta de transição e de outra forma devem ser evitadas. Em um namespace, a diretiva using é uma ferramenta para a composição de namespaces.  Em uma função (somente), uma diretiva using pode ser seguramente utilizada como uma conveniência notacional”.

2) using std::cout;

Essa construção importa apenas o identificador cout, sendo bem mais seletiva. Nesse caso o identificador endl não foi importado, sendo necessário para o seu uso o nome completo: std::endl.

Cabe dizer que uma diretiva using (global ou não) pode ser colocada nos seguintes  escopos: global, dentro de um namespace, dentro de uma função, dentro um método ou mesmo dentro de um bloco. Não é permitido colocar using diretamente dentro de uma classe ou estrutura. Esse posicionamento por si só define o escopo da importação em questão. Via de regra, deve-se utilizar o menor escopo possível, pesando-se sempre a conveniência da notação com a violação da separação de escopos.

Boas práticas

Um namespace não precisa declarar tudo o que será utilizado de uma só vez, e embora seja confuso ter mais de uma declaração com o mesmo namespace isso é permitido (porém desaconselhável). No entanto, é razoável ter em um lugar (um arquivo “.h”, por exemplo) apenas as declarações e em outro lugar a implementação propriamente dita. Há duas formas de se fazer isso, ilustradas a seguir. A primeira faz uma extensão na declaração do namespace, a segunda usa o nome qualificado do identificador sendo definido. Particularmente acho perigosa a primeira opção, prefiro a segunda.

Dividindo namespaces

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem();
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

// em qualquer outro lugar ou arquivo!!

namespace Teste {
  void escreveMensagem() {
    using namespace std;

    cout << "Uma mensagem qualquer!" << endl;
  }
}

Implementação usando nomes qualificados

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem();
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

// Em qualquer outro lugar ou arquivo!!

void Teste::escreveMensagem() {
  using std::cout;
  using std::endl;

  cout << "Uma mensagem qualquer!" << endl;
}

Um namespace pode conter outros namespaces. Nesse caso teremos um namespace aninhado a outro namespace. O conceito é o mesmo de aninhamento de blocos ou aninhamento de classes. Inclusive, se o namespace A contém o namespace B que por sua vez contém o identificador X, o nome qualificado de X é A::B::X. Por outro lado, um namespace somente pode ser declarado no escopo global ou dentro de outro namespace. Não é permitido que um namespace seja declarado dentro de uma função, classe ou método.

Podemos também definir aliases para namespaces. O escopo é semelhante ao de uma declaração using: global, dentro de funções, métodos ou blocos. Um alias é uma forma conveniente de dar outro nome a um namespace. A vantagem é poder trocar rapidamente um pacote de uma biblioteca por outro (desde que as interfaces sejam compatíveis, lógico). A sintaxe é:

void foo() {
  namespace NovoNome = std;

  NovoNome::cout << "Uma mensagem" << NovoNome::endl;
}

Por último, por mais estranho que pareça, é permitido declarar um namespace sem nome. Nesse caso o compilador cria um nome temporário, que não pode ser acessado de nenhum outro lugar a não ser a unidade sendo compilada – esta inclusive pode acessar livremente qualquer identificador dentro desse namespace. Ou seja, funciona como uma restrição de escopo no estilo static functions.

“In my place, in my place / Were lines that I couldn’t change“

Código Fonte:

#include <cstdlib>
#include <iostream>

using namespace std;

struct A {
  void funcaoA() {}
};

struct B {
  void funcaoB() {}
};

struct C {
  void funcaoC() {}
};

struct ABC1 {
  A a;
  B b;
  C c;
};

struct ABC2: public A, public B, public C {
};

int main(int argc, char *argv[])
{
  cout << "sizeof( A ): " << sizeof( A ) << endl;
  cout << "sizeof( B ): " << sizeof( B ) << endl;
  cout << "sizeof( C ): " << sizeof( C ) << endl;
  cout << "---" << endl;
  cout << "sizeof( ABC1 ): " << sizeof( ABC1 ) << endl;
  cout << "sizeof( ABC2 ): " << sizeof( ABC2 ) << endl;

  ABC1 x;
  ABC2 y;

  x.a.funcaoA();
  y.A::funcaoA();

  system("PAUSE");
  return EXIT_SUCCESS;
}

Saída:

sizeof( A ): 1
sizeof( B ): 1
sizeof( C ): 1
---
sizeof( ABC1 ): 3
sizeof( ABC2 ): 1
Pressione qualquer tecla para continuar. . .

Como vimos neste outro post, mesmo que uma classe ou estrutura não contenha atributos ela deve ocupar pelo menos um byte. Normalmente, classes sem atributos são para declarar ou implementar interfaces,ou para o reaproveitamento organizado de código. Uma outra utilidade é na composição de templates, em particular para o caso de expressões lambda. (link).

Qualquer que seja a situação, se uma classe possui um campo que é uma classe vazia (sem atributos), esse campo terá de ocupar pelo menos um byte. Com a composição de templates no caso das expressões lambda podemos chegar a ter uma composição de classes vazias ocupando uma grande quantidade de bytes no final.

Esse exemplo acima ilustra uma possibilidade de reduzirmos ou eliminarmos a quantidade de espaços vazios alocados inutilmente para este tipo de classe.  A classe ABC1 ocupou 3 bytes, enquanto a classe ABC2 ocupou apenas um byte. Semanticamente não é a mesma coisa, porém para o caso de templates normalmente isso não fará diferença pois estaremos mais interessados no código dos métodos do que em outra coisa.

Essa abordagem no entanto apresenta algumas dificuldades, na medida em que utiliza herança múltipla. Por exemplo, se as classes possuírem métodos virtuais não haverá nenhum ganho de espaço devido às VMTs.

Além disso, a sintaxe muda um pouco na hora de chamar os métodos como podemos observar na linha 40.

“So this is Christmas/And what have you done/Another year over/And a new one just begun.”

Programa lento? Já viu se é a gerência de memória?

Redefinindo os operadores new e delete

É fato conhecido entre os programadores C++ que a gerência de memória implementada na biblioteca padrão do C/C++ é ineficiente para a alocação/liberação de muitos (mas muuuuuitos mesmo!) blocos de memória de tamanhos distintos. Programas que alocam e liberam objetos freneticamente pagam um preço muito alto se utilizarem os operadores new e delete padrão. O problema ocorre porque as rotinas que manipulam os blocos de memória devem lidar com blocos de tamanhos diferentes, e isso significa trabalhar com listas encadeadas, encontrar blocos de tamanho adequado, fragmentação etc. Nesse link há uma pequena introdução sobre o assunto.

O programa a seguir aloca e desaloca objetos freneticamente. Não quero discutir o que o programa faz, na verdade ele foi copiado daqui (uma comparação de desempenho entre Java, C++ e outras linguagens…) com duas pequenas alterações: 1) eliminei a chamada a gettimeofday e meço o tempo pelo SO; 2) o programa original tinha um leak de memória. Quero apenas mostrar como esse programa roda usando o new e delete padrão, e como uma abordagem não intrusiva para redefinir esses operadores consegue fazer com que esse programa rode 10x mais rápido…

Código original:

#include <stdio.h>
#include <iostream>

using namespace std;

class Person {
  public:
    Person( int id, int count ): _next(NULL), _prev(NULL), _count(count), _id(id) {}

    int shout( int shout, int nth ) {
      if( shout < nth )
        return shout + 1;

      _prev->_next = _next;
      _next->_prev = _prev;

      return 1;
    }

    int count() const { return _count; }
    Person* next() const { return _next; }
    Person* prev() const { return _prev; }

    void next(Person* person) { this->_next = person ; }
    void prev(Person* person) { this->_prev = person; }

   private:
     int _count;
     int _id;
     Person* _next;
     Person* _prev;
};

class Chain {
  public:
    Chain(const int id, const int size) : _first(NULL), _id(id) {
      Person* current = NULL;
      Person* last = NULL;

      for( int i = 0 ; i < size ; i++ )
      {
        current = new Person( id + i, i );

        if( _first == NULL )
          _first = current;

        if( last != NULL ) {
          last->next(current);
          current->prev(last);
        }

        last = current;
      }

      _first->prev(last);
      last->next(_first);
    }

    Person* kill( const int nth ) {
      Person* current = _first;
      int shout = 1;

      while( current->next() != current )
      {
        Person* tmp = current;

        shout = current->shout( shout,nth );
        current = current->next();

        if( shout == 1 )
          delete tmp;
      }

      _first = current;

      return current;
    }

    Person* first() const  { return _first; }

    ~Chain() { delete _first; }

  private:
      Person* _first;
      int _id;
};

int main( int argc, char* argv[] )
{
  const int ITER = 10000000;

  for( int i = 0 ; i < ITER ; ++i ) {
    Chain* chain = new Chain(i, 40);

    chain->kill(3);
    delete chain;
  }

  return 0;
}

Ok, o código acima é meio doido. É sobre a história de Flávio Josefo, por vezes designado como problema de Josefo ou Roleta Romana. Mas o interessante é que ele aloca e libera 410 milhões de pequenos objetos com dois tamanhos diferentes e de forma intercalada, gerando um estresse nas rotinas de gerência de memória. Apesar desse número, o consumo de memória do programa é mínimo: a cada instante, o número máximo de objetos alocados é 41. De certa forma, esse programa mimetiza o comportamento de um programa que executa sequencialmente milhares de pequenas tarefas por minuto em transações curtas: para cada tarefa é alocado um pequeno número de objetos de tamanhos distintos e após a transação estes objetos são liberados.  O tempo de execução e opções de compilação são mostrados a seguir:

Máquina          : Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
Sistema          : Windows XP SP2
Compilador       : gcc version 4.4.0 (mingw32)
Linha de comando : g++ -O3 -funroll-loops -fprefetch-loop-arrays -march=core2 -msse4 ChainOriginal.cpp -o ChainOriginal.exe
Tempo de execução: 71.88 segundos

Pois bem, o que há de errado com esse código? Nada, exceto que os operadores new e delete fazem uma série de operações internas sobre listas encadeadas de espaços de memória livre que os tornam um pouco lentos. A gerência da memória dinâmica é um tópico complexo de estudo. Há vários substitutos específicos das rotinas padrão do C++ que gerenciam memória e que são mais eficientes para determinadas situações do que as rotinas genéricas. E há algumas técnicas para diminuir o tempo gasto com essa gerência – aqui vou mostrar uma variação bem simples de uma técnica conhecida como slab allocation e que é utilizada por exemplo pelo kernel do Linux. Essa técnica funciona com buffers ou caches de áreas de memória, uma para cada determinado tipo de objeto, e se adequa bem para a situação acima. Ela é muito boa quando o programa possui um número qualquer de objetos de classes distintas sendo alocados e liberados frequentemente. A implementação a seguir funciona apenas quando a não há hierarquia de classes – ou seja, não há subclasses. Para funcionar com subclasses é necessária uma outra implementação, um pouco menos eficiente pois terá de lidar com destrutores virtuais e sobrecarga de operadores. Mas vamos por partes.

Non-Virtual Slab Allocation:

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class Cache {
  private:
    vector<void*> cache;

  public:
    enum Config { Max = 100 }; // Número máximo de objetos mantido no cache.
                               // Quando esse número é atingido, as chamadas
                               // a "free" realmente liberam os objetos.

    Cache(): cache() {
      cache.reserve( Max );
    }

    void *alloc( size_t size ) {
      if( cache.size() > 0 ) {
        void* aux = cache.back();

        cache.pop_back();
        return aux;
      }
      else
        return new char[size];
    }

    void free( void* ptr ) {
      if( cache.size() < Max )
        cache.push_back( ptr );
      else
        delete[] (char *) ptr;
    }
};

template <class C>
class NonVirtualSlab {
  private:
    static Cache cache;

  public:
    void* operator new ( size_t size ) {
      return cache.alloc( size );
    }

    void operator delete ( void* ptr, size_t ) {
      cache.free( ptr );
    }
};

template <class C>
Cache NonVirtualSlab<C>::cache;

class Person: public NonVirtualSlab<Person> {
  public:
    Person( int id, int count ): _next(NULL), _prev(NULL), _count(count), _id(id) {}

    int shout( int shout, int nth ) {
      if( shout < nth )
        return shout + 1;

      _prev->_next = _next;
      _next->_prev = _prev;

      return 1;
    }

    int count() const { return _count; }
    Person* next() const { return _next; }
    Person* prev() const { return _prev; }

    void next(Person* person) { this->_next = person ; }
    void prev(Person* person) { this->_prev = person; }

   private:
     int _count;
     int _id;
     Person* _next;
     Person* _prev;
};

class Chain: public NonVirtualSlab<Chain> {
  public:
    Chain(const int id, const int size) : _first(NULL), _id(id) {
      Person* current = NULL;
      Person* last = NULL;

      for( int i = 0 ; i < size ; i++ )
      {
        current = new Person( id + i, i );

        if( _first == NULL )
          _first = current;

        if( last != NULL ) {
          last->next(current);
          current->prev(last);
        }

        last = current;
      }

      _first->prev(last);
      last->next(_first);
    }

    Person* kill( const int nth ) {
      Person* current = _first;
      int shout = 1;

      while( current->next() != current )
      {
        Person* tmp = current;

        shout = current->shout( shout,nth );
        current = current->next();

        if( shout == 1 )
          delete tmp;
      }

      _first = current;

      return current;
    }

    Person* first() const  { return _first; }

    ~Chain() { delete _first; }

  private:
      Person* _first;
      int _id;
};

int main( int argc, char* argv[] )
{
  const int ITER = 10000000;

  for( int i = 0 ; i < ITER ; ++i ) {
    Chain* chain = new Chain(i, 40);

    chain->kill(3);
    delete chain;
  }

  return 0;
}

Tempo total de execução com as mesmas opções do compilador: 7.67 segundos! Aproximadamente 9.4 vezes mais rápido! E a única modificação a ser feita no fonte são nas linhas 57 e 85, onde é acrescentado a herança para NonVirtualSlab<>.

Bom, para herança e métodos virtuais é necessário uma outra implementação. Em breve posto ela aqui.

“Is this the real life? Is this just fantasy?”

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