c++ - geeksforgeeks - ¿Qué es un iterador en general?
list iterator c++ (3)
Este problema surge cuando intenté escribir una plantilla de clase C ++ con ctor que acepte "iterador general". No sé si es apropiado usar la palabra general aquí, pero lo que quiero decir es que puede aceptar el iterador como el contenedor STL.
En otras palabras, estoy confundido acerca de iterador . Parece que todos los contenedores STL tienen el mismo tipo de iterador, entonces, ¿qué es ese tipo? ¿Es solo puntero? ¿O algo más complicado? Pero el contenedor STL acepta puntero normal.
(Me gustaría compararlo con Iterator<T> en Java , que es bastante simple y es solo una clase)
En C ++, un Iterador es un concepto , no un tipo concreto (o abstracto), sino cualquier tipo que obedezca a ciertas reglas tipo iterador .
Por ejemplo, los iteradores generalmente pueden incrementarse ++i . Se puede acceder a ellos (sin referencia) *i para obtener el valor al que apuntan actualmente. Son esencialmente abstracciones de un puntero .
En los contenedores y algoritmos de la biblioteca estándar hay diferentes tipos de iteradores con diferentes propiedades. Sus propiedades se enumeran aquí:
en.cppreference.com/w/cpp/iterator
Entonces, cuando se escriben algoritmos en C ++ que aceptan iteradores, generalmente solo se aceptan parámetros de plantilla genéricos y se usan las propiedades de iterador apropiadas en la función. El compilador se quejará si el usuario pasa algo a su función que no obedece las reglas del iterador:
template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
for(; begin != end; ++begin)
std::cout << *begin << ''/n'';
}
Puede agregar un montón de controles específicos para asegurarse de que el usuario haya pasado algo sensato, pero eso es demasiado amplio para esta pregunta.
Nota:
Si bien los conceptos actuales, como en.cppreference.com/w/cpp/named_req/Iterator , son simplemente un conjunto de propiedades semánticas acordadas en el Estándar que deben seguir los programadores, una solución más completa que formalizará dichos conceptos (en código) está destinada a la próxima versión del Estándar, C++20 .
Iterador es un patrón de diseño de comportamiento descrito como parte de "Cuadrilla de cuatro patrones de diseño". Resuelve un problema con la iteración sobre objetos en un objeto agregado sin conocer la estructura interna de ese objeto.
Consulte a continuación para obtener más detalles sobre el patrón de iterador: http://www.blackwasp.co.uk/Iterator.aspx
Los iteradores como concepto provienen de antes de que C ++ fuera un estándar.
C ++ comenzó como C con las clases. Se agregaron más funciones y un número cada vez mayor de personas se interesaron en el idioma.
Una parte muy importante del trabajo se llamó STL, la Biblioteca de plantillas estándar, originalmente escrita por Stepanov y Lee. en 1994 en Hewlett-Packard, posteriormente mantenido por SGI.
Esta biblioteca utilizó la parte de metaprogramación de la plantilla de C ++ de maneras bastante revolucionarias. Fue escrito para permitir un rendimiento casi normal con tipos abstractos, con implementaciones de algoritmos divorciados de implementaciones de contenedores, para tipos casi arbitrarios.
Los iteradores son un concepto - un tipo más alto de tipo
En ella, el iterador era un concepto . Un concepto en C ++ es una categoría de tipos (un tipo de tipos que podría decir). Los conceptos en C ++ no son aplicados por el compilador (en este momento).
Un tipo satisface un concepto si tiene las operaciones requeridas, y esas operaciones respetan las reglas del concepto.
Existe una jerarquía de conceptos en torno a los iteradores en el STL y más adelante en el estándar C ++. Van del menos restrictivo (un iterador) al más (un iterador contiguo de acceso aleatorio de lectura-escritura), y forman un árbol.
Funciones de plantilla funciones de escritura
Cuando un algoritmo de plantilla solicita un iterador, solicita un tipo que satisfaga el concepto de iterador (como se describe en el estándar de C ++). Cuando solicitan un RandomAccessIterator, solicitan un tipo que satisfaga el concepto de RandomAccessIterator (que también incluye el concepto Iterator, el concepto ForwardIterator y algunos otros).
Entonces, la template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator ) es una función de plantilla que toma dos instancias del mismo tipo que satisfacen el concepto ForwardIterator.
ForwardIterators tiene que admitir varias operaciones ( *it , ++it , bool b = it != it bool b = it == it , bool b = it == it , etc), admiten ciertos rasgos ( iterator_traits<it>::iterator_category , iterator_traits<it>::reference , iterator_traits<it>::value_type , etc), y esas operaciones deben seguir ciertas reglas.
Si lo alimenta con un tipo que satisface RandomAccessIterator, std::sort garantiza un mejor rendimiento que si se pasa un ForwardIterator .
Un puntero en bruto satisface ambos iteradores Forward RandomAccess sin que usted haga nada. std::vector<?>::iterator también satisface ambos, pero a menudo no es un puntero en bruto (la biblioteca estándar hizo algún trabajo).
Los dos tipos, el puntero sin formato y std::vector<?>::iterator , generalmente son tipos no relacionados. El sistema de plantillas y rasgos de C ++ permite que los tipos no relacionados sean comprendidos por el mismo algoritmo de plantilla con una sobrecarga de tiempo de ejecución cero.
En c ++ 2a, hay planes para introducir conceptos en el lenguaje que verifiquen algunos de los requisitos para cosas como RandomAccessIterator y documenten en el lenguaje los otros requisitos que prácticamente no se pueden verificar.
C ++ no es un lenguaje OO
Posiblemente se confunda al estar acostumbrado a lenguajes orientados a objetos. C ++ admite la programación orientada a objetos, pero no es un lenguaje orientado a objetos. Admite el polimorfismo, que trata el mismo tipo de múltiples tipos, sin herencia basada en objetos de varias maneras.
En un lenguaje orientado a objetos, cada iterador heredaría de un tipo de iterador abstracto. Los algoritmos interactuarían con el iterador a través de esa interfaz abstracta, a menudo enviando llamadas a través de una tabla de funciones virtuales de algún tipo. Los valores del tipo no serían posibles, ya que el código del algoritmo se compilaría sin saber cuántos bytes toman los iteradores, por lo que se produciría una indirección adicional.
En C ++, el algoritmo no es una función hasta que le pasas el tipo del iterador. En ese punto, la función está escrita a medida para ese iterador. El estándar de C ++ establece que si el iterador hace ciertas cosas (obedece al Concepto requerido), la función escrita por la plantilla tendrá cierto comportamiento.
Esta función escrita en la plantilla sabe qué tan grande es el iterador, qué hacen las operaciones, puede alinear las operaciones y almacenar instancias del iterador en búferes o en la pila como un valor. A menos que el iterador lo obligue, no hay un envío virtual, y si las operaciones son visibles, se pueden insertar en la función escrita.
El compilador puede examinar los bucles ajustados y la vectorización puede ocurrir, como si usted escribiera la función a mano.
La misma plantilla puede ordenar entradas de base de datos o cadenas o enteros; en cada caso se escribe una nueva función, y se le dice al compilador que intente hacerla funcionar más rápido.
TL; DR
Los iteradores no son un tipo; Son una especie de tipo. Los tipos completamente no relacionados pueden ser iteradores. No hay clase base para los iteradores; Sólo hay ciertas formas en que garantizan que se comportan.
Los algoritmos de C ++ generan un código personalizado para cada tipo de iterador que se pasa a std::sort ; si ordena un vector de int y un vector de cadenas, no se comparte ningún código binario entre los dos (excepto la posibilidad de comdat fold).
Los conceptos (tipo de tipo) Iterator / ForwardIterator / RandomAccessIterator son requisitos documentados sobre los tipos pasados a los algoritmos de C ++. No se hace ninguna aplicación, excepto que el compilador es libre de hacer literalmente cualquier cosa si no cumple con los requisitos.