c++ - programacion - ¿Puedo convertir un iterador inverso en un iterador directo?

libreria para listas c++

Question

Tengo una clase llamada Action , que es esencialmente un contenedor alrededor de una decena de objetos Move .

Debido a que necesito atravesar el deque de Moves tanto hacia adelante como hacia atrás, tengo un iterador directo y un reverse_iterator como variables miembro de la clase. La razón de esto es porque necesito saber cuándo he pasado el "final" del deque, tanto cuando estoy yendo hacia adelante como hacia atrás.

La clase se ve así:

class Action
{
public:
    SetMoves(std::deque<Move> & dmoves) { _moves = dmoves; }
    void Advance();
    bool Finished() 
    {
        if( bForward )
            return (currentfwd==_moves.end());
        else
            return (currentbck==_moves.rend());
    }
private:
    std::deque<Move> _moves;
    std::deque<Move>::const_iterator currentfwd;
    std::deque<Move>::const_reverse_iterator currentbck;
    bool bForward;
};

La función Advance es la siguiente:

void Action::Advance
{
    if( bForward)
        currentfwd++;
    else
        currentbck++;
}

Mi problema es que quiero poder recuperar un iterador para el objeto Move actual, sin necesidad de consultar si estoy avanzando o retrocediendo. Esto significa que una función devuelve un tipo de iterador, pero tengo dos tipos.

¿Debo olvidar devolver un iterador y devolver una referencia constante a un objeto Move ?

Los mejores deseos,

BeeBand

Answer 1

Como std::deque es un contenedor de acceso aleatorio (igual que std::vector ), es mucho mejor usar un único índice entero en el deque para ambos recorridos.

Answer 2

Este es exactamente el tipo de problema que impulsó el diseño de STL para comenzar. Hay razones reales para:

1. No almacena iteradores junto con contenedores
2. Usar algoritmos que aceptan iteradores arbitrarios
3. Tener algoritmos evaluar un rango completo en lugar de un solo elemento a la vez

Sospecho que lo que estás viendo ahora es más o menos la punta del iceberg de los problemas reales. Mi consejo sería dar un paso atrás y, en lugar de preguntar cómo lidiar con los detalles del diseño actual, formule una pregunta un poco más general sobre lo que está tratando de lograr y la mejor manera de lograrlo. resultado final.

Para aquellos que se preocupan principalmente por la pregunta en el título, la respuesta es un "sí" muy calificado. En particular, un reverse_iterator tiene un miembro base() para hacer eso. Las calificaciones son algo problemáticas sin embargo.

Para demostrar el problema, considere un código como este:

#include <iostream>
#include <vector>
#include <iterator>

int main() { 
    int i[] = { 1, 2, 3, 4};
    std::vector<int> numbers(i, i+4);

    std::cout << *numbers.rbegin() << "/n";
    std::cout << *numbers.rbegin().base() << "/n";
    std::cout << *(numbers.rbegin()+1).base() << "/n";

    std::cout << *numbers.rend() << "/n";
    std::cout << *numbers.rend().base() << "/n";
    std::cout << *(numbers.rend()+1).base() << "/n";
}

Ejecutar esto en este momento particular en mi máquina particular produce el siguiente resultado:

4
0
4
-1879048016
1
-1879048016

Resumen: con rbegin() debemos agregar uno antes de convertirlo a un iterador directo para obtener un iterador que sea válido, pero con rend() no debemos agregar uno antes de convertir para obtener un iterador válido.

Siempre que use X.rbegin() y X.rend() como parámetros para un algoritmo genérico, está bien, pero la experiencia indica que la conversión a iteradores de reenvío a menudo genera problemas.

Al final, sin embargo, para el cuerpo de la pregunta (en oposición al título), la respuesta es más o menos la que se da arriba: el problema surge al tratar de crear un objeto que combine la colección con un par de iteradores en esa colección . Repara ese problema y todo el negocio con iteradores directo e inverso se vuelve irrelevante.

Answer 3

Los iteradores inversos tienen una base() miembros base() que devuelve un iterador directo correspondiente. Tenga en cuenta que este no es un iterador que se refiere al mismo objeto, sino que se refiere al siguiente objeto de la secuencia. Esto es para que rbegin() corresponda con end() y rend() corresponde con begin() .

Entonces, si quieres devolver un iterador, entonces harías algo como

std::deque<Move>::const_iterator Current() const
{
    if (forward)
        return currentfwd;
    else
        return (currentbck+1).base();
}

Sin embargo, preferiría devolver una referencia y encapsular todos los detalles de la iteración dentro de la clase.

Answer 4

Me parece que en realidad tienes dos comportamientos diferentes en la misma clase.

Notablemente, parece que solo puede atravesar su colección en un orden, de lo contrario, si comenzara el recorrido y luego cambiara el argumento hacia adelante, terminaría en una situación bastante extraña.

Personalmente, estoy a favor de exponer ambos iteradores (es decir, avanzar begin, end, rbegin and rend ).

También puede devolver un objeto Iterador simple:

template <class T>
class Iterator
{
public:
  typedef typename T::reference_type reference_type;

  Iterator(T it, T end) : m_it(it), m_end(end) {}

  operator bool() const { return m_it != m_end; }

  reference_type operator*() const { return *m_it; }

  Iterator& operator++() { ++m_it; return *this; }

private:
  T m_it;
  T m_end;
};

template <class T>
Iterator<T> make_iterator(T it, T end) { return Iterator<T>(it,end); }

Entonces, puedes devolver este simple objeto:

class Action
{
public:
  Action(std::deque<Move> const& d): m_deque(d) {} // const& please

  typedef Iterator< std::deque<Move>::iterator > forward_iterator_type;
  typedef Iterator< std::deque<Move>::reverse_iterator > backward_iterator_type;

  forward_iterator_type forward_iterator()
  {
    return make_iterator(m_deque.begin(), m_deque.end());
  }

  backward_iterator_type backward_iterator()
  {
    return make_iterator(m_deque.rbegin(), m_deque.rend());
  }


private:
  std::deque<Move> m_deque;
};

O si desea elegir dinámicamente entre recorrido hacia adelante y hacia atrás, puede hacer que Iterator sea una interfaz virtual pura y tenga un recorrido tanto hacia adelante como hacia atrás.

Pero en realidad, realmente no veo el punto de almacenar AMBOS repetidores hacia adelante y hacia atrás si parece que solo usará uno: /

Answer 5

Tal vez deberías reconsiderar tu elección de contenedor.

Por lo general, no es necesario utilizar iteradores inversos para retroceder.

currentfwd--

irá hacia atrás, aunque podría no funcionar (lo que supongo que probaste) con dequeue.

Lo que realmente debería hacer es modelar su clase aquí como decorador de dequeue e implementar sus propios iteradores de Acción. Eso sería lo que haría de todos modos.