guide - iterator c++ ejemplo

¿Cuál es la forma más efectiva de obtener el índice de un iterador de un std:: vector?

Question

Estoy iterando sobre un vector y necesito el índice al que el iterador está apuntando actualmente. AFAIK esto se puede hacer de dos maneras:

• it - vec.begin()
• std::distance(vec.begin(), it)

¿Cuáles son los pros y los contras de estos métodos?

Answer 1

Como han demostrado UncleBens y Naveen, hay buenas razones para ambos. Cuál es "mejor" depende de qué comportamiento desea: ¿desea garantizar un comportamiento de tiempo constante, o desea volver a un tiempo lineal cuando sea necesario?

it - vec.begin() toma tiempo constante, pero el operator - solo se define en iteradores de acceso aleatorio, por lo que el código no se compilará en absoluto con los iteradores de lista, por ejemplo.

std::distance(vec.begin(), it) funciona std::distance(vec.begin(), it) para todos los tipos de iteradores, pero solo será una operación de tiempo constante si se usa en iteradores de acceso aleatorio.

Ninguno de los dos es "mejor". Usa el que hace lo que necesitas.

Answer 2

Lo preferiría it - vec.begin() precisamente por la razón opuesta dada por Naveen: así que no se compilaría si cambia el vector en una lista. Si hace esto durante cada iteración, podría fácilmente convertir un algoritmo O (n) en un algoritmo O (n ^ 2).

Otra opción, si no saltas en el contenedor durante la iteración, sería mantener el índice como un segundo contador de bucle.

Answer 3

Me gusta este: it - vec.begin() , porque para mí claramente dice "distancia desde el principio". Con los iteradores estamos acostumbrados a pensar en términos de aritmética, por lo que el signo - es el indicador más claro aquí.

Answer 4

Preferiría std::distance(vec.begin(), it) ya que me permitirá cambiar el contenedor sin ningún cambio de código. Por ejemplo, si decide utilizar std::list lugar de std::vector que no proporciona un iterador de acceso aleatorio, su código aún se compilará. Como std :: distance selecciona el método óptimo, dependiendo de los rasgos del iterador, tampoco tendrá una degradación del rendimiento.

Answer 5

Según http://www.cplusplus.com/reference/std/iterator/distance/ , dado que vec.begin() es un iterador de acceso aleatorio , el método de la distancia utiliza el operador - .

Entonces, la respuesta es, desde el punto de vista del rendimiento, que es la misma, pero tal vez usar distance() sea ​​más fácil de entender si alguien tendría que leer y entender su código.

Answer 6

Si ya está restringido / codificado su algoritmo para usar solo un std::vector::iterator y std::vector::iterator , no importa qué método terminará usando. Su algoritmo ya se concreta más allá del punto en el que elegir uno del otro puede hacer cualquier diferencia. Ambos hacen exactamente lo mismo. Es solo una cuestión de preferencia personal. Yo personalmente usaría la resta explícita.

Si, por otro lado, desea conservar un mayor grado de generalidad en su algoritmo, es decir, para permitir la posibilidad de que algún día en el futuro se aplique a algún otro tipo de iterador, entonces el mejor método depende de su intención. . Depende de qué tan restrictivo quiera ser con respecto al tipo de iterador que se puede usar aquí.

• Si utiliza la resta explícita, su algoritmo se restringirá a una clase de iteradores bastante restringida: iteradores de acceso aleatorio. (Esto es lo que obtienes ahora de std::vector )

• Si usa distance , su algoritmo admitirá una clase mucho más amplia de iteradores: iteradores de entrada.

Por supuesto, calcular la distance para los iteradores de acceso no aleatorio es, en general, una operación ineficiente (mientras que, de nuevo, para los de acceso aleatorio es tan eficiente como la resta). Depende de usted decidir si su algoritmo tiene sentido para los iteradores de acceso no aleatorio, en términos de eficiencia. Si la pérdida de eficiencia resultante es devastadora hasta el punto de hacer que su algoritmo sea completamente inútil, entonces debería apegarse a la resta, prohibiendo así los usos ineficientes y obligando al usuario a buscar soluciones alternativas para otros tipos de iteradores. Si la eficiencia con los iteradores de acceso no aleatorio todavía está dentro del rango utilizable, entonces debe usar la distance y documentar el hecho de que el algoritmo funciona mejor con los iteradores de acceso aleatorio.

Answer 7

Usaría la variante - para std::vector - está bastante claro lo que significa, y la simplicidad de la operación (que no es más que una resta del puntero) se expresa mediante la sintaxis ( distance , en el otro lado) , suena como pitágoras en la primera lectura, ¿no es así?). Como señala UncleBen, - también actúa como una aserción estática en caso de que el vector se cambie accidentalmente a la list .

También creo que es mucho más común, aunque no tengo números para probarlo. Argumento maestro: it - vec.begin() es más corto en código fuente, menos trabajo de escritura, menos espacio consumido. Como está claro que la respuesta correcta a su pregunta se reduce a ser una cuestión de gustos, esto también puede ser un argumento válido.