5.1.2e  Iteradores de acceso aleatorio

§1  Sinopsis

Los iteradores de acceso aleatorio (RandomAccessIterator) presentan un comportamiento similar a los punteros ordinarios cuando referencian a miembros de matrices [1], lo que significa que pueden utilizarse con ellos los mismos operadores. Por ejemplo, aceptan el operador de elemento de matriz [ ] (que aquí deberíamos denominar de "acceso a elemento de contenedor" 4.9.16), que permiten realizar entre ellos la operación resta, para obtener la "distancia" entre dos iteradores ( 5.1.2), o suma con un entero para obtener un desplazamiento determinado.

Es interesante observar que en el caso de las matrices, la aritmética de sus punteros está directamente relacionada con el almacenamiento subyacente, ya que las matrices son colecciones de objetos que ocupan posiciones de memoria contiguas.  Por ejemplo, si M es una matriz de enteros, M+3 se refiere al cuarto elemento a partir del principio, que además está físicamente alojado en la tercera posición de memoria con respecto al miembro inicial. Sin embargo, en un contenedor estándar, esta relación se pierde. Si It es un iterador de acceso aleatorio referido al primer elemento de un contenedor C.  It+3 se refiere al cuarto elemento según un orden lógico, pero el elemento no está necesariamente en la tercera posición de memoria física después del primero.

§2  Descripción

Los iteradores de acceso aleatorio se utilizan en algoritmos genéricos para operaciones tales como ordenaciones ("Sort") y búsquedas binarias ("Binary search").  Por ejemplo, el código que sigue reordena aleatoriamente los elementos de un contenedor de forma similar a la función random_shuffle() de la STL.

template <class RandomAccessIterator>
  void mixup (RandomAccessIterator first, RandomAccessIterator last) {
    while (first < last) {
      iter_swap(first, first + randomInteger(last - first));
      ++first;
    }
  }
unsigned int randomInteger (unsigned int n) {  // funcion auxiliar
  return rand() % n;
}

Comentario:

El programa realiza un bucle mientras se cumpla la condición first < last.  Recuerde que este operador solo puede ser utilizado entre iteradores de acceso aleatorio ( 5.1.2).

El valor pasado como argumento a la función auxiliar randomInteger() es la distancia n entre ambos iteradores. Esta función devuelve un número aleatorio entero entre 0 y el valor n de su argumento.  Utiliza a su vez la función rand();  una función de la librería Estándar C (que hemos denominado "clásica" 5) descrita en la cabecera <stdlib.h>, y el operador módulo % ( 4.9.1).

En cada iteración el miembro del contenedor señalado por el primer puntero, es intercambiado aleatoriamente con otro situado más adelante, utilizando el algoritmo iter_swap() que acepta dos iteradores genéricos como argumento y responde a la siguiente interfaz:

template <class ForwardIterator1, class ForwardIterator2>
   void iter_swap (ForwardIterator1, ForwardIterator2);

  Inicio.

---

[1]  Hemos indicado repetidamente que estos punteros gozan de todas las características de los iteradores de acceso aleatorio, y pueden utilizarse con los algoritmos de la STL que soportan este tipo de iterador.