¿A dónde apunta el rend?

Question

Para admitir la noción de STL de rangos semiabiertos, se nos permite señalar uno más allá de una matriz. Supongamos que tenemos un vector de tres elementos. Si std::vector::iterator se implementa como un puntero, como suele ser el caso en las versiones de lanzamiento, a continuación, begin y end punto a estas ubicaciones:

+---+---+---+.... 
    | | | | . 
    +---+---+---+.... 
    ^  ^
    begin  end 

donde los puntos denotan el pseudo-elemento de una sola past-the-final. Dado que no existe tal cosa como un one-before-the-beginning, ¿dónde exactamente podría indicar rend? Permítanme ilustrar:

+---+---+---+.... 
    | | | | . 
    +---+---+---+.... 
^  ^
rend  rbegin 

Claramente, la ilustración es malo, porque rend es un puntero ilegal. Así que supongo que la implementación de std::vector::reverse_iterator nunca puede ser un puntero, incluso en compilaciones de versiones.

¿Estoy en lo cierto? Entonces, ¿cuál sería la forma más eficiente de implementar reverse_iterator?

Answer 1

Hay una diferencia entre a qué apunta lógicamente un reverse_iterator y a qué apunta su iterador. Lógicamente, rbegin produce un iterador que apunta al último elemento de la secuencia y rend produce un iterador que apunta a un elemento antes del inicio. Pero esto generalmente se implementa con un iterador base que apunta a un elemento más allá del elemento al que apunta el iterador inverso. Algo como esto:

template<class Iter> 
class reverse_iter 
{ 
    Iter base; 
public: 
    explicit reverse_iter(Iter it) : base(it) {} 

    reference operator*() const { 
     Iter tmp = base; 
     --tmp; 
     return *tmp; 
    } 

    reverse_iter& operator++() {--base; return *this;} 
}; 

lo tanto, si se inicializa un objeto tal reverse_iter<> con container.end() los puntos de iterador de base a uno más allá del final pero dereferencing el iterador inverso le dará el último elemento. Ningún daño hecho.

Answer 2

Como no se permite desreferenciar un iterador que apunta fuera del contenedor, en realidad no importa a qué rend() "apunta". No tiene que ser un valor del puntero legal, puede ser cualquier valor que tenga un significado particular para el tipo contenedor/iterador.

Answer 3

La interfaz std::reverse_iterator incluye una función de miembro .base que recupera un iterador igual al original. Sospecho que lo que suelen hacer es simplemente almacenar en caché el iterador original, y compensarlo por 1 en la sobrecarga del operador *.

Answer 4

El resultado de rbegin puntos a la misma como end (uno más allá del final), y el resultado de rend a la misma como begin (el primer elemento). Cuando se quita la referencia de un iterador inverso, se devuelve una referencia al elemento anterior en el rango.

Answer 5

Las otras respuestas responden bien la pregunta.

Pero también me pregunto si sería legal de todos modos, ya que presumiblemente una implementación puede hacer lo que quiera detrás de las escenas, siempre y cuando funcione y cumpla con los estándares. Si elige implementar el iterador como un puntero y elige desreferencia, entonces es responsabilidad de los compiladores saber que funcionará. No podría implementarlo de esta manera, pero me parece que el autor del compilador tiene una licencia especial para hacer esto, ya que sabe cuál será el comportamiento indefinido, y no le exponga ese comportamiento directamente, solo a través de una interfaz de iterador.