Table of Contents
APÉNDICE A: LA BIBLIOTECA ESTÁNDAR DE PLANTILLAS C++ (<i>STL</i>)
La Biblioteca Estándar de Plantillas (Standard Template Library - STL) es una biblioteca de código C++ de amplia difusión concebida por Silicon Graphics ( www.sgi.com ). En el presente Apéndice se presenta un breve resumen de sus principales funciones, que se utilizan a todo lo largo del código Greenstone. Para una explicación más completa, consulte el manual oficial de referencia STL disponible en la siguiente dirección Internet: www.sgi.com , o alguno de los numerosos libros sobre STL, como el de Josuttis (1999).
Tal como lo sugiere el término “plantilla”, STL no es sólo una biblioteca de objetos lista para usar. Unida al mecanismo de plantillas de C++, proporciona a los programadores una solución para desarrollar de manera concisa sus propios objetos, recurriendo a las funciones algorítmicas de STL. Esto añade un grado más de complejidad pero vale la pena.
A fin de ayudar a comprender los extractos del código de Greenstone que figuran en el presente manual, citaremos algunos ejemplos didácticos de utilización de la STL.
Listas (<i>Lists</i>)
<imgcaption figure_programming_a_list_of_integers|%!– id:1214 –%Programación de una lista de números enteros %!– withLineNumber –%></imgcaption>
#include <iostream.h>
#define nil 0
struct intlist {
int val;
struct intlist* next;
};
int total_int_list(intlist* head)
{
int total = 0;
intlist* curr = head;
while (curr!=nil)
{
total += curr->val;
curr = curr->next;
}
return total;
}
void main()
{
intlist node1 = { 5, nil };
intlist node2 = { 4, nil };
node2.next = &node1;
int total = total_int_list(&node2);
cout << "Total de los objetos: " << total << endl;
}
En primer lugar, estudiaremos dos programas que implementan una lista de números enteros. Uno de ellos utiliza tipos C++ básicas (la “manera tradicional de proceder”), mientras que el otro utiliza STL. En la Figura <imgref figure_programming_a_list_of_integers> se muestra la implementación del código fuente que no utiliza STL. Las líneas 5-8 definen la estructura de datos básica que vamos a utilizar: en el campo val se almacena el valor del número entero, y next indica el siguiente elemento de la lista. Como puede advertirse se trata, en suma, de una implementación clásica de una lista enlazada.
Para ilustrar la utilización de la estructura de datos, el programa principal (líneas 23-32) inicializa una lista de números enteros con los elementos [5, 4]. Luego activa la función total_int_list (definida en las líneas 10-21), que tiene como único parámetro un puntero dirigido hacia el principio de una lista y que suma los valores que ésta contiene. El valor que devuelve (9 en nuestro ejemplo) aparece en la pantalla.
Las líneas 12-18 llevan a cabo las tareas principales. Se comienza por un poco de inicialización: la variable local total se fija en cero, y curr apunta hacia el principio de la lista. A continuación, un bucle while agrega el elemento de número entero actual al subtotal vigente (total += curr→val;) antes de pasar al siguiente elemento (curr = curr→next;). El bucle while termina cuando curr equivale a nil (nada), lo que significa que no queda ningún elemento por tratar.
<imgcaption figure_programming_a_list_of_integers_using_stl|%!– id:1218 –%Programación de una lista de números enteros mediante la STL ></imgcaption>
#include <iostream.h>
#include <list>
int total_int_list(list<int>* head)
{
int total = 0;
list<int>::iterator curr = head->begin();
while (curr!=head->end())
{
total += *curr;
curr++;
}
return total;
}
void main()
{
list<int> vals;
vals.push_back(5);
vals.push_back(4);
int total = total_int_list(&vals);
cout << "Total de los objetos: " << total << endl;
}
En la Figura <imgref figure_programming_a_list_of_integers_using_stl> se muestra un programa equivalente que utiliza STL. Ya no es necesario definir una estructura de datos adecuada en el código, sino que basta con la directiva #include <list> de la línea 2 que contiene la plantilla para la lista definida en STL. El objeto se denomina “clase Contenedor” ya que cuando se declara una variable de este tipo se especifica también el tipo que se desea que almacene. En la línea 19 se elabora una lista de números enteros con la instrucción list<int> vals;. Se pueden agregar elementos al objeto mediante la función miembro push_back (), como se hace en las líneas 20-21.
Las líneas 6-12 efectúan el trabajo principal. Sigue habiendo dos inicializaciones y un bucle while, pero por lo demás la nueva sintaxis tiene poco en común con la antigua. En esta nueva forma de tratamiento es fundamental una variable de tipo iterator (línea 7). Numerosas clases STL incluyen tipos iterator para ofrecer una manera uniforme de recorrer una secuencia de objetos de contenedor. El primer elemento se devuelve con begin() y el elemento que sigue al último elemento se devuelve con end(). Se pasa al elemento siguiente mediante la operación de incremento ++, que es sobrecargada por la clase iterator para implementar esta tarea, y se accede al valor almacenado mediante una operación de derreferenciación ( *curr en la línea 10) también sobrecargada.
La implementación STL de este programa es un poco más concisa que el código convencional (25 líneas, en lugar de 31). Las ventajas son más importantes en proyectos más voluminosos, ya que el objeto list de STL tiene un potencial mayor de lo que muestra el ejemplo. Este objeto incluye, por ejemplo, una lista doblemente enlazada que admite diversas formas de inserción y supresión. Se requerirían tareas de programación suplementarias para integrar estas funciones en la versión de lista de números enteros básica.
Obsérvese que el parámetro total_int_list de la Figura <imgref figure_programming_a_list_of_integers_using_stl> se ha implementado como puntero para que corresponda con el puntero utilizado en total_int_list de la Figura <imgref figure_programming_a_list_of_integers>. En STL, suele ser más natural (y preferible) utilizar referencias en lugar de punteros. Así pues, el parámetro se convierte en list<int>& head, y sus funciones miembro se activan con la sintaxis head.begin(); y así sucesivamente.
Correspondencias (<i>Maps</i>)
Cuando se implementa un sistema de biblioteca digital, es útil poder almacenar elementos en una matriz indizada por secuencias de texto en lugar de números. En Greenstone, por ejemplo, esto simplifica considerablemente el almacenamiento de los archivos de macros después de su lectura; lo mismo ocurre con los diversos archivos de configuración. El tipo de datos que permite esta clase de acceso se denomina matriz asociativa y suele encontrarse en los lenguajes de programación modernos de alto nivel. Se lo conoce también con el nombre de “ hash array ” (matriz de desmenuzamiento, sobre todo en Perl) ya que la técnica habitual utilizada para implementar los índices de texto es el desmenuzamiento (eso es, calcular una suma de control).
<imgcaption figure_using_associative_arrays_in_stl|%!– id:1225 –%Utilización de matrices asociativas en STL %!– withLineNumber –%></imgcaption>
#include <iostream.h>
#include <map>
int total_int_table(map<char*, int>& table)
{
int total = 0;
map<char*, int>::iterator curr = table.begin();
while (curr!=table.end())
{
total += (curr->second);
curr++;
}
return total;
}
int main()
{
map<char*, int> table;
table["Alicia"] = 31;
table["Pedro"] = 24;
table["Maria"] = 47;
int total = total_int_table(table);
cout << "Edad total: " << total << endl;
}
En STL, las matrices asociativas se constituyen mediante el objeto map (correspondencia). En la Figura <imgref figure_using_associative_arrays_in_stl> se presenta un ejemplo un tanto artificial que almacena la edad de tres personas (Alicia, Pedro y Maria) en una matriz asociativa indizada con sus nombres (líneas 19-22). El problema es escribir una función que calcule la edad total de todas las personas presentes, sin saber ni cuántas ni quiénes son. Por supuesto, se podría resolver este problema con una matriz clásica de números enteros indizados numéricamente. Este ejemplo está concebido para ilustrar las funciones del objeto map y poner de manifiesto las semejanzas de tratamiento con el objeto list acompañado de un iterator.
Al igual que list, map es una clase de contenedor. Sin embargo, cuando se declara una variable de este tipo, es preciso especificar dos cosas: el tipo de índice y el tipo de elemento1). Como se puede apreciar en la línea 19, se obtiene una matriz asociativa que almacena números enteros indizados por cadenas utilizando char* (que es la manera de declarar una cadena en C++) como tipo de índice, seguido de int como tipo de elemento.
Existen diversas maneras de almacenar elementos en la matriz asociativa. En las líneas 20-22 del ejemplo se utiliza el índice de la matriz sobrecargada [ ] para inicializar el cuadro con la edad de las tres personas. La semejanza entre total_int_table, que efectúa el cálculo principal en el programa, y total_int_list en la Figura <imgref figure_programming_a_list_of_integers> es notable. De hecho, estos dos objetos son casi idénticos y no es una coincidencia. STL recurre en gran medida a la herencia, de tal modo que objetos diferentes utilizan las mismas operaciones fundamentales. Así ocurre sobre todo con los iterators. Las pequeñas diferencias entre las dos funciones consisten en que el iterator procede aquí de map<char*, int>, y que el acceso a sus elementos se hace con la instrucción curr→second(); en efecto, la derreferenciación de la variable (*curr) está definida para devolver un objeto de tipo pair. Esta operación registra el nombre del índice ( first) y el valor del elemento ( second), pero sólo nos interesa este último. Por lo demás, el código permanece igual. La única diferencia que persiste –el cambio del único argumento de la función de puntero a referencia– es superficial.
El código de Greenstone utiliza ampliamente otros dos tipos STL: vector (vector) y set (conjunto). El primero facilita las matrices dinámicas y el segundo admite las operaciones matemáticas de conjunto como la unión, la intersección y la diferencia.