Standard Template Library parte I

Esta série de artigos pretende apresentar alguns recursos da Biblioteca padrão do C++, a Standard Template Library (STL), que foi definida por volta de 1997. A STL possui contêineres, rotinas de E/S, strings, suporte a computação numérica e muito mais, e utilizá-la traz muitas vantagens. Sendo parte da Biblioteca Padrão, é encontrada em vários compiladores C++ e IDEs existentes, exatamente como a biblioteca padrão do C

Os artigos são destinados àqueles que já têm um conhecimento prévio de C++, e para entender e utilizar eficientemente a STL também é necessário ter um conhecimento prévio de programação genérica (gabaritos/templates), pois a STL é completamente baseada nessa tecnologia. Conheça a seguir algumas de suas principais vantagens e características.

Portabilidade

Por ter sido padronizada, programas utilizando a STL de maneira correta podem ser compilados em uma vasta gama de compiladores e plataformas, tanto comerciais quanto livres.

Desempenho

Cada implementação da STL deve seguir corretamente as definições sobre o desempenho de cada contêiner, algoritmo ou função. Essas definições de desempenho foram criadas por comitê, como, por exemplo, que o tempo necessário para acessar um elemento randômico em um vetor deve ser constante, independentemente do tamanho do vetor, assim como adicionar um novo elemento ao final do mesmo, mas inserir um elemento ao início de um vetor consome um tempo linearmente proporcional ao número de elementos já contidos nele.

Com essas definições, um programador terá certeza de que utilizar uma certa função em um contêiner vai sempre funcionar da maneira esperada, independente da implementação. Claro que uma implementação pode ser mais rápida que outra, mas deve sempre seguir as definições de desempenho para cada operação, evitando surpresas.

Suporte

Como a STL é padronizada, um programador que utilize uma implementação X da STL pode facilmente dar suporte a um programador da implementação Y, assim, qualquer lista ou fórum pode fornecer suporte a várias implementações. Os newsgroups comp.lang.c++ e comp.lang.c++.moderated são bons lugares para se tirar dúvidas a respeito da STL.

Variedade

Existem inúmeras implementações da STL, tanto comerciais quanto livres, vários compiladores C++ vêm com o suporte à STL incluídos, e é possível utilizar uma implementação de outro fabricante com o seu compilador.

Facilidade de uso

A STL foi criada com a finalidade de ser facilmente utilizada. De nada adiantaria se a biblioteca fosse complicada ou se dependesse de muitas linhas de código para inicializar um vetor. Para se criar um vetor de inteiros e uma string basta declarar:

std::vector int_array;
std::string nome;

O std:: serve para informar ao compilador que o tipo vetor se encontra no namespace std, assim como todas as funções e classes da biblioteca padrão. Caso haja alguma outra biblioteca que tenha definido uma classe vector, a mesma não causará problemas de ambigüidade no programa que utilize essa biblioteca e a biblioteca padrão.

Flexibilidade

Muitas vezes, é necessário criar um vetor ou lista em uma memória específica ou mesmo compartilhada, ou utilizar uma string com caracteres do tipo wchar_t em vez do char. A STL também foi criada com o intuito de, além de ser fácil de ser utilizada, ser fácil de ser extendida ou configurada para usos específicos.

A classe vector, por exemplo, é declarada da seguinte maneira:

template  > class vector

Ao definir um vetor como o int_array acima, está sendo utilizado o alocador padrão da STL para o tipo int, mas pode-se criar uma classe alocadora que funcione com memória compartilhada e assim definir o vetor que utilize memória compartilhada:

class mem_comp_alloc { ... };
std::vector int_array_comp;

As definições entre os caracteres < e > são os parâmetros de gabarito, e definem que a classe vector aceita dois "tipos" como parâmetros, sendo o primeiro do tipo _Tp que pode ser desde um int até qualquer tipo ou classe definidos pelo usuário. O segundo parâmetro é do tipo _Alloc que tem como valor default std::allocator<_Tp>, ou seja, uma classe alocadora que aceita como parâmetro o mesmo tipo que foi informado para o vector.

O tipo _Alloc, embora não seja definido na definição da classe vector, deve ter funções membros, typedefs e propriedades de uma classe allocator, ou o programa não irá compilar, gerando um erro de compilação dentro dos cabeçalhos de inclusão da STL.

Já a classe std::string na verdade é um typedef para std::basic_string, std::allocator>, assim como std::wstring é um typedef para uma classe basic_string do tipo wchar_t.  Ou seja, o gabarito std::basic_string aceita  três parâmetros: um tipo qualquer para armazenamento de caracteres (char, unsigned char, wchar_t, etc.), um char traits, que define as operações sobre o tipo/classe de caracteres informado, e um alocador para o tipo informado. O typedef para std::string cria uma basic_string que utiliza o tipo char como tipo de armazenamento de caractere, com uma classe que define as operações sobre o tipo char, e um alocador para o tipo char, economizando um certo trabalho de digitação.

Portanto, a classe basic_string pode ser parametrizada em termos de tipo de caractere, de char traits, que define as operações sobre um tipo/classe de caracteres e um alocador. Sendo a STL completamente flexível, a gama de utilização para a mesma é infindável.

Contêineres padrões

A STL possui os seguintes contêineres padrões: vector, list, string, deque, set, multiset, map e multimap; e os tipos que não são contêineres.: bitset, valarray, stack, queue e priority_queue.

Algumas implementações também definem os contêineres não-padrão: rope, slist, hash_set, hash_multiset, hash_map e hash_multimap. Se portabilidade for importante, é melhor ficar longe destes contêineres, pois pode haver diferenças entre um hash_map da implementação A e da implementação B.

Escrever sobre a STL pode levar a mais de um livro inteiro O livro The C++ Standard Library: A Tutorial and Reference de Nicolai M. Josuttis, Addison-Wesley e The C++ Programming Language (3ª edição), de Bjorne Stroustrup, dedica mais de quatro capítulos para falar da STL, o restante é sobre a linguagem C++ atualizada. Discutimos neste artigo a classe vector. Para outros artigos serão discutidas as classes string, map, list e etc.

std::vector

Quando é necessário escrever um programa que leia alguns inteiros fornecidos pelo usuário, ordená-los e mostrar ao usuário o resultado, o seguinte programa normalmente é escrito:

#define MAX_NUMEROS 1024;
int nums[MAX_NUMEROS];
int a;
int i=0;

for(;;) {
        if( !(a = lenumero() ) ) break;
        nums[i++] = a;
}
sortnumeros( nums, i-1 );
// provavelmente usando qsort ou algum algoritmo
// criado pelo próprio desenvolvedor

mostranumeros( nums, i-1 );
// algum loop enviando os números para o console

Existem alguns problemas neste programa:

std::vector nums;
nums.reserve(512);
int a;

for(;;) {
        if( !(a = lenumero() ) ) break;
        nums.push_back(a);
}
std::sort (nums.begin(), nums.end() );
mostranumeros( nums );
// pode utilizar ostream_iterator ou std::for_each