Introdução à STL e templates em C++

Templates em C++

class Stack {
	public:
		Stack(int size) {
			stack = new int[size];
			msize = size;
			ptr = 0;
		}
		
		~Stack() {
			delete[] stack;
		}

		int size() {
			return ptr;
		}

		void push(int i) {
			if (ptr < msize)
				stack[ptr++] = i;
			else
				// whatever
		}

		int top() {
			if (ptr > 0)
				return stack[ptr-1];
			else
				// whatever
		}

		void pop() {
			if (ptr > 0)
				ptr--;
			else
				// hm, whatever
		}

	private:
		int ptr;
		int msize;
		int *stack;
};

Claro que posso copiar o código todo e alterar int para double. E se quiser os 2 ao mesmo tempo? E se depois quiser um stack de objectos de uma classe qualquer que ainda nem sei qual é? Já se vê o problema: esta implementação não é genérica, ou seja, não pode ser usada com qualquer tipo de dados. Os Templates resolvem este problema. Antes de explicar, aqui está o código do mesmo stack mas agora genérico, ou seja, um stack que pode ser de um tipo qualquer:

template<class Type>
class Stack {
	public:
		Stack(int size) {
			stack = new Type[size];
			msize = size;
			ptr = 0;
		}
		
		~Stack() {
			delete[] stack;
		}

		int size() {
			return ptr;
		}

		void push(const Type &t) {
			if (ptr < msize)
				stack[ptr++] = t;
			else
				// whatever
		}

		Type top() {
			if (ptr > 0)
				return stack[ptr-1];
			else
				// whatever
		}

		void pop() {
			if (ptr > 0)
				ptr--;
			else
				// hm, whatever
		}

	private:
		int ptr;
		int msize;
		Type *stack;
};

template
Type Stack::top()
{
	if (ptr > 0)
		return stack[ptr-1];
	else
		// whatever
}

int main()
{
	Stack<int> pilha(10);
	Stack<double> pilhaReal(10); // ai
	
	pilha.push(2);
	pilhaReal.push(3.14);

	cout << pilha.top() << "\n";

	pilhaReal.pop();

	return 0;
}

A STL inclui várias classes que implementam várias estruturas de dados como stacks, queues, vectors, maps, etc e algoritmos para operar sobre elas. Como o nome indica, as classes da STL são definidas com templates para poderem conter qualquer tipo de dados.

Introdução à STL: vector e map

#include <vector>

using std::vector;

int main()
{
	vector<int> v;

	v.push_back(4);
	v.push_back(2);
	v.push_back(3);
	v[0] = 1;

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}
	
	return 0;
}

O vector inclui outros métodos úteis que podem consultar na referência. Outro container útil é o map. O map associa uma chave a um item. Para definir um objecto do tipo map, é preciso especificar 2 tipos, o da chave e o dos items. Por exemplo, um vector<int> pode ser considerado um map com chaves do tipo int e items do tipo int também. Um vector<string> é como um map com chaves tipo int e items tipo string. Uma diferença crucial é que no map podemos ter como único elemento, por exemplo, mapa[666] = "buedabad"; enquanto que no vector, para isso temos de ter todos os elementos até 666. Bem, algum código para ver como funciona:

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
	map<string, int> digitos;
	string s;

	digitos["zero"] = 0;
	digitos["um"] = 1;
	digitos["dois"] = 2;
	digitos["três"] = 3;
	digitos["quatro"] = 4;
	digitos["cinco"] = 5;
	digitos["seis"] = 6;
	digitos["sete"] = 7;
	digitos["oito"] = 8;
	digitos["nove"] = 9;

	while (cin >> s) {
		cout << digitos[s] << endl;
	}
	
	return 0;
}

A saída será:
6
9

Acho que dá para perceber como funcionam os maps :) Para poder introduzir outras funcionalidades da STL, temos de falar primeiros de iterators

Iterators

for (i = 0; i < size; i++) {
	frobnicate(array[i]);
}

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
	map<string, int> digitos;
	map<string, int>::iterator iter; // o nosso iterator
	string s;

	digitos["zero"] = 0;
	digitos["um"] = 1;
	digitos["dois"] = 2;
	digitos["três"] = 3;
	digitos["quatro"] = 4;
	digitos["cinco"] = 5;
	digitos["seis"] = 6;
	digitos["sete"] = 7;
	digitos["oito"] = 8;
	digitos["nove"] = 9;
	
	for (iter = digitos.begin(); iter != digitos.end(); iter++) {
		cout << iter->first << " = " << iter->second << endl;
	}

	return 0;
}

A ordem não é aleatória: estão ordenados por ordem alfabética, ou seja, por ordem crescente das chaves. Para definir um iterator sobre um map<string, int> fazemos map<string, int>::iterator i;. Este iterator só pode ser usado sobre objectos do tipo map<string, int>; não pode ser usado para iterar sobre, por exemplo, um vector<int> nem sobre um map<int, int>.

O método digitos.begin() retorna um iterator para o início do mapa; o digitos.end() retorna um iterator para um elemento após o último do mapa. O iterator devolvido pelo digitos.end() nunca é válido, serve só para saber quando chegámos ao fim ou para saber se tentámos aceder a um elemento não existente; por exemplo, para verificar se uma dada string existe num mapa:

if (digitos.find("onze") == digitos.end()) {
	// não existe!
} else {
	// existe!
}

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
	int n;
	vector<int> v;
	
	cout << "0 para parar:\n";
	while (cin >> n) {
		if (n == 0)
			break;
		v.push_back(n);
	}

	sort(v.begin(), v.end());

	for (vector<int>::iterator iter = v.begin(); iter != v.end(); iter++) {
		cout << *iter << endl;
	}

	return 0;
}

Isto foi só uma introdução para poder usar o vector e o map mas dá para fazer mais coisas com eles. Também existem classes úteis como a queue, set, list, e outras. Para saber o que há para saber sobre a STL o melhor sítio a consultar é a referência da SGI. Podem começar aqui.

Em caso de haver alguma incorrecção por aqui ou precisarem de algum esclarecimento, mandem um mail: a28123@alunos.det.ua.pt