Iterador de C ++, ¿por qué no hay una clase base de Iterador de la que todos los iteradores heredan?

Estoy aprendiendo para un examen y tengo una pregunta que me cuesta responder y responder.

¿Por qué no existe una clase base de iterador que todos los otros iteradores hereden?

Supongo que mi maestro se está refiriendo a la estructura jerárquica de la referencia de cpp " http://prntscr.com/mgj542 " y tenemos que proporcionar otra razón además de por qué deberían hacerlo.

Sé qué son los iteradores (más o menos) y que se usan para trabajar en contenedores. Por lo que entiendo debido a las diferentes estructuras de datos subyacentes posibles, los diferentes contenedores tienen diferentes iteradores porque puede acceder aleatoriamente a una matriz, por ejemplo, pero no a una lista vinculada y los diferentes contenedores requieren diferentes formas de moverse a través de ellos.

Probablemente sean plantillas especializadas según el contenedor, ¿verdad?

Ya ha recibido respuestas que indican por qué no es necesario que todos los iteradores hereden de una sola clase base Iterator. Sin embargo, había llegado un poco más lejos. Uno de los objetivos de C ++ es la abstracción con un costo de tiempo de ejecución cero.

Si los iteradores trabajaran todos ellos heredando de una clase base común, y usaran funciones virtuales en la clase base para definir la interfaz, y las clases derivadas proporcionaran implementaciones de esas funciones virtuales, eso podría (y a menudo) agregaría un tiempo de ejecución sustancial gastos generales a las operaciones involucradas.

Consideremos, por ejemplo, una jerarquía de iterador simple que usa herencia y funciones virtuales:

template <class T>
class iterator_base { 
public:
    virtual T &operator*() = 0;
    virtual iterator_base &operator++() = 0;
    virtual bool operator==(iterator_base const &other) { return pos == other.pos; }
    virtual bool operator!=(iterator_base const &other) { return pos != other.pos; }
    iterator_base(T *pos) : pos(pos) {}
protected:
    T *pos;
};

template <class T>
class array_iterator : public iterator_base<T> {
public: 
    virtual T &operator*() override { return *pos; }
    virtual array_iterator &operator++() override { ++pos; return *this; }
    array_iterator(T *pos) : iterator_base(pos) {}
};

Entonces demos una prueba rápida:

int main() { 
    char input[] = "asdfasdfasdfasdfasdfasdfasdfadsfasdqwerqwerqwerqrwertytyuiyuoiiuoThis is a stringy to search for something";
    using namespace std::chrono;

    auto start1 = high_resolution_clock::now();
    auto pos = std::find(std::begin(input), std::end(input), 'g');
    auto stop1 = high_resolution_clock::now();

    std::cout << *++pos << "\n";

    auto start2 = high_resolution_clock::now();
    auto pos2 = std::find(array_iterator(input), array_iterator(input+sizeof(input)), 'g');
    auto stop2 = high_resolution_clock::now();

    std::cout << *++pos2 << "\n";

    std::cout << "time1: " << duration_cast<nanoseconds>(stop1 - start1).count() << "ns\n";
    std::cout << "time2: " << duration_cast<nanoseconds>(stop2 - start2).count() << "ns\n";
}

[nota: dependiendo de su compilador, es posible que deba hacer un poco más, como definir iterator_category, difference_type, reference, etc., para que el compilador acepte el iterador.]

Y la salida es:

y
y
time1: 1833ns
time2: 2933ns

[Por supuesto, si ejecuta el código, sus resultados no coincidirán exactamente con estos.]

Entonces, incluso para este caso simple (y haciendo solo unos 80 incrementos y comparaciones) hemos agregado alrededor del 60% de gastos generales a una búsqueda lineal simple. Especialmente cuando los iteradores se agregaron originalmente a C ++, bastantes personas simplemente no habrían aceptado un diseño con tanta sobrecarga. Probablemente no habrían sido estandarizados, e incluso si lo hubieran hecho, prácticamente nadie los usaría.

La diferencia es entre lo que es algo y cómo se comporta algo.

Muchos idiomas intentan combinar los dos, pero son cosas muy distintas.

Si cómo es qué, y qué es cómo ...

Si todo hereda de objectentonces, se producen algunos beneficios como: cualquier variable de objeto puede tener cualquier valor. Pero ese también es el problema, todo debe comportarse ( el cómo ) como un object, y verse como ( el qué ) un object.

Pero:

• ¿Qué pasa si su objeto no tiene una definición significativa de igualdad?
• ¿Qué pasa si no tiene un hash significativo?
• ¿Qué pasa si su objeto no puede ser clonado, pero los objetos sí pueden serlo?

O bien, el objecttipo se vuelve esencialmente inútil, debido a que el objeto no proporciona elementos comunes en todas las instancias posibles. O existirán objetos que tengan una definición rota / con cuernos de zapato / absurda de alguna supuesta propiedad universal encontrada en la objectcual se produce un comportamiento casi universal, excepto por una serie de trampas.

Si lo que no está relacionado con cómo

Alternativamente, puede mantener separados el Qué y el Cómo . Luego, varios tipos diferentes (sin nada en común en absoluto qué ) pueden comportarse de la misma manera que el colaborador ve cómo . En este sentido, la idea de un Iteratorno es un qué específico , sino un cómo . Específicamente, ¿ cómo interactúa con una cosa cuando aún no sabe con qué está interactuando?

Java (y similares) permiten enfoques para esto mediante el uso de interfaces. Una interfaz a este respecto describe los medios de comunicación e implícitamente un protocolo de comunicación y acción que se sigue. Cualquier Qué que se declare como de un Cómo dado , afirma que apoya la comunicación y la acción relevantes descritas por el protocolo. Esto permite a cualquier colaborador confiar en el Cómo y no atascarse al especificar exactamente qué se puede usar.

C ++ (y similares) permiten enfoques para esto escribiendo pato. A una plantilla no le importa si el tipo colaborador declara que sigue un comportamiento, solo que dentro de un contexto de compilación dado, con el objeto se puede interactuar de una manera particular. Esto permite que los punteros de C ++ y los objetos que anulan operadores específicos sean utilizados por el mismo código. Porque cumplen con la lista de verificación para ser considerados equivalentes.

• admite * a, a->, ++ a y a ++ -> iterador de entrada / reenvío
• admite * a, a->, ++ a, a ++, --a y a-- -> iterador bidireccional

El tipo subyacente ni siquiera tiene que estar iterando un contenedor, podría ser cualquier cosa . Además, permite que algunos colaboradores sean aún más genéricos, imaginen que una función solo necesita a++, un iterador puede satisfacer eso, un puntero, un entero, cualquier objeto podría implementarse operator++.

Especificación por debajo y por encima

El problema con ambos enfoques está por debajo y por encima de la especificación.

El uso de una interfaz requiere que el objeto declare que admite un comportamiento dado, lo que también significa que el creador debe imbuirlo desde el principio. Esto hace que algunos Qué no hagan el corte, ya que no lo declararon. También significa que siempre lo que tiene un antepasado común, la interfaz que representa el cómo . Esto vuelve al círculo del problema inicial de object. Esto hace que los colaboradores especifiquen en exceso sus requisitos, mientras que simultáneamente hacen que algunos objetos sean inutilizables debido a la falta de declaración, o que se oculten las trampas ya que el comportamiento esperado está mal definido.

El uso de una plantilla requiere que el colaborador trabaje con un Qué completamente desconocido y, a través de sus interacciones, define un Cómo . Hasta cierto punto, esto dificulta la escritura de los colaboradores, ya que debe analizar el Qué para sus primitivas de comunicación (funciones / campos / etc.) mientras evita errores de compilación, o al menos señalar cómo un determinado Qué no cumple con sus requisitos para el Cómo . Esto permite que el colaborador requiera el mínimo absoluto de cualquier What , lo que permite el rango más amplio de lo que se utilizará. Desafortunadamente, esto tiene la desventaja de permitir usos sin sentido de objetos que técnicamente proporcionan las primitivas de comunicación para un determinadoCómo , pero no sigas el protocolo implícito que permite que ocurran todo tipo de cosas malas.

Iteradores

En este caso, una Iteratores una ¿Cómo es la abreviatura de una descripción de la interacción. Cualquier cosa que coincida con esa descripción es, por definición, un Iterator. Knowing How nos permite escribir algoritmos generales y tener una breve lista de ' Cómo ' se le da un Qué específico 'que se debe proporcionar para que el algoritmo funcione. Esa lista son las funciones / propiedades / etc, su aplicación tiene en cuenta la específica Lo que está siendo tratado por el algoritmo.

Porque C ++ no necesita tener clases base (abstractas) para hacer polimorfismo. Tiene subtipos estructural , así como subtipos nominativa .

Confusamente en el caso particular de los iteradores, los estándares anteriores definidos std::iteratorcomo (aproximadamente)

template <class Category, class T, class Distance = std::ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
}

Es decir, simplemente como un proveedor de los tipos de miembros requeridos. No tenía ningún comportamiento de tiempo de ejecución, y quedó en desuso en C ++ 17

Tenga en cuenta que incluso esto no puede ser una base común, ya que una plantilla de clase no es una clase, cada instanciación es independiente de las demás.

Una razón es que los iteradores no tienen que ser instancias de una clase. Los punteros son iteradores perfectamente buenos en muchos casos, por ejemplo, y dado que son primitivos, no pueden heredar nada.