5.2.1 Una primera implementación

Vamos a hacer una primera implmentación que no tendrá en cuenta cuando se agota la memoría.

/*

arreglo.h

Autor: L. Alejandro Bernal R.

Fecha: 2000.12.02

Descripción: Implementa el concepto de un arreglo variable.

*/

#ifndef _ARREGLO_H_

#define _ARREGLO_H_

#include <stdlib.h>

/*

TDA Arreglo 

    Descripción: Un arreglo es una secuencia de elementos de tamaño variable.

    Invariante: Arreglo=<elem[0],...,elem[n-1]> y (Para todo i,0 <= i<n,elem[i] pertenece a TipoB)

*/

template<class TipoB> class Arreglo

{

    private:

    // Atributos:

    TipoB *elem; // Arreglo de elementos.

    int num; // Número actual de elementos.

    public:

    // Operaciones:

    /*

    Operación Arreglo 

        Descripción: Crea un arreglo vacio.  

        Descripción operacional: Arreglo: -> Arreglo

        Precondición: verdadero 

        Poscondición: Arreglo=<>

    */

    Arreglo() { elem = NULL; num= 0; }

    /*

    Operación Arreglo

        Descripción: Crea un arreglo basado en un arreglo fuente.

        Descripción operacional: Arreglo: Arreglo -> Arreglo

        Precondición: fuente pertenece a Arreglo

        Poscondición: Para todo i, 0 <= i < n, elem[i] = fuente.elem[i]

    */

    Arreglo(Arreglo<TipoB> &fuente);

    /*

    Operación: Arreglo

        Descripción: Libera el espacio ocupado por el arreglo.

        Descripción operacional: Arreglo: Arreglo ->

        Precondición:

        Poscondición:

    */

    Arreglo() { delete elem; }

    /*

    Operación =

        Descripción: Asigna (copia) la información del arreglo fuente.

        Descripción operacional: =: Arreglo x Arreglo -> Arreglo

        Precondición: fuente pertenece a Arreglo

        Poscondición: Para todo i, 0<= i < n, elem[i] =fuente.elem[i]

    */

    Arreglo &operator =(Arreglo<TipoB> fuente);

    /*

    Operación [] 

        Descripción: Retorna una referencia a un elemento del arreglo.

        Descripción operacional: []: Arreglo x N -> TipoB 

        Precondición: i pertenece a N 

        Poscondición: []=elem[i] 

    */

    TipoB &operator [](int i);

    /*

    Operación tam

        Descripción: Retorna el tamaño del arreglo.

        Descripción operacional: tam: Arreglo -> N

        Precondición:

        Poscondición: tam=n

     */

     int tam() { return num; }

}; // template <class TipoB> class Arreglo

/*

Operación Arreglo

    Descripción: Crea un arreglo basado en un arreglo fuente.

    Descripción operacional: Arreglo: Arreglo -> Arreglo

    Precondición: fuente pertenece a Arreglo

    Poscondición: Para todo i, 0 <= i < n, elem[i] = fuente.elem[i]

*/

template<class TipoB> Arreglo<TipoB>::Arreglo(Arreglo<TipoB> &fuente)

{

    num = fuente.num;

    elem = new TipoB[num];

    for(int i = 0; i < num; i++){

        elem[i] = fuente.elem[i];

    }

}

/*

Operación =

    Descripción: Asigna (copia) la información del arreglo fuente.

    Descripción operacional: =: Arreglo x Arreglo -> Arreglo

    Precondición: fuente pertenece a Arreglo

    Poscondición: Para todo i, 0<= i < n, elem[i] =fuente.elem[i]

*/

template<class TipoB> Arreglo<TipoB> &Arreglo<TipoB>::operator =(Arreglo<TipoB> fuente)

{

    delete elem;

    num = fuente.num;

    elem = new TipoB[num];

    for(int i = 0; i < num; i++){

        elem[i] = fuente.elem[i];

    }

}

/*

Operación []

    Descripción: Retorna una referencia a un elemento del arreglo.

    Descripción operacional: []: Arreglo x N -> TipoB

    Precondición: i pertenece a N

    Poscondición: []=elem[i]

*/

template<class TipoB> TipoB &Arreglo<TipoB>::operator [](int i)

{

    if(i < num){

        return elem[i];

    }

    // Crear un nuevo arreglo con el espacio suficiente.

    TipoB *nuevo = new TipoB[i + 1];

    // Pasar los elementos al nuevo arreglo.

    for(int j = 0; j < num; j++){

        nuevo[j] = elem[j];

    }

    delete elem;

    elem = nuevo;

    num = i + 1;

    return elem[i];

} // TipoB &Arreglo::operator [](int i)

#endif

//--- Fin de arreglo.h

En este programa se han presentan varias caraterísticas del C++ que no se habian usado. Por ejemplo la función destructora:

/*

    Operación: Arreglo

        Descripción: Libera el espacio ocupado por el arreglo.

        Descripción operacional: Arreglo: Arreglo ->

        Precondición:

        Poscondición:

*/

Arreglo() { delete elem; }

Esta función, como ya dijimos en el diseño, se usa en el momento de destruir una instancia del TDA. Se llama automáticamente la instancia deja de existir y en nuestro caso se utiliza para liberar la memoria dinámica ocupada por el arreglo.

Hay dos operaciones que no estaban en el diseño original. La primera es un constructor que se basa en otro arreglo y la segunda una sobrecarga del operador de asignación:

/*

Operación Arreglo

    Descripción: Crea un arreglo basado en un arreglo fuente.

    Descripción operacional: Arreglo: Arreglo -> Arreglo

    Precondición: fuente pertenece a Arreglo

    Poscondición: Para todo i, 0 <= i < n, elem[i] = fuente.elem[i]

*/

Arreglo(Arreglo<TipoB> &fuente);

/*

Operación =

    Descripción: Asigna (copia) la información del arreglo fuente.

    Descripción operacional: =: Arreglo x Arreglo -> Arreglo

    Precondición: fuente pertenece a Arreglo

    Poscondición: Para todo i, 0<= i < n, elem[i] =fuente.elem[i]

*/

Arreglo &operator =(Arreglo<TipoB> fuente);

Pra entender esto es necesario recordar que cuando se inicializa un Arreglo se utiliza el constructor y cuando se asigna un arreglo a otro se utiliza el operador de asignación. La acción por defecto del C++, en estas dos operaciones, es copiar atributo por atributo en el arreglo destino, igual con el apuntador elem, y como este es un apuntador copia la dirección de memoria y no el erreglo en si. Como resultado tenemos dos arreglos que comparten la misma región de memoria como se ve en la figura .

Figure: Resultado de usar la operación de asignación por defecto.

Y esto trae muchos problemas, por ejemplo, cuando se llama la operación destructora se intenta liberar dos veces la misma región de memoria. Por ello es necesario hacer que esta región de memoria sea copiada, para ello definimos una nueva función constructora y sobrecargamos el operador de asignación.

Siempre que en los atributos se defina un apuntador a una región de memoria dinámica se debe declarar un constructor de clase que tiene como parámetro otro objeto de la misma clase y se debe sobrecargar el operador de asignación. Estas dos operaciones deben copiar la región de memoria.

También con respecto a estos operadores, no es necesario escribirlos en el diseño, por que, ellos están resolviendo un problema de implementación y no de diseño, pero si es necesario documentarlos adecuadamente en el código.

Otra nueva característica se puede ver en el siguiente código es:

/*

    Operación [] 

        Descripción: Retorna una referencia a un elemento del arreglo.

        Descripción operacional: []: Arreglo x N -> TipoB 

        Precondición: i pertenece a N 

        Poscondición: []=elem[i] 

    */

    TipoB &operator [](int i);

En este código se está definiendo lo que en C++ se llama un operador, no hay que confundir este concepto con el de operación de TDA. Los operadores en C++ son funciones que no tienen un identificador de letras si no que sobrecargan los operadores del lenguaje, por ejemplo aquí estamos sobrecargando el operador [] que se usa para los arreglos de C++, precisamente por que nuestro TDA Arreglo está extendiendo este concepto.

Otra característica sobre la que hay que llamar la atención es que la implementación de la operación [] se hace en el archivo de interfaz del TDA. Esto es asi por que se está implementado el TDA Arreglo como una plantilla, no como una clase y se necesita la plantilla del operador para definir una instancia particular.

Finalmente el uso de referencias, el & antes de la palabra operador, es vital para que nuestro arreglo se comporte los más parecido posible a los arreglos nativos de C++. Cuando una función retorna una referencia, no retorna el valor de la variable si no una referencia a él. Mediante esta referencia podemos modificar el contenido de la variable.

Para aclarar un poco más veamos el siguiente código que utiliza el TDA Arreglo:

/*

arreglo_prueba.cpp

Autor: L. Alejandro Bernal R.

Fecha: 200.12.02

Descripción: Prueba del TDA arreglo.

*/

#include "arreglo.h"

#include <iostream.h>

int main(void)

{

    Arreglo<int> arr;

    arr[10] = 67;

    cout << "arr.tam=" << arr.tam() << " arr[10]=" << arr[10] << '\n';

    arr[2] = 3;

    cout << "arr.tam=" << arr.tam() << " arr[2]=" << arr[2] << '\n';

    arr[20] = 345;

    cout << "arr.tam=" << arr.tam() << " arr[20]=" << arr[20] << '\n';

     Arreglo<int> arr2 = arr;

     cout << "arr2.tam=" << arr2.tam() << " arr2[10]=" << arr[10] << '\n';

     cout << "arr2.tam=" << arr2.tam() << " arr2[2]=" << arr[2] << '\n';

     cout << "arr2.tam=" << arr2.tam() << " arr2[20]=" << arr[20] << '\n';

     Arreglo<int> arr3;

     arr3 = arr;

     cout << "arr3.tam=" << arr3.tam() << " arr3[10]=" << arr[10] << '\n';

     cout << "arr3.tam=" << arr3.tam() << " arr3[2]=" << arr[2] << '\n';

     cout << "arr3.tam=" << arr3.tam() << " arr3[20]=" << arr[20] << '\n';

     return 0;

}

//---- Fin arreglo_prueba.cpp

En el código se a utilizado Arreglo para definir un arreglo de enteros llamado arr, esa acción corresponde a la sentancia:

Arreglo<int> arr;

Esta toma la plantilla Arreglo y crear un arreglo de enteros, en detalle: Crea una clase que tiene un apuntador elem a un arreglo de enteros. Además, reescribe las operaciones con el tipo int. Las funciones que están implementadas dentro de la clase se instancian como funciones en línea y las que están por fuera como funciones normales. Esto quiere decir que las plantillas no generan código objeto sino hasta el momento en que se declara un objeto con un tipo específico, en nuestro ejemplo arr.

En la siguiente parte del código todo parece comportarse com en un arreglo nativo, pero hay que recordar que cuando se hace algo como:

arr[10] = 67;

Se está invocando el operador que sobrecarmos y no el operador original del C++. Más adelante tenemos las sentencia:

Arreglo<int> arr2 = arr;

Esta declara un arr2 de enteros e inicializa, no asigna, el arreglo con los valores de arr, esto quiere decir que aquí se está usando el constructor y no el operador de asignación.

Por su parte en las sentencias:

Arreglo<int> arr3;

arr3 = arr;

si se está usando el operador de asignación. Es importante diferenciar esto:

Cuando en una declaración aparece el = este no se refiere a una signación, sino a una inicialización y por esto se llama a un constructor para hacer la copia y no al operador de asignación.

Finalmente, es de resaltar que este arreglo se usa de la misma forma que los arreglos nativos de C++, gracias a la sobrecarga de operadores.

La sobrecarga de operadores, cuando está bien usada, permite definir una interfaz más natural en las implementaciones de TDAs.

Pero es importante no abusar de la sobrecarga de operadores, por ejemplo si se sobrecarga el operador + para una operación que imprime^5.1 lo que origina es más bien confución y no una interfaz bien construida.

Footnotes

... imprime^5.1

Esto es lo que pasa con el operador <<, el significado original de este es un corrimiento de bits a la izquierda y pero en la librería estádar de C++ (particularmente la iostream) sobrecarga ese operador para imprimir, lo que origina mucha confución, en especial cuando se está iniciando el aprendizaje de C++.