====== APÉNDICE A: LA BIBLIOTECA ESTÁNDAR DE PLANTILLAS C++ (STL) ====== 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 (Lists) ===== #include #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 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. #include #include int total_int_list(list* head) {   int total = 0;   list::iterator curr = head->begin();   while (curr!=head->end())   {     total += *curr;     curr++;   }   return total; } void main() {   list 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 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 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 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 se ha implementado como puntero para que corresponda con el puntero utilizado en //total_int_list// de la Figura . En STL, suele ser más natural (y preferible) utilizar referencias en lugar de punteros. Así pues, el parámetro se convierte en //list& head//, y sus funciones miembro se activan con la sintaxis //head.begin();// y así sucesivamente. ===== Correspondencias (Maps) ===== 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). #include #include int total_int_table(map& table) {   int total = 0;   map::iterator curr = table.begin();  while (curr!=table.end())   {     total += (curr->second);     curr++;   } return total; } int main() {   map 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 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 elemento((Técnicamente son cuatro tipos, pero los dos últimos son opcionales. Puesto que nos limitamos a una introducción básica de esta clase STL, omitiremos los detalles sobre estos dos últimos tipos.)). 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 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//, 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.