Algoritmos (II)

Tipos de iteradores

Los iteradores son fundamentales en la implementación de algoritmos genéricos de tratamientos de datos, pues permiten el acceso secuencial a los elementos almacenados en una colección sin necesidad de exponer la estructura interna de la misma.

En las implementaciones habituales de los vectores (matrices unidimensionales de datos almacenadas en el free store, cuyo tamaño puede variar durante el tiempo de ejecución), los iteradores suelen definirse como simples alias de punteros tradicionales que apuntan al tipo de objeto contenido (para más información, puedes consultar Stroustrup B., "The C++ Programming Language". Addison-Wesley, 4th Edition, 2013):

   template<typename T>    class Vector {       T* v_,     // inicio de la memoria alojada        * space_, // final de la secuencia, inicio de capacidad adicional        * last_;  // final de la memoria total alojada    public:       using const_iterator = T const*; // equivalente a: typedef T const* const_iterator       using       iterator = T*;       auto begin() const noexcept -> const_iterator { return v_; }       auto begin()       noexcept -> iterator       { return v_; }       auto end()   const noexcept -> const_iterator { return space_; }       auto end()         noexcept -> iterator       { return space_; }       // ...    };

Con carácter general, sin embargo, los iteradores deben ser implementados como clases o estructuras que sobrecarguen los operadores necesarios para su uso. Tal es el caso, por ejemplo, de los iteradores proporcionados por una lista (en la imagen inferior, doblemente enlazada con nodo centinela dnb_):

   struct Node_base {       Node_base* prev,              * next;       // ...    };    template<typename T>    class List { // lista doblemente enlazada       struct Node : Node_base {          T dat;       };       Node_base dnb_; // nodo base centinela    public:       struct iterator {          Node_base* node;          auto operator==(iterator rhs) const noexcept -> bool { return node == rhs.node; }          auto operator!=(iterator rhs) const noexcept -> bool { return node != rhs.node; }          auto operator*() const -> T& { return static_cast<Node*>(node)->dat; }          auto operator->() const noexcept -> T*                   { return std::addressof(static_cast<Node*>(node)->dat); }          auto& operator++() noexcept { node = node->next; return *this; }          auto& operator--() noexcept { node = node->prev; return *this; }          // añadir versiones sufijo de operator++ y operator--       };       auto begin() noexcept { return iterator{dnb_.next}; }       auto end()   noexcept { return iterator{&dnb_}; }       // ...    };

Todo iterador, sea un puntero o la instancia de una clase, debe poder ser construido como copia de otro dado (CopyConstructible), reasignado como copia de otro ya existente (CopyAssignable), destruible (Destructible) e intercambiable (Swappable). Asimismo, debe ser desreferenciable dentro del rango de acceso permitido a la colección de datos (una expresión del tipo *it debe tener el efecto esperado) e incrementable (++it debe devolver una referencia a un iterador que apunte al elemento inmediatamente posterior al inicialmente referenciado).

En base a las funcionalidades adicionales ofrecidas por el tipo de iterador, éste puede clasificarse como perteneciente a una de las siguientes cinco categorías fundamentales:

• InputIterator: Sólo lectura (=*it) en sentido ascendente (++), permitiendo operaciones de acceso (it->) y de comparación (==,!=).

• OutputIterator: Sólo escritura (*it=) en sentido ascendente (++); no es comparable ni permite acceso con el operador ->.

• ForwardIterator: Acceso (it->), lectura (=*it) y escritura (*it=) en sentido ascendente (++). Es comparable (==,!=).

• BidirectionalIterator: Acceso (it->), lectura (=*it) y escritura (*it=) en sentido ascendente (++) y descendente (--). Es comparable (==,!=).

• RandomAccessIterator: Acceso (it->), lectura (=*it) y escritura (*it=) en sentido ascendente y descendente con un offset arbitrario (++,--,+n,-n,+=n,-=n). Es comparable (==,!=,<,>,<=,>=).

Así, el iterador proporcionado por la plantilla de clase Vector<> indicada anteriormente es, al tratarse de un puntero tradicional, de acceso aleatorio (RandomAccessIterator), mientras que el iterador de la lista List<> es de tipo bidireccional (BidirectionalIterator).