Una vez definidos los algoritmos de inserción, eliminación e intercambio de nodos en la lista mediante la estructura detail::Node_base (véase el primer post de esta serie), procederemos a implementar la lista doblemente enlazada como una plantilla uniparamétrica de clase List<>, donde el parámetro indique el tipo de variable almacenada.
Los elementos almacenados en la lista (nodos) constarán de tres campos, a saber: los punteros prev y next a los nodos inmediatamente anterior y posterior, respectivamente, así como el área de datos. Emplearemos la herencia como mecanismo básico para añadir la información contenida en la estructura detail::Node_base (es decir, los punteros de posicionamiento) a una nueva estructura privada List<>::Node que contenga, esta vez sí, el área de datos:
Los elementos almacenados en la lista (nodos) constarán de tres campos, a saber: los punteros prev y next a los nodos inmediatamente anterior y posterior, respectivamente, así como el área de datos. Emplearemos la herencia como mecanismo básico para añadir la información contenida en la estructura detail::Node_base (es decir, los punteros de posicionamiento) a una nueva estructura privada List<>::Node que contenga, esta vez sí, el área de datos:
template<typename T>
class List {
struct Node : detail::Node_base { // herencia pública
T dat; // dato almacenado
Node(T const& d) : dat{d} { };
};
detail::Node_base dnb_; // nodo centinela
public:
struct List_iterator; // ver definición más abajo
struct List_const_iterator;
// resto de la interfaz pública...
};
Observemos que una lista contiene un subobjeto detail::Node_base, de nombre dnb_, que actuará como nodo centinela. Éste no almacenará, por supuesto, ningún dato: tan sólo proporcionará un indicador natural para finalizar las iteraciones a lo largo de la estructura. Asimismo, y con el fin de facilitar la implementación de los métodos de la clase, enlazaremos la lista circularmente a través de dicho nodo centinela, tal y como se muestra en la figura inferior. De esta manera, será posible acceder al inicio o al fondo de la lista partiendo del nodo centinela con una sola operación de avance o retroceso, respectivamente (dnb_.next en el primer caso y dnb_.prev en el segundo).
Resulta inmediato codificar los constructores de la clase, junto al operador de asignación copia, atendiendo al esquema planteado arriba:
El constructor por defecto, aquél que inicializa la estructura vacía, deja aislado al nodo centinela, de modo que sus campos prev y next apuntan al propio nodo. Por su parte, el constructor copia crea primeramente una lista vacía llamando al constructor por defecto. A continuación, y de forma segura ante excepciones, introduce en el fondo de nuestra estructura una copia de cada elemento encontrado en la lista other mediante llamadas sucesivas a la función miembro push_back(). De producirse una excepción, se borra el contenido acumulado hasta ese momento en la lista invocando al método clear() y se relanza la excepción. Por supuesto, para que el bucle for basado en rango contenido en el constructor copia funcione correctamente, necesitaremos dotar a la lista de las funciones begin() y end() habituales, así como definir unos iteradores bidireccionales adecuados List_iterator y List_const_iterator para la misma.
List() noexcept // inicializa una lista vacía
: dnb_{&dnb_, &dnb_} { } // invariante de la clase
List(List<T> const& other) // constructor copia
: List<T>{}
{
try {
for (auto const& val : other)
push_back(val);
}
catch (...) {
clear();
throw;
}
}
List<T>& operator=(List<T> const& other) // operador de asignación-copia
{
// copy-and-swap idiom (garantía fuerte ante excepciones):
auto tmp = List<T>{other};
dnb_.swap(tmp.dnb_);
return *this;
} // tmp (que contiene la lista original) es automáticamente destruido aquí
El constructor por defecto, aquél que inicializa la estructura vacía, deja aislado al nodo centinela, de modo que sus campos prev y next apuntan al propio nodo. Por su parte, el constructor copia crea primeramente una lista vacía llamando al constructor por defecto. A continuación, y de forma segura ante excepciones, introduce en el fondo de nuestra estructura una copia de cada elemento encontrado en la lista other mediante llamadas sucesivas a la función miembro push_back(). De producirse una excepción, se borra el contenido acumulado hasta ese momento en la lista invocando al método clear() y se relanza la excepción. Por supuesto, para que el bucle for basado en rango contenido en el constructor copia funcione correctamente, necesitaremos dotar a la lista de las funciones begin() y end() habituales, así como definir unos iteradores bidireccionales adecuados List_iterator y List_const_iterator para la misma.
En relación a los iteradores, éstos deben permitir el acceso secuencial a los elementos
almacenados en la lista sin necesidad de exponer la estructura interna
de la misma. Deberán ser implementados, para ello, como clases que
sobrecarguen los operadores necesarios para su uso. Concretamente, la
definición de la clase List_iterator toma la forma siguiente:
Recordemos que un iterador bidireccional it cualquiera, tal y como explicamos en un post anterior, debe proporcionar las operaciones de acceso (it->), lectura (=*it) y escritura (*it=) en sentido ascendente (++) y descendente (--). Debe ser, asimismo, comparable con otros iteradores de su misma clase (==,!=).
struct List_iterator {
detail::Node_base* node;
explicit List_iterator(detail::Node_base* node_ = nullptr) noexcept
: node{node_} { }
bool operator==(List_iterator const& rhs) const noexcept { return node == rhs.node; }
bool operator!=(List_iterator const& rhs) const noexcept { return node != rhs.node; }
T& operator*() const
{
return static_cast<Node*>(node)->dat; // downcasting seguro
}
T* operator->() const noexcept
{
return std::address_of(static_cast<Node*>(node)->dat); // ídem
}
List_iterator& operator++() noexcept // prefijo
{
node = node->next;
return *this;
}
List_iterator operator++(int) noexcept // sufijo
{
auto tmp = *this;
node = node->next;
return tmp;
}
List_iterator& operator--() noexcept // prefijo
{
node = node->prev;
return *this;
}
List_iterator operator--(int) noexcept // sufijo
{
auto tmp = *this;
node = node->prev;
return tmp;
}
};
Observemos que la estructura Node deriva públicamente de Node_base: de ser necesaria una conversión explícita de un puntero Node_base* a un puntero Node* (habiéndonos asegurado, por supuesto, de que dicha operación tenga sentido), podemos hacer uso del operador static_cast.
Una definición similar a la de la estructura anterior puede introducirse para los iteradores a objetos constantes List_const_iterator.
Gracias a ambos tipos de iteradores, las funciones miembro insert(), erase(), push_back(), begin() y end() son inmediatas de codificar:
void insert(List_iterator position, T const& val) // garantía fuerte
{
Node* p = new Node{val};
p->hook(position.node); // inserta el nuevo nodo delante de position
}
List_iterator erase(List_iterator position) noexcept
{
List_iterator ret{position.node->next};
position.node->unhook();
delete static_cast<Node*>(position.node);
return ret;
}
void push_back(T const& val) { insert(List_iterator{&dnb_}, val); }
List_const_iterator begin() const noexcept { return List_const_iterator{dnb_.next}; }
List_iterator begin() noexcept { return List_iterator{dnb_.next}; }
List_const_iterator end() const noexcept { return List_const_iterator{&dnb_}; }
List_iterator end() noexcept { return List_iterator{&dnb_}; }
La función miembro pública clear() borra el contenido actual de la lista, dejando al nodo centinela aislado, en el modo siguiente:
El destructor de la lista consiste sencillamente en una llamada a la función anterior:
Otras muchas funciones miembro pueden ser definidas con facilidad para enriquecer la interfaz pública de la lista. Así, por ejemplo, las siguientes funciones de capacidad permiten determinar el tamaño actual de la lista o averiguar de forma directa si ésta se encuentra vacía:
void clear() noexcept
{
auto current = dnb_.next;
while (current != &dnb_) {
auto tmp = current;
current = current->next;
delete static_cast<Node*>(tmp);
}
dnb_.next = dnb_.prev = &dnb_;
}
El destructor de la lista consiste sencillamente en una llamada a la función anterior:
~List() { clear(); }
Otras muchas funciones miembro pueden ser definidas con facilidad para enriquecer la interfaz pública de la lista. Así, por ejemplo, las siguientes funciones de capacidad permiten determinar el tamaño actual de la lista o averiguar de forma directa si ésta se encuentra vacía:
std::size_t size() const noexcept // O(n)
{
auto sz = std::size_t{0};
auto p = dnb_.next;
while (p != &dnb_) {
++sz;
p = p->next;
}
return sz;
}
bool empty() const noexcept { return dnb_.next == &dnb_; }
Referencias bibliográficas:
- GCC Compilers - libstdc++ API - https://gcc.gnu.org/onlinedocs/gcc-6.1.0/libstdc++/api/. La lista estándar std::list<> se encuentra distribuida bajo la licencia GPL v3, con una cláusula adicional heredada de SGI. Consúltense los términos de distribución en https://gcc.gnu.org/onlinedocs/gcc-6.1.0/libstdc++/api/a01624_source.html.
- Cormen T. H., et al., Introduction to Algorithms, 3rd Edition, MIT Press.
No hay comentarios:
Publicar un comentario