c++ - libreria - Devolver un ''cualquier tipo de iterador de entrada'' en lugar de un vector:: iterador o una lista:: iterador

libreria vector c++

Question

Esta pregunta ya tiene una respuesta aquí:

• Generic iterator 3 respuestas

Supongamos que quiero implementar en C ++ una estructura de datos para almacenar gráficos orientados. Los arcos se almacenarán en Nodos gracias a los contenedores STL. Me gustaría que los usuarios puedan iterar sobre los arcos de un nodo, de una manera similar a STL.

El problema que tengo es que no quiero exponer en la clase Node (que en realidad será una clase base abstracta) qué contenedor STL usaré realmente en la clase concreta. Por lo tanto, no quiero que mis métodos devuelvan std :: list :: iterator o std :: vector :: iterator ...

Intenté esto:

class Arc;

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator;  // Wrong!

class Node {
public:
  ArcIterator incomingArcsBegin() const {
    return _incomingArcs.begin();
  }
private:
  std::vector<Arc*> _incomingArcs;
};

Pero esto no es correcto porque un vector :: const_iterator no se puede usar para crear un ArcIterator. Entonces, ¿qué puede ser este ArcIterator?

Encontré este artículo sobre Iteradores personalizados para el STL pero no ayudó. Debo ser un poco pesado hoy ...;)

Answer 1

Bueno, porque std::vector está garantizado para tener un almacenamiento contiguo, debe ser perfecto bien para hacer esto:

class Arc;
typedef Arc* ArcIterator;

class Node {
public:
    ArcIterator incomingArcsBegin() const {
        return &_incomingArcs[0]
    }

    ArcIterator incomingArcsEnd() const {
        return &_incomingArcs[_incomingArcs.size()]
    }
private:
    std::vector<Arc*> _incomingArcs;
};

Básicamente, los punteros funcionan lo suficiente como iteradores de acceso aleatorio que son un reemplazo suficiente.

Answer 2

Busqué en el archivo de encabezado VECTOR.

vector<Arc*>::const_iterator

es un typedef para

allocator<Arc*>::const_pointer

¿Podría ser ese tu ArcIterator? Me gusta:

typedef allocator<Arc*>::const_pointer ArcIterator;

Answer 3

C ++ 0x te permitirá hacer esto con determinación automática de tipo .

En el nuevo estándar, esto
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
puede ser reemplazado con esto
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

De la misma manera, podrá devolver cualquier iterador que sea apropiado y almacenarlo en una variable auto .

Hasta que el nuevo estándar entre en vigor, tendrías que personalizar tu clase o proporcionar una interfaz abstracta para acceder a los elementos de tu lista / vector. Por ejemplo, puede hacerlo almacenando un iterador en la variable miembro y proporcionar funciones de miembro, como begin() y next() . Esto, por supuesto, significaría que solo un ciclo a la vez puede iterar con seguridad sobre sus elementos.

Answer 4

Eche un vistazo al any_iterator de Adobe: esta clase usa una técnica llamada tipo borrado por la cual el tipo de iterador subyacente está oculto detrás de una interfaz abstracta. Cuidado: el uso de any_iterator incurre en una penalización de tiempo de ejecución debido al envío virtual.

Answer 5

Para ocultar el hecho de que sus iteradores se basan en std::vector<Arc*>::iterator , necesita una clase de iterador que delegue en std::vector<Arc*>::iterator . std::iterator no hace esto.

Si observas los archivos de cabecera en la biblioteca estándar de C ++ de tu compilador, es posible que std::iterator no sea muy útil por sí solo, a menos que lo único que necesites sea una clase que defina typedefs para value_type , value_type , etc.

Como Doug T. mencionó en su respuesta, la biblioteca de impulso tiene clases que facilitan la escritura de iteradores. En particular, boost::indirect_iterator puede ser útil si desea que sus iteradores devuelvan un Arc cuando se desreferencia en lugar de un Arc* .

Answer 6

Podría templatar la clase Node y escribir en él el iterador y el const_iterator.

Por ejemplo:

class Arc {};

template<
  template<class T, class U> class Container = std::vector,
  class Allocator = std::allocator<Arc*>
>
class Node
{
  public:
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator;
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator;

    constArcIterator incomingArcsBegin() const {
      return _incomingArcs.begin();
    }

    ArcIterator incomingArcsBegin() {
      return _incomingArcs.begin();
    }
  private:
    Container<Arc*, Allocator> _incomingArcs;
};

No he probado este código, pero te da la idea. Sin embargo, debe tener en cuenta que el uso de un ConstArcIterator simplemente no permitirá la modificación del puntero al Arc, no la modificación del Arc en sí (a través de métodos non-const, por ejemplo).

Answer 7

Prueba esto:

class Arc;
class Node {
private:
  std::vector<Arc*> incoming_;
public:
  typedef std::vector<Arc*>::iterator iterator;
  iterator incoming_arcs_begin()
  { return incoming_.begin(); }
};

Y use Node :: iterator en el resto del código. Cuando / si cambia el contenedor, debe cambiar typedef en un solo lugar. (Podría avanzar un paso más con typedef adicional para el almacenamiento, en este caso vector).

En cuanto a la cuestión const, defina el const_iterator del vector como su iterador, o defina los tipos de doble iterador (const y nonconst version) como lo hace el vector.

Answer 8

Quiero pensar que debería haber una forma de hacerlo mediante STL directo, similar a lo que estás tratando de hacer.

De lo contrario, es posible que desee estudiar el uso de fachadas y adaptadores de iteradores de boost donde puede definir sus propios iteradores o adaptar otros objetos a los iteradores.

Answer 9

Si realmente no desea que los clientes de esa clase sepan que utiliza un vector debajo, pero aún así desean que puedan iterar de alguna manera sobre él, lo más probable es que necesiten crear una clase que reenvíe todos sus métodos a std :: vector :: iterador.

Una alternativa sería templarar el nodo según el tipo de contenedor que debería usar debajo. Luego, los clientes saben específicamente qué tipo de contenedor está usando porque les dijeron que lo usen.

Personalmente, no creo que tenga sentido encapsular el vector lejos del usuario, pero aún así proporcionar la mayoría (o incluso algunas) de su interfaz. Es demasiado delgada de una capa de encapsulación para proporcionar realmente algún beneficio.

Answer 10

Considere usar el patrón de visitante e invertir la relación: en lugar de preguntarle a la estructura de gráfico por un contenedor de datos, le da al gráfico un funtor y deja que el gráfico aplique ese funtor a sus datos.

El patrón de visitante es un patrón comúnmente utilizado en los gráficos, consulte la documentación de la biblioteca de gráficos de boost en los conceptos de los visitantes.