10 La Lista - Estudio de un Caso

 

Peter Müller
Globewide Network Academy (GNA)
pmueller@uu-gna.mit.edu

10.1 Tipos Genéricos (Plantillas)

  En C++ los tipos de datos genéricos son llamados plantillas de clase o simplemente plantillas (templates) para abreviar. Una plantilla de clase se parece a la definición de una clase normal, en la que algunos aspectos son representados por placeholders (sustitutos). En el ejemplo de la lista por venir, usamos este mecanismo para generar listas de diversos tipos de datos :

  template <class T>
  class List : ... {
  public:
    ...
    void append(const T data);
    ...
  };

En la primera línea introducimos la palabra clave template con la cuál se inician todas las declaraciones de plantillas. Los argumentos de una plantilla se encierran en corchetes angulares.

Cada argumento especifica un placeholder (sustituto) en la siguiente definición de clase. En nuestro ejemplo, queremos que la clase List sea definida para diversos tipos de datos. Uno podría decir, que queremos definir una clase de listas. En este caso, la clase de listas está definida por el tipo de objetos que contienen. Usamos el nombre T como sustituto. Ahora, nosotros usamos T en todos los lugares donde normalmente se espera encontrar el tipo de los objetos reales. Por ejemplo, cada lista provee un método para añadir un elemento a sí misma. Nosotros ahora podemos definir este método tal como se muestra arriba utilizando T.

En la práctica, la definición de la lista ahora debe especificar el tipo de la lista. Si nos apegamos a la expresión de la clase usada anteriormente, tenemos que crear una instancia de clase. De esta instancia de clase, podemos entonces crear instancias de objetos "reales" :

  List<int> integerList;

Creamos aquí una instancia de clase de una List, la cuál lleva integers como sus elementos de datos. Nosotros especificamos el tipo encerrándolo en corchetes angulares. El compilador aplica ahora el argumento "int" provisto y automáticamente genera una definición de clase donde el sustituto T es reemplazado por int, por ejemplo, genera la siguiente declaración de método para append():

  void append(const int data);

Las plantillas pueden llevar más de un argumento para proveer más sustitutos. Por ejemplo, para declarar una clase diccionario que provea acceso a sus elementos de datos por medio de una clave, uno puede pensar en la siguiente declaración :

  template <class K, class T> 
  class Dictionary {
    ...
  public:
    ...
    K getKey(const T from);
    T getData(const K key);
    ...
  };

Usamos aquí dos sustitutos para poder usar diccionarios con varias claves y tipos de datos.

Los argumentos de plantillas pueden usarse también para generar definiciones de clase parametrizadas. Por ejemplo, una pila podría ser implementada por un arreglo de elementos de datos. El tamaño del arreglo podría ser especificado dinámicamente :

  template <class T, int size>
  class Stack {
    T _store[size];

  public:
    ...
  };

  Stack<int,128> mystack;

En este ejemplo, mystack es una pila de integers utilizando un arreglo de 128 elementos. Sin embargo, no usaremos en lo siguiente clases parametrizadas.

10.2 "Formas" de Datos y Recorrido

  En la siguiente discusión distinguimos entre una "forma" de estructura de datos y sus estrategias de recorrido. Lo primero, es la "apariencia", la cuál ya provee mucha información acerca de los bloques de construcción de la estructura de datos.

Una estrategia de recorrido define el orden en el cuál los elementos de la estructura de datos serán visitados. Tiene sentido el separar la forma, de las estrategias de recorrido, debido a que las estructuras de datos pueden ser recorridas usando estrategias muy diversas.

El recorrido de una estructura de datos es implementado usando iteradores. Los iteradores garantizan la visita a cada ítem de su estructura de datos asociada en un orden bien definido. Deben proveer al menos las siguientes propiedades :

1.

Elemento actual. El iterador visita los elementos de datos uno a la vez. El elemento que se visita actualmente es llamado el "elemento actual" ("current element").

2.

Función sucesor. La ejecución del paso al siguiente elemento de datos depende de la estrategia de recorrido implementada por el iterador. La función sucesor se usa para regresar el elemento que será visitado en seguida : Regresa el sucesor del elemento actual.

3.

Condición de terminación. El iterador debe proveer un mecanismo que cheque si se han visitado todos los elementos, o si falta alguno por visitar.

10.3 Propiedades de las Listas Ligadas Sencillas

  Cuando se hace algo orientado a objetos, la primera pregunta a realizar es

¿Cuáles son los bloques de construcción básicos del ítem a implementar?

Echa un vistazo a la Figura 10.1, que muestra una lista consistente en cuatro rectángulos. Cada rectángulo tiene una bala en el centro, los primeros tres apuntan a su vecino de la derecha. Debido a que el último rectángulo no tiene vecino de la derecha, no hay apuntador.

 

Figura 10.1:  Bloques de construcción básicos de una lista ligada sencilla.

Primeramente escojamos nombres para estos bloques de construcción. Hablar de rectángulos no es apropiado, debido a que uno puede pensar en una figura que use círculos o triángulos.

En el campo de las gráficas se usa el nombre nodo. Un nodo contiene un apuntador a su sucesor. Así, la lista en la figura consiste en nodos, cada uno de los cuáles tiene exactamente un apuntador asociado a él.

Se pueden distinguir tres tipos de nodos :

• El primer nodo (cabeza), el cuál no tiene predecesor,
• los nodos de en medio, los cuáles tienen exactamente un predecesor y exactamente un sucesor y
• el último nodo (cola), el cuál no tiene sucesor.

Nótese que los nodos no llevan ningún contenido. Esto se debe a que la mera estructura de datos list consiste solamente en nodos, puestos en fila uno tras otro. Desde luego que las aplicaciones reales necesitan nodos, llevando algún contenido. Pero en el sentido de la orientación a objetos, ésta es una especialización de los nodos.

Por la figura podemos ver que una lista solamente puede ser usada con una estrategia de recorrido : cursor hacia adelante. Inicialmente, la cabeza será el primer elemento actual. La función sucesor simplemente va tras el apuntador de el nodo actual. La función terminación checa que el elemento actual sea efectivamente la cola.

Nótese que no es posible regresar o empezar del medio de la lista. Esto último contradiría el requerimiento de que cada elemento deba ser visitado.

La siguiente pregunta es, ¿Cuáles son las operaciones ofrecidas por una lista ? Una lista solamente define dos nodos bien identificados cabeza y cola. Echémos un vistazo más profundo a éstos últimos.

Un nuevo nodo puede ser put-in-front (puesto en el frente) de la lista de tal modo que :

• su apuntador señale a la cabeza actual,
• el nuevo nodo se convierta en la nueva cabeza.

En forma similar, un nuevo nodo puede fácilmente ser appended (añadido) a la cola:

• el apuntador a la cola señala al nuevo nodo,
• el nuevo nodo se convierte en la nueva cola.

La función inversa a poner-en-el-frente es delete-from-front (eliminar del frente):

• el nodo sucesor de la cabeza se convierte en la nueva cabeza,
• el antiguo nodo cabeza es descartado.

Deberías poder figurarte por qué no hay una función append inversa barata.

Finalmente, existen otras tres primitivas baratas, cuyo significado es inmediato. Así, no las examinaremos más. Sin embargo, las presentamos aquí para efectos de no dejar huecos :

• get-first (obtiene el primero): regresa los datos del nodo cabeza,
• get-last (obtiene el último): regresa los datos del nodo cola y por último
• is-empty (¿vacía ?): regresa información sobre si la lista está vacía o no.

10.4 Implementación de la "Forma"

 

10.4.1 Plantillas para los Nodos

  El bloque básico de construcción de una lista es el nodo. Así, declaremos primero una clase para nodos. Un nodo no tiene nada más que un apuntador a otro nodo. Asumamos que este nodo vecino siempre está del lado derecho.

Echa un vistazo a la siguiente declaración de la clase Node.

  class Node {
    Node *_right;

  public:
    Node(Node *right = NULL) : _right(right) {}
    Node(const Node &val) : _right(val._right) {}

    const Node *right() const { return _right; }
    Node *&right() { return _right; }

    Node &operator =(const Node &val) {
      _right = val._right;
      return *this;
    }

    const int operator ==(const Node &val) const {
      return _right == val._right;
    }
    const int operator !=(const Node &val) const {
      return !(*this == val);
    }
  };

Una mirada a la primera versión del método right() : contiene un const justamente antes del cuerpo del método. Cuando se usa en esta posición, const declara al método constante en lo que respecta a los elementos del objeto invocante. Por consecuencia, solamente te está permitido usar este mecanismo en declaraciones de métodos o definiciones, respectivamente.

Este tipo de modificador const también se usa para checar sobrecarga. Así,

  class Foo {
    ...
    int foo() const;
    int foo();
  };

declara dos métodos diferentes. El primero se usa en contextos constantes, mientras que el otro se usa en contextos variables.

Aunque la clase plantilla Node implementa un simple nodo, parece definir abundante funcionalidad. Hacemos esto porque es buena práctica el ofrecer al menos la siguiente funcionalidad para cada tipo de datos definido :

• Copy Constructor. El copy constructor (constructor para copia) se necesita para permitir la definición de objetos que son inicializados a partir de otros ya existentes.
• operator =. Todos los objetos deberían saber como asignarse otros objetos (del mismo tipo) a sí mismos. En nuestra clase de ejemplo, ésto es simplemente la asignación de apuntador.
• operator ==. Todo objeto debería saber como comparase a sí mismo con otro objeto.

El operador de desigualdad " !=" se implementa usando la definición del operador de igualdad. Recuerda que this apunta al objeto invocador, así,

  Node a, b;
  ...
  if (a != b) ...

resultaría en una llamada al operador operator !=() con this señalando a la dirección de a. Desreferenciamos this por medio del operador de desreferencia estándar "*". Ahora, *this es un objeto de clase Node el cuál es comparado con otro objeto, usando el operador operator ==(). Por consecuencia, se usa la definición del operador operator ==() de la clase Node. Al usar el operador booleano estándar NOT " !", negamos el resultado y obtenemos el verdadero valor de operator !=().

Los métodos de arriba deberían estar disponibles para cada clase que definas. Esto asegura que tu puedas usar tus objetos tal como usarías cualesquiera otros objetos, por ejemplo integers. Si alguno de estos métodos no tienen mucho sentido por alguna razón, tú deberías declararlos en una sección privada de la clase para explícitamente marcarlos como no de uso público. De otro modo, el compilador de C++ sustituiría los operadores estándar.

Obviamente, las aplicaciones reales requieren que los nodos lleven datos. Como se mencionó arriba, esto significa especializar los nodos. Los datos pueden ser de cualquier tipo, de ahí que estemos usando la construcción de plantilla.

  template <class T>
  class DataNode : public Node {
    T _data;

  public:
    DataNode(const T data, DataNode *right = NULL) :
      Node(right), _data(data) {}
    DataNode(const DataNode &val) :
      Node(val), _data(val._data) {}

    const DataNode *right() const { 
      return((DataNode *) Node::right());
    }
    DataNode *&right() { return((DataNode *&) Node::right()); }

    const T &data() const { return _data; }
    T &data() { return _data; }

    DataNode &operator =(const DataNode &val) {
      Node::operator =(val);
      _data = val._data;
      return *this;
    }

    const int operator ==(const DataNode &val) const {
      return(
        Node::operator ==(val) &&
        _data == val._data);
    }
    const int operator !=(const DataNode &val) const {
      return !(*this == val);
    }
  };

La plantilla DataNode de arriba simplemente especializa la clase Node para que transporte datos de cualquier tipo. Añade funcionalidad para accesar su elemento de datos y también ofrece el mismo conjunto de funcionalidad estándar : Copy Constructor, operator =() and operator ==(). Nótese como reutilizamos funcionalidades ya definidas por la clase Node.

10.4.2 Plantillas para la Lista

  Ahora ya podemos declarar la plantilla para la lista. Nosotros usamos aquí también el mecanismo de plantilla, debido a que queremos que la lista lleve datos de tipo arbitrario. Por ejemplo, queremos poder definir listas de integers. Empezamos con una plantilla de clase abstracta ListBase la cuál funciona como la clase de base para todas las otras listas. Por ejemplo, las listas doblemente ligadas obviamente comparten las mismas propiedades como lo hacen las listas ligadas sencillas.

  template <class T>
  class ListBase {
  public:
    virtual ~ListBase() {}  // Fuerza al destructor a que sea
                            // virtual
    virtual void flush() = 0;

    virtual void putInFront(const T data) = 0;
    virtual void append(const T data) = 0;
    virtual void delFromFront() = 0;

    virtual const T &getFirst() const = 0;
    virtual T &getFirst() = 0;
    virtual const T &getLast() const = 0;
    virtual T &getLast() = 0;

    virtual const int isEmpty() const = 0;
  };

Lo que realmente hacemos es describir la interface para cada lista especificando los prototipos de los métodos requeridos. Hacemos éso para cada operación que hemos identificado en la sección 10.3. Adicionalmente, incluímos también un método flush() (purgar) que nos permite eliminar todos los elementos de una lista.

Para las operaciones get-first (obtener el primero) y get-last (obtener el último) hemos declarado dos versiones. Una para uso en un contexto constante y otro para un contexto variable.

Con esta plantilla para clases abstractas, nosotros somos capaces de realmente definir nuestra plantilla de clase para lista :

  template <class T>
  class List : public ListBase<T> {
    DataNode<T> *_head, *_tail;

  public:
    List() : _head(NULL), _tail(NULL) {}
    List(const List &val) : _head(NULL), _tail(NULL) { 
      *this = val; 
    }
    virtual ~List() { flush(); }
    virtual void flush();

    virtual void putInFront(const T data);
    virtual void append(const T data);
    virtual void delFromFront();

    virtual const T &getFirst() const { return _head->data(); }
    virtual T &getFirst() { return _head->data(); } 
    virtual const T &getLast() const { return _tail->data(); }
    virtual T &getLast() { return _tail->data(); }

    virtual const int isEmpty() const { return _head == NULL; }

    List &operator =(const List &val) {
      flush();
      DataNode<T> *walkp = val._head;
      while (walkp) append(walkp->data());
      return *this;
    }

    const int operator ==(const List &val) const {
      if (isEmpty() && val.isEmpty()) return 1;
      DataNode<T> *thisp = _head,
                  *valp = val._head;
      while (thisp && valp) {
        if (thisp->data() != valp->data()) return 0;
        thisp = thisp->right();
        valp = valp->right();
      }
      return 1;
    }
    const int operator !=(const List &val) const {
      return !(*this == val);
    }

    friend class ListIterator<T>;
  };

Los constructores inicializan los elementos _head and _tail de la lista a NULL que es el apuntador NULO en C y C++. Deberías saber como implementar los otros métodos a partir de tu experiencia en programación. Aquí solamente presentamos la implementación del método putInFront():

  template <class T> void
  List<T>::putInFront(const T data) {
    _head = new DataNode<T>(data, _head);
    if (!_tail) _tail = _head;
  } /* putInFront */

Si definimos métodos de una plantilla de clase afuera de su declaración, también debemos especificar la palabra clave template. Nuevamente usamos el operador new para crear dinámicamente un nuevo nodo de datos. Este operador permite la inicialización de su objeto creado con argumentos encerrados entre paréntesis. En el ejemplo de arriba, new crea una nueva instancia de la clase DataNode$<$T$\gt$. Consecuentemente, es llamado el constructor correspondiente.

Nótese también como usamos el sustituto T. Si nosotros creáramos una instancia de la plantilla de clase List, digamos, List$<$int$\gt$ esto causaría también la creación de una instancia de clase de la plantilla de clase DataNode, a saber DataNode$<$int$\gt$.

La última línea de la declaración de la plantilla de clase declara la plantilla de clase ListIterator para que sea amiga de List. Nosotros queremos definir separadamente el iterador de la lista. Sin embargo, está my cercanamente relacionado, así que le permitimos que sea un amigo.

10.5 Implementación del Iterador

En la sección 10.2 presentamos el concepto de iteradores para recorrer una estructura de datos. Los iteradores deben implementar tres propiedades :

• Elemento actual.
• Función sucesor.
• Condición de terminación.

En términos generales, el iterador sucesivamente regresa datos asociados con el elemento actual. Obviamente, habrá un método, digamos current() que implemente esta funcionalidad. El tipo que regrese este método depende del tipo de datos almacenados en la estructura de datos particular. Por ejemplo, cuando se itera sobre List$<$int$\gt$ el tipo regresado debería ser int.

La función sucesor, digamos succ(), utiliza información adicional que está almacenada en los elementos estructurales de la estructura de datos. En nuestro ejemplo de lista, dichos elementos son los nodos los que llevan los datos y un apuntador a su vecino de la derecha. El tipo de elementos estructurales usualmente difiere de aquél de los datos en bruto. Considera nuevamente nuestra List$<$int$\gt$ donde succ() debe usar DataNode$<$int$\gt$ como elementos estructurales.

La condición de terminación es implementada por un método, digamos terminate(), el cuál regresa TRUE si (y solamente si) todos los elementos de datos de la estructura de datos asociada han sido visitados. Mientras succ() pueda encontrar un elemento aún no visitado, este método regresa FALSE.

Nuevamente, nosotros queremos especificar una clase de iterador abstracto que defina las propiedades de cada iterador. Los pensamientos de arriba conducen a la siguiente declaración :

  template <class Data, class Element>
  class Iterator {
  protected:
    Element _start,
            _current;
    
  public:
    Iterator(const Element start) : 
      _start(start), _current(start) {}
    Iterator(const Iterator &val) :
      _start(val._start), _current(val._current) {}
    virtual ~Iterator() {}

    virtual const Data current() const = 0;
    virtual void succ() = 0;
    virtual const int terminate() const = 0;

    virtual void rewind() { _current = _start; }

    Iterator &operator =(const Iterator &val) {
      _start = val._start;
      _current = val._current;
      return *this;
    }

    const int operator ==(const Iterator &val) const {
      return(_start == val._start && _current == val._current);
    }
    const int operator !=(const Iterator &val) const {
      return !(*this == val);
    }
  };

Nuevamente, nosotros usamos el mecanismo de plantilla para permitir el uso del iterador para cualquier estructura de datos que almacene datos del tipo Data y que use elementos estructurales del tipo Element. Cada iterador "conoce" un elemento inicial (estructural) y el elemento actual. Hacemos accesibles a ambos desde las clases derivadas porque los iteradores derivados necesitan accesarlos para implementar las siguientes propiedades de un iterador. Ya deberías comprender como operan los constructores y por qué forzamos al destructor a que sea virtual.

Subsecuentemente especificamos tres métodos que deberían implementar las tres propiedades de un iterador. Agregamos también un método rewind() (rebobinar) que simplemente pone el elemento actual al inicio de los elementos. Sin embargo, las estructuras de datos complejas (por ejemplo las tablas hash) pudieran requerir algoritmos de rebobinado más sofisticados. Por esa razón, también especificamos este método como virtual, permitiendo a los iteradores derivados que lo redefinan para su estructura de datos asociada.

El último paso en el proceso de implementación del iterador es la declaración del iterador de la lista. Este iterador está altamente relacionado con nuestra plantilla de la clase List, por ejemplo, está claro que los elementos estructurales son plantillas de la clase DataNode. El único tipo "abierto" es el de los datos. Una vez más, usamos el mecanismo de plantilla para proveer iteradores de lista para los diferentes tipos de listas :

  template <class T>
  class ListIterator : public Iterator<T, DataNode<T> *> {
  public:
    ListIterator(const List<T> &list) :
      Iterator<T, DataNode<T> *>(list._head) {}
    ListIterator(const ListIterator &val) :
      Iterator<T, DataNode<T> *>(val) {}

    virtual const T current() const { return _current->data(); }
    virtual void succ() { _current = _current->right(); }
    virtual const int terminate() const {
      return _current == NULL;
    }

    T &operator ++(int) {
    	T &tmp = _current->data();
    	succ();
    	return tmp;
    }

    ListIterator &operator =(const ListIterator &val) {
      Iterator<T, DataNode<T> *>::operator =(val);
      return *this;
    }
  };

La plantilla de clase ListIterator se deriva de Iterator. El tipo de datos es, por supuesto, el tipo para el cuál el iterador de la lista es declarado, de ahí que nosotros insertamos el sustituto T para el tipo de datos Data del iterador. El proceso de iteración se logra con la ayuda de los elementos estructurales del tipo DataNode. Obviamente, el elemento inicial es la cabeza de la _head la cuál es del tipo DataNode$<$T$\gt$ *. Escogemos este tipo para el tipo del elemento Element.

Nótese que el iterador de la lista en la práctica esconde los detalles acerca de los elementos estructurales. Este tipo depende grandemente de la implementación de la lista. Por ejemplo, si nosotros hubiéramos escogido una implementación de arreglo, podríamos haber usado integers como elementos estructurales donde el elemento actual sería señalado por un índice de arreglo.

El primer constructor lleva la lista a ser recorrida como su argumento e inicializa su porción del iterador en concordancia. Como cada ListIterator$<$T$\gt$ es un amigo de List$<$T$\gt$ tiene acceso a los miembros privados de la lista. Usamos esto para inicializar el iterador a que apunte a la cabeza de la lista.

Omitimos el destructor porque no tenemos ningún miembro de datos adicional para el iterador de la lista. Consecuentemente, no hacemos nada especial para éso. Sin embargo, el destructor de la plantilla de clase Iterator es llamado. Recuerad que tenemos que definir este destructor para forzar a las clases derivadas a que también tengan uno virtual.

Los métodos siguientes solamente definen las tres propiedades requeridas. Ahora que tenemos elementos estructurales definidos DataNode$<$T$\gt$ * los usamos de la siguiente manera:

• el elemento actual es el dato llevado por el elemento estructural actual,
• la función sucesor es para que el elemento estructural actual se ponga en el vecino de la derecha y the successor function is to set the current structural element to its right neighbour and
• la condición de terminación es para checar si el elemento estructural actual es el apuntador NULL. Nótese que esto solo puede suceder en dos casos :

  1.

  La lista está vacía. En este caso, el elemento actual ya es NULL porque el miembro _head de la cabeza de la lista es NULL.

  2.

  El elemento actual llegó al último elemento. En este caso la anterior llamada a la función sucesor pone el elemento actual en el vecino de la derecha del último elemento, el cuál es NULL.

Hemos incluído también un operador de postincremento "++" sobrecargado. Para distinguir este operador del operador de preincremento, lleva un argumento integer (anónimo) adicional. Como nosotros solamente usamos este argumento para declarar un prototipo de operador correcto, y porque nosotros no usamos el valor del argumento, omitimos el nombre del argumento.

El último método es el operador de asignación sobrecargado para iteradores de lista. En forma similar a los anteriores operadores de asignación, solamente reutilizamos las ya definidas asignaciones de las superclases ; Iterator$<$T$\gt$::operator =() en este caso.

Los otros métodos y operadores, a saber, rewind(), operator ==() y operator !=() son todos heredados de la plantilla de clase Iterator.

10.6 Ejemplo de Uso

  La plantilla de la lista tal como se presentó en las secciones anteriores, puede usarse del siguiente modo :

  int
  main() {
    List<int> list;
    int ix;

    for (ix = 0; ix < 10; ix++) list.append(ix);
    
    ListIterator<int> iter(list);
    while (!iter.terminate()) {
      printf("%d ", iter.current());
      iter.succ();
    }
    puts("");
    return 0;
  }

Como hemos definido un operador de postincremento para el iterador de la lista, el bucle puede ser escrito también así :

  while (!iter.terminate()) 
    print("%d ", iter++);

10.7 Discusión

 

10.7.1 Separación de la "Forma" y Estrategias de Acceso

El ejemplo presentado se enfoca sobre una perspectiva orientada a objetos. En las aplicaciones reales las listas ligadas sencillas podrían ofrecer más funcionalidades. Por ejemplo, la inserción de ítems nuevos de datos no debería presentar ningún problema debido al uso de apuntadores :

1.

Toma el apuntador sucesor del nuevo elemento y haz que apunte al elemento que debería convertirse en su vecino de la derecha.

2.

Toma el apuntador sucesor del elemento después del cuál el nuevo elemento debería ser insertado y haz que apunte al nuevo elemento.

Dos operaciones simples. Sin embargo, el problema es designar el elemento después del cuál el nuevo elemento debería ser insertado. Nuevamente, se necesita un mecanismo para recorrer la lista. Esta vez, sin embargo, el recorrido se detiene en un elemento en particular : El elemento donde la lista (o la estructura de datos) es modificada.

En forma similar a la existencia de diferentes estrategias de recorrido, uno puede pensar en diferentes estrategias de modificación. Por ejemplo, para crear una lista ordenada, donde los elementos son ordenados en sentido ascendente, usa un modificador ascendente.

Estos modificadores deben tener acceso a los elementos estructurales de la lista, y así, deberían ser declarados amigos también. Esto llevaría a la necesidad de que cada modificador deba ser amigo de su estructura de datos. Pero ¿Quién puede garantizar que no sea olvidado ningún modificador ?

Una solución es que las estrategias de modificación no sean implementadas por clases "externas" como son los iteradores. En lugar de éso, son implementadas por herencia. Si se necesita una lista ordenada, se trata de una especialización de la lista general. Esta lista ordenada añadiría un método, digamos insert(), el cuál inserta un nuevo elemento de acuerdo a la estrategia de modificación.

Para hacer esto posible, la plantilla de lista presentada debe ser cambiada. Porque ahora, las clases derivdas deben tener acceso a los nodos cabeza y cola para implementar estas estrategias. Consecuentemente, _head and _tail deberían ser protected (protegidos).

10.7.2 Iteradores

La implementación del ieterador presentada asume que la estructura de datos no sea cambiada durante el uso del iterador. Considera el siguiente ejemplo para ilustrar esto :

  List<int> ilist;
  int ix;

  for (ix = 1; ix < 10; ix++) 
    ilist.append(ix);

  ListIterator<int> iter(ilist);

  while (!iter.terminate()) {
    printf("%d ", iter.current());
    iter.succ();
  }
  printf("\n");

  ilist.putInFront(0);

  iter.rewind();
  while (!iter.terminate()) {
    printf("%d ", iter.current());
    iter.succ();
  }
  printf("\n");

Este fragmento de código imprime

  1 2 3 4 5 6 7 8 9
  1 2 3 4 5 6 7 8 9

en lugar de

  1 2 3 4 5 6 7 8 9
  0 1 2 3 4 5 6 7 8 9

Esto es debido al hecho de que nuestro iterador de lista solamente almacena apuntadores a los elementos estructurales de la lista. Así, el elemento inicial _start se pone en un principio a que señale la localización a la que apunta el nodo cabeza de la lista _head. Esto conduce simplemente a que haya dos apuntadores diferentes referenciando la misma localización. Por consecuencia, cuando se cambia un apuntador, tal como sucede cuando se invoca putInFront(), el otro apuntador no es afectado.

Por esa razón, cuando se rebobina el iterador después putInFront() el elemento actual se pone al elemento inicial, el cuál fué establecido en el momento que el constructor del iterador fue llamado. Ahora, el elemento inicial de hecho está referenciando el segundo elemento de la lista.

10.8 Ejercicios

 

1.

En forma similar a la definición del operador de postincremento en la plantilla de clase ListIterator, se podría definir un operador de preincremento así :

	  T &operator ++() {
	    succ();
	    return _current->data();
	  }

¿Qué problemas ocurren?

2.

Añade el siguiente método

	  int remove(const T &data);

a la plantilla de clase List. El método debería eliminar la primera occurrencia de data en la lista. El método debería regresar 1 si efectivamente eliminó un elemento o 0 (cero) si no lo hizo.

¿Qué funcionalidad debe proveer data? Recuerda que puede ser de cualquier tipo, ¡Especialmente clases definidas por el usuario!

3.

Deriva una plantilla de clase CountedList de List la cuál cuente sus elementos. Añade un método count() de tipo arbitrario que regrese el número actual de elementos almacenados en la lista. Trata de reutilizar de List tanto como sea posible.

4.

En relación al problema del iterador discutido en la sección 10.7. ¿Cuáles serían las posibles soluciones para permitir que la lista fuera alterada mientras un iterador de aquélla está en uso?