Usando STL C++ Lib com o Arduino e Arquiteturas AVR

Diante do amadurecimento de projetos e a demanda de bibliotecas mais avançadas para lidar com coleções de dados e comunicação mais complexa via rede, me deparei com a necessidade de uso de containers como Vetores e Maps, porém o GCC para AVR não possui a biblioteca padrão de templates que nos permite tal uso.

Diante disso me vi com a necessidade de encontrar uma alternativa, ao pesquisar a internet achei um desenvolvedor que está mantendo um projeto com base na implementação da SGI do STL, esta implementação conforme seus argumentos tem um consumo de memória muito eficiente, sendo que a outra opção mais próxima tem tem um consumo 70% maior.

Com base na introdução apresentada no site http://www.sgi.com/tech/stl/stl_introduction.html e o trabalho de Andy Brown que adaptou a versão SGI STL para AVR, apresento o inicio do trabalho com uma nova biblioteca e a construção da mesma para uso com o Arduino, já que Andy Brown, sugere que esta biblioteca seja depositada dentro da pasta do core, o que não acredito ser uma boa prática, então estarei adaptando a mesma para uso externo como uma Biblioteca do Arduino.

O texto abaixo é a tradução livre da Introdução ao STL da SGI, e pela explicação sobre o STL da SGI introduz muito bem o que é o STL e seu beneficio, em caso de dúvida no final da página você poderá apresenta-la assim amadureço o texto de forma a amadurecer eventuais pontos que tenha ficado pouco claro.

Introdução à Biblioteca Padrão de Template

A Biblioteca Padrão de Template, ou STL da seu nome em inglês “Standard Template Library”, é uma biblioteca do C++ para classes de containers, algoritmos e iterators; ela prové a maioria dos algoritmos básicos e estruturas de dados para ciência de computador. O STL é uma biblioteca genérica, de forma que seus componentes são fortemente parametrizados: a maioria dos componentes do STL são templates. Você precisa se garantir que entende bem o que são templates no C++ antes de usar STL, para isso, ao menos leia antes o artigo O que é um Template em C++.

Containers e algoritmos

Como muitas bibliotecas de classes, o STL inclue classes de containers: Classe no qual o proposito é conter outro objetos. o STL inclue como vector, list, deque, set, multiset, map, multimap, hash_set, hash_multiset, hash_map e hash_multimap. cada uma destas classes é um template, e pode ser instanciado para conter algum tipo de objeto, você pode, por exemplo, usar um vector<int> da mesma forma que você usa um array no C, exceto que o vetor elimina a necessidade de gerenciamento da memória dinâmica manualmente.

      vector<int> v(3);            // Declare a vector of 3 elements.
      v[0] = 7;
      v[1] = v[0] + 3;
      v[2] = v[0] + v[1];          // v[0] == 7, v[1] == 10, v[2] == 17  

O STL também inclui uma larga coleção de algoritmos que manipulam os dados armazenados em containers, você pode reverter a ordem de elementos em um vetor, por exemplo, usando o algoritmo reverse.

      reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7

Há dois pontos importantes sobre esta chamada ao reverse. Primeiro, ele é uma função global, não é uma função membro de uma classe. Segundo, ele recebe dois argumentos ao invés de um: ele opera sobre uma faixa de elementos, ao invés de um container. Neste caso particular a faixa deve cobrir o container v como um todo.

a razão para isso é que, como outros algoritmos em STL, ele é desacoplado de outras classes containers. Este significa que reverse pode ser usado não apenas com a reversão de elementos em vetores, mas também reverter elementos em listas, e cada elemento em um array em C. O seguinte programa também é valido.

      double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
      reverse(A, A + 6);
      for (int i = 0; i < 6; ++i)
        cout << "A[" << i << "] = " << A[i];

O exemplo usado como faixa, é exatamente como o exemplo que reverte o vetor: o primeiro argumento para reverter é o ponteiro para o inicio da faixa, e o segundo argumento aponta para um elemento após o ultimo elemento da faixa. Esta faixa é denominada como A, A + 6; a assimétrica notação é uma lembrança que os dois pontos são diferentes, que o primeiro é o inicio da faixa e o segundo é um após o fim da faixa.

Iterators

No exemplo de reversão do Array C, o argumento para reversesão claramente do tipo double*. Quais são os argumentos para reversese você está revertendo um vector, ou mesmo um list? Isto é, o que exatamente faz reverse declarar seus argumento como são, e o que exatamente faz v.begin() e v.end() retornar?.

A resposta é que os argumentos para reverse são iterators, que são uma generalização dos ponteiros. Ponteiros são por si mesmo iterators, por isso é que é possível reverter os elementos de um array em C. De forma similar, vector declara um tipo iterator interno e um const_iterator. No exemplo acima, o tipo retornado por v.begin()^ e v.end() é vector<int>::iterator. Há também alguns Iterators, tais como istream_iterator e ostream_iterator, que não são associados a nenhum container.

Iterators são um mecanismo que torna possível desacoplar algoritmos dos containers: algoritmos são templates, e são parametrizados para o tipo do iterator, porém não são restritos a um tipo simples de container. Considere, por exemplo, como escrever um algoritmo que executa uma pesquisa linear através de um faixa. Este é o algoritmo de busca STL.

      template <class InputIterator, class T>
      InputIterator find(InputIterator first, InputIterator last, const T& value) {
          while (first != last && *first != value) ++first;
          return first;
      }

O find espera três argumentos: dois iterators que define a faixa, e um valor para ser pesquisado dentro da faixa. Ele examina cada iterator na faixa [first, last], partindo do início até o fim, e parando quando ele encontra um iterator que aponta para o valor ou quando ele chega ao final da faixa.

first e last são declarados como do tipo InputIterator, e InputIterator é um parâmetro do tipo template. Isto é, não há na verdade algum tipo chamado inputIterator: quando você chama find, o compilador substitui o atual tipo do argumento pelo o tipo formal dos parâmetros InputIterator e T. se os dois primeiros argumentos para o find são do tipo int* e o terceiro é do tipo int, então é como se você tivesse chamado a função:

      int* find(int* first, int* last, const int& value) {
          while (first != last && *first != value) ++first;
          return first;
      }

Conceitos e Modelagem

Uma pergunta muito importante a ser feita sobre qual a função do template, não exatamente sobre algoritmos do STL, é qual o conjunto de tipos que pode ser corretamente substituído para um parâmetro formal do template. Esclarecendo, por exemplo, int*ou double*pode ser substituído por parâmetros formais do tipo InputIterator do find . Igualmente, int ou double não pode: find usa a expressão *first, e o operador de referência do ponteiro não faz sentido para um objeto do tipo int ou do tipo double. A resposta simples, então , é que find define de forma implícita um conjunto de requerimentos nos tipos, e que ele pode ser instanciado com algum tipo que satisfaz estes requisitos. Portanto, o tipo é substituído por InputStream que fornece certos tipos de operações: deve ser possível comparar dois objetos conforme a igualdade de seu tipo, deve ser possível incrementar um objeto deste tipo, deve ser possível fazer referência pelo ponteiro de um objeto do tipo obtido pleo objeto que ele aponta, e assim por diante.

find não é o único algoritmo do STL que tem tal conjunto de requisitos; os argumentos do for_each e do count, e outros algoritmos, devem satisfazer os mesmos requisitos. Estes requisitos são suficientemente importantes para que nos demos então um nome: tais conjuntos de requisitos são chamamos de “Conceito”, e nos chamamos este conceito em particular de Input Iterator porque int* fornece todo as operações que são especificadas pelos requisitos do Input Iterator.

Conceitos não parte da linguagem C++; eles são uma forma de declarar um conceito em um programa, ou declarar que um tipo particular é um modelo de um conceito. Mesmo assim, conceitos são uma parte extremamente importante do STL. Usando conceitos torna possível escrever programas que claramente separam interfaces de implementação: o autor do algoritmo find somente tem de considerar a interface especificada pelo conceito Input Iterator. ao invés de da implementação de cada tipo possível conforme cada conceito. Similarmente, se você deseja usar find, você precisa somente se assegurar que os argumentos que você passa para ele são do modelo Input Iterator. Esta é a razão que find e reverse podem ser usada com lists, vectors, arrays em C, e muitos outros tipos: programando em termos de conceitos, ao invés de termos de tipos específicos torna possível reutilizar o componente de software e então combinar componentes conjuntamente.

Refinamentos

Input Iterator é, de fato, um fraco conceito: isto é, ele impõem alguns requisitos. Um Input Iterator deve suportar um subconjunto da aritmética de ponteiros (ele deve ser possível incrementar um Input Iterator usando o operador ++ prefixado ou pós-fixado), mas não precisa suportar todos os operadores de aritmética de ponteiros. Isto é suficiente para o find, mas alguns outros algoritmos requerem que seus argumentos satisfaça requisitos adicionais. reverse, por exemplo, deve ser apto a decrementar seus argumentos também e incrementa-los; ele usa a expressão --last. Em termos de conceito, nos dizemos que os argumentos do reverse devem ser modelos de um Bidirectional Iterator ao invés de um Input Iterator.

O conceito Bidirectional Iterator é muito similar ao conceito Input Iterator: ele simplesmente impõem alguns requisitos adicionais. Os tipos que são modelos do Bidirectional Iterator são um subconjunto dos tipos que são modelos para o Input Iterator: cada tipo que é um modelo do Bidirectional Iterator é também um modelo do Iterator. int*, por exemplo, é ambo um modelo para Bidirectional Iterator e um modelo para Input Iterator, mas istream_iterator, é somente um modelo de input iterator: ele não atende os requisitos mais rigorosos do Bidirectional Iterator.

Nos descrevemos a relação entre Input Iterator e Bidirectional Iterator dizendo que Bidirectional Iterator é um refinamento de Input Iterator. Refinamentos de conceitos é muito parecido com herança de classes em C++; a principal razão para nós usarmos uma palavra diferente, ao invés de simplesmente dizer que é uma “herança”, é enfatizar que o refinamento se aplica a conceitos ao invés de se aplicar ao tipo em questão.

Há atualmente três outros conceitos de iterator em adição aos dois que nos temos já discutidos aqui: Os cinco iterators são Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, e Random Access Iterator; Forward Iterator é o refinamento do *Input Iterator, **Bidirectional Iterator é um refinamento de Forward Iterator, e Random Access Iterator é um refinamento de Bidirectional Iterator. (Output Iterator é relacionado a outros 4 conceitos, mas ele não é parte da hierarquia de refinamentos: ele não é um refinamento de nenhum dos outros conceitos de iterator, e nenhum dos outros conceitos de iterator são refinamentos dele). Na página Iterator Overview há mais informações sobre iterator em geral.

Classes Containers, como iterators, são organizadas em uma hierarquia de conceitos. Todos os contêineres são modelos de conceitos; Conceitos mais refinados, tais como uma Sequence e um Associative Container, descreve tipos específicos de contêineres.

Outras partes do STL

Se você entendeu algoritmos, iterators e contêineres, então você entendeu práticamente tudo que há para se conhecer sobre STL. O STL, porém, inclui vários outros tipos de componentes.

Primeiro, o STL inclui vários utilitários: conceitos muito básicos e funções que são usadas em diferentes partes da biblioteca. O conceito Assignable, por exemplo, descreve tipos que tem operadores de atribuição e construtores de cópia; na maioria das classes STL são modelos de Assignable, e a maioria dos algoritmos exigem que seus argumentos sejam modelos de Assignable.

Segundo, o STL inclue alguns mecanismos de baixo nível para alocação de desalocação de memória. Allocators são muito especializados, e você pode seguramente ignorar para alguns todos os propósitos.

Finalmente, o STL inclue uma grande coleção de objetos de função, também conhecidos como functors. Exatamente como iterators são generalizações de ponteiros. objetos de função são generalizações de funções: um objeto de função é qualquer coisa que você possa chamar usando um sintaxe ordinária de função. Há vários conceitos diferentes relacionados a objetos de função, incluindo Unary function (um objeto de função que recebe apenas um parâmetro, por exemplo, os que são chamados como f(x)) e Binary Function (um objeto de função que recebe dois argumentos, por exemplo os que são chamados como `f(x, y)). Objetos de função são uma parte importante da programação com genericos (Generic Programming) porque eles são abstrações não apenas sobre tipos de objetos, mas também sobre operações que estão sendo executadas.

Conclusão

Como podem ver o STL traz grandes benefícios ao programador, e quando trabalhamos com coleções de dados e pequenos objetos pode ser muito útil. Há um mito que diz não podemos usar STL em sistemas embarcados e microcontroladores como AVR, veremos no próximo artigo “O Mito que impede o uso de templates em sistemas embarcados”.